Java面试题: get entry by two fields in O(log(n)) time

你好有一个面试任务，想法是用字段存储元素:id，name，updateTime；

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

要求:

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

注意事项

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

我的想法

我不能使用 CopyOnWriteArrayList，因为如果键是 id，则需要 O(N) 才能找到最后更新的元素，这违反了要求。

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

我可以使用两棵树，第一棵通过 id 进行比较，第二棵通过 updateTime 进行比较，但是我应该同步所有访问方法，这使得我的程序成为单线程

我想我已经接近了，只需要找到如何使用 O(log(N)) 获取元素，但我的想法已经用完了。

请您参考如下方法:

希望我理解正确。

如果您需要存储元素并且“添加”和“获取”时间低至 (log(N))，这听起来像经典的 HashMap (如果搜索时间达到，则使用链表哈希和二叉树一定的阈值-我相信从 Java 8 开始)。 所以在最坏的情况下它是 log(N)。

对于“获取上次更新”功能:您可以将每个更新的元素存储在堆栈中(不是真正的堆栈，只是您不断添加的列表)以及执行该功能的时间。只需对列表执行二进制搜索。当您到达最后一分钟更新的第一个项目时 - 只需将索引返回到该项目。

那样你只执行二进制搜索 (log(N))。

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