Java面试问题:在O(log(n))时间内按两个字段输入

Question

Hi有一个面试任务，这个想法是用字段存储元素：id，name，updateTime；

应该有方法add(Element)，getElement(id)，getLastUpdatedElements()

需求：

• 代码应该在Java上
• 应该是线程安全的
• 计算复杂度的上限--所有这些方法都应该是O(log(n))

Notes

• 可以在运行时更改任何元素的更新时间。
• getLastUpdatedElements -返回更新的最后一分钟元素

我的想法

我不能使用CopyOnWriteArrayList，因为如果键是id，则需要O(N)来查找最后更新的元素，是什么破坏了需求。

为了在getLastUpdatedElements()中适应O(log(N))的复杂性，我可以通过updateTime使用ConcurrentSkipListSet和比较器，但在这种情况下，通过ID获得元素需要O(N)。(请注意，在这种情况下，add(Element)是O(log(N))，因为我们知道新创建的元素的updateTime )。

我可以使用两种树，第一种是id的比较器，第二种是updateTime的比较器，但是所有的访问方法都应该同步使我的程序是单线程的。

我想我已经接近了，只是需要找出如何用O(log(N))来获取元素，但是我的想法已经不多了。

Answer 1

我希望我能正确理解你。

如果您需要存储元素，并将"add“和"get”的时间降到最低(log(N))，这听起来就像经典的散列映射(如果搜索时间达到某个阈值时使用链接列表散列和二叉树--因为我相信是java 8)。所以最坏的情况是log(N)。

对于"get最后更新“函数:您可以将每个更新的元素存储在堆栈中(实际上不是堆栈，只是一个不断添加的列表)和函数执行的时间。只需对列表执行二进制搜索即可。当您到达最后一分钟更新的第一项时，只需将索引返回到该项。

这样，您只执行二进制搜索(log(N))。

当然，这两种数据结构都有一个锁。如果您真的想从性能角度深入研究它，您可以实现两个锁:一个用于插入/更新条目，另一个用于读取条目。类似于“读者-作家问题”，如：https://www.tutorialspoint.com/readers-writers-problem