求问个面经设计题目

Job Hunting Interview
, , , ,
1

让你实现一些API，假定每个单词有一个定义，<word, defination>，然后实现

1. void add(word, def) 
2. void remove(word)
3. void update(word, def)
4. String lookup(word) return defition
5. printOut() 打印出所有的 <word, def> pair 并且按照word排序。
  1. 第一种想的是用一个map。 add，remove，update，lookup都是O(1), printOut排序nlogn
  2. 第二种想的是两个map, 其中一个是TreeMap， 这样 update, lookup O(1)， add, remove O(logn) 复杂度, printOut() O(n) 复杂度

看面经贴说，面试官让他 add，remove，update，lookup都是O(1), printOut排序O(n)，可以用任意数据结构，这个有可能吗？

求问大佬们想法，谢谢

2

什么公司的？

4

小公司，wealthfront

5

感觉不可能。除非add word的顺序有什么特殊的条件

6

如果input word有limit的话，可以用buckets做，也就是 bucket sort

7

哦哦，我也觉得这要求也太特别了，谢谢X老师！

8

O(n) 的话也只有 bucket sort 了

9

如果word长度是限定的，比如说word.length() < 1000这种，用Trie就对了。add，remove，update，lookup，所有针对一个单词的操作，都是遍历一边这个长度。排序的话，建树的时候就保证alphabetical小的在前面就行。