关于一道API 设计的题目

让你实现一些API，假定每个单词有一个定义，<word, defination>，然后实现
1.add(word, def), void      
2. remove(word), void
3. update(word, def),  void
4. lookup(word) 返回def
5.printOut() 打印出所有的 <word, def> pair 并且按照word排序。

我用的方法是用两个map, 其中一个是TreeMap， 这样可以保证 update, lookup O(1) 复杂度,       add, remove O(logn) 复杂度, printOut() O(n) 复杂度

后来要求是 add 和 remove 也O(1) 其他的时间复杂度不变。。

不用考虑空间复杂度，可以使用任意的数据结构

有没有大佬知道的

看得我太乱了。。。大家现在都喜欢扔个词儿就跑的交流方式吗。。。我整理了半天才明白LZ题目是啥，要求是啥。

用 LinkedHashMap 可以做到 add/remove/lookup O(1)要求，
排序的话，quick select 的 average case 和 best case，可以做到 O(n)
但感觉这么考能考啥。。。。考记忆复杂度吗。。。有点二说实话，LZ move on 吧，别太难过了

肥颓 发表于 2019-11-7 18:38
这放py 就是很典型的dictionary 的用法 没有任何trick 的。。。
简直就是dictionary 的定义。。。

跟语言没关系，py只是叫dict，本质上还是hash map

这题如果不是print要O(n)，确实就是python上dict，java上hashmap就行了

肥颓 发表于 2019/11/08 08:38:42
这放py 就是很典型的dictionary 的用法 没有任何trick 的。。。
简直就是dictionary 的定义。。。

Printout需要排序的，要on

这放py 就是很典型的dictionary 的用法 没有任何trick 的。。。
简直就是dictionary 的定义。。。

add 应该也是O(1), remove 也是O(1),

不是哈希表吗

按照什么东西排序？

肥颓 发表于 2019-11-8 10:16
按照什么东西排序？

按照字母的顺序比如 aa,ab 是对的，ab,aa是错的

匿名者 发表于 2019-11-8 10:19
按照字母的顺序比如 aa,ab 是对的，ab,aa是错的

printout 需要 O(n) 并且还要排序

为啥要匿名啊。。。。。。。。
字典序的话

我就会维护一个堆，然后插入是logn

其他的一样

肥颓 发表于 2019/11/08 10:50:10
为啥要匿名啊。。。。。。。。
字典序的话

我就会维护一个堆，然后插入是logn

其他的一样

选错了，这是一道面试题目，不匿名了。
要求是O(1)，logn 之后要我变成constant time