设计一个高度优化的数据结构来执行insert、delete和getRandom三个操作

Question

我刚参加了一个软件面试。其中一个问题是以高度优化的方式设计具有insert、delete和getRandom三种方法的任何数据结构。面试官让我想出一个数据结构的组合来设计一个新的数据结构。插入是可以设计的，但是对于随机和删除，我需要获取特定元素的位置。他给了我一个提示，让我考虑一下排序所需时间最少的数据结构。

欢迎任何回答或讨论……

Answer 1

假设t是您想要存储在数据结构中的元素的类型。拥有一个可扩展的数组elements，其中包含所有没有特定顺序的元素。有一个哈希表indices，它将t类型的元素映射到它们在elements中的位置。

• Inserting e意思是
  • 在e的末尾加上elements (即push_back)，把它的位置i
  • insert映射到`indices

中

​

• 删除e意味着
  • 通过elements
  • update indices的最后一个元素f找到e在elements中的位置e：删除映射(f,indices.size())并插入(f,i)

​

• 随机绘制一个元素(将其保留在数据结构中，即它是peek，而不是pop)只是在[0,elements.size()[中绘制一个整数i并返回elements[i].

假设哈希表非常适合您的t类型的元素，那么所有三个操作都是O(1)。

注意数据结构中有0个或1个元素的情况。

Answer 2

在这里，一棵树可能工作得很好。Order log(n) insert和delete，choose也可以是log(n)：从根节点开始，在每个交叉点随机选择一个子节点(由每个子节点的叶节点总数加权)，直到到达一个叶节点。

Answer 3

排序所需时间最少的数据结构是排序数组。

get_random()是二进制搜索，所以O(log )。

insert()和delete()涉及添加/删除有问题的元素，然后重新排序，这是O(n log n)，例如可怕。

我认为他的暗示很糟糕。你可能参加了一个糟糕的面试。