关于一道API 设计的题目

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

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

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

maljean 发表于 2019-11-7 22:01
Trie 的插入 复杂度应该是O(n) n是插入word的 长度。而且用trie 的话，难度有点高了
Hash table 的增删应 ...

priority queue 要输出应该是O(nlgn)吧？每个元素O(lgn）啊

一剑终情 发表于 2019-11-9 04:59
priority queue 要输出应该是O(nlgn)吧？每个元素O(lgn）啊

取决于你要什么时候排序了 如果是输入logn 就未必了

我觉得做不到lookup/update/add/remove都是O(1)然后printout是o(n)啊。毕竟print的是排序的结果，那么这样的话这个数据结构实现了o(n)复杂度的排序算法 ，这是不可能的啊。。。

jeff070496 发表于 2019-11-9 05:30
我觉得做不到lookup/update/add/remove都是O(1)然后printout是o(n)啊。毕竟print的是排序的结果，那么这样 ...

我也觉得啊，我面试的时候没打出来 直接跪了

https://www.1point3acres.com/bbs/thread-568438-1-1.html

stream?
stream.collect(toSet())默认是不reserve order的，我遇到过直接给我sorted结果的情况。。。

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

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