关于一道API 设计的题目

midaliuliu 发表于 2019-11-8 10:53
选错了，这是一道面试题目，不匿名了。
要求是O(1)，logn 之后要我变成constant time

但如果你要维持输出有序，那肯定总时间复杂度要nlogn 的
只是说你把排序放到哪里完成罢了

肥颓 发表于 2019/11/08 10:55:21
但如果你要维持输出有序，那肯定总时间复杂度要nlogn 的
只是说你把排序放到哪里完成罢了

是啊，我觉得没办法两全吧，可是就是让我全部O1, printout是on。

hashmap+trie

hashmap记录从word到trie的node。

add：按字符串去更新trie和hashmap。串长可以认为是O(1). 所以为O(1)

其他操作类似

printout即前序遍历这颗树。O(n)

求讨论，求米

codeyy 发表于 2019/11/08 11:10:12
hashmap+trie

hashmap记录从word到trie的node。

add：按字符串去更新trie和hashmap。串长可以认为是O(1). 所以为O(1)

其他操作类似

print...

这个方法我想了，他告诉我用trie不算O1。。。我当时就无语了

midaliuliu 发表于 2019/11/08 11:32:33
这个方法我想了，他告诉我用trie不算O1。。。我当时就无语了

同无语。所以word用可能无限长？seriously？

Trie 的插入 复杂度应该是O(n) n是插入word的 长度。而且用trie 的话，难度有点高了
Hash table 的增删应该是O(1)啊， 为什么是O(log N)。 如果用priority queue 之类的，那复杂度直接就是NlogN吧， 不过这样输出降低到了O（n）
用hash table 应该没啥问题。 print的话，我觉得这边需要排序，要NlogN，避免不了的。

midaliuliu 发表于 2019-11-8 10:58
是啊，我觉得没办法两全吧，可是就是让我全部O1, printout是on。

有没有可能是什么mapreduce 的法子。。。
hash 过去然后归并出来。。。。

直接用LinkedHashMap就完了吧

Nevermore777 发表于 2019/11/09 01:17:46
直接用LinkedHashMap就完了吧

排序也可以吗

Nevermore777 发表于 2019-11-9 01:17
直接用LinkedHashMap就完了吧

好像确实可以