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

wayfarer 阅读:19 2023-08-02 22:59:51 评论:0

你好有一个面试任务,想法是用字段存储元素:idnameupdateTime

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

要求:

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

注意事项

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

我的想法

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

为了适应 getLastUpdatedElements() 的 O(log(N)) 复杂性,我可以使用 ConcurrentSkipListSetupdateTime 的比较器,但在那种情况下通过 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


标签:面试
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号