在给定的情况下，如何决定数据结构？

Question

我正在准备参加技术面试，遇到的大多数问题都是情景based.Often，情景是一个大数据集，我被要求决定使用哪种最优的数据结构。

我熟悉大多数数据结构，它们的实现和性能。但在给定的情况下，我陷入了进退两难的境地，并对结构持果断态度。

寻找在给定情况下可以遵循的步骤/算法，这些步骤/算法可以帮助我在面试的时间段内达到最佳数据结构。

Answer 1

这取决于您需要有效地支持哪些操作。

让我们从最简单的例子开始-你有一个很大的元素列表，你必须找到给定的元素。让我们考虑一下不同的候选人

您可以使用对数排序数组通过二进制搜索在O(log )时间内找到一个元素。如果你想同时支持插入和删除，该怎么办？在最坏的情况下，将一个元素插入到排序数组中需要O(n)时间。(考虑在开头添加一个元素。您必须将所有元素向右移动一个位置)。现在出现了二进制搜索树(BST)。它们可以在O(log )时间内支持元素的插入、删除和搜索。

现在您需要支持两个操作，即查找最小值和最大值。在第一种情况下，它只分别返回第一个和最后一个元素，因此复杂度为O(1)。假设BST是像红黑树或AVL树那样的平衡树，求最小和最大值需要O(log )时间。考虑另一种情况，您需要返回第k个顺序统计量。同样，排序数组胜出。正如您所看到的，这是一个权衡，这实际上取决于您遇到的问题。

让我们举另一个例子，。您将看到一个包含V个顶点和E个边的图，您必须找到图中连通分量的数量。使用深度优先搜索(假设邻接表表示)，它可以在O(V+E)时间内完成。考虑另一种情况，其中边是递增添加的，并且可以在过程中的任何时间点询问连接的组件的数量。在这种情况下，可以使用具有等级和路径压缩启发式Disjoint Set Union数据结构，且对于这种情况是非常快的。

又一个示例-你需要支持范围更新，高效地找到一个子数组的和，并且没有新的元素插入到数组中。如果您有一个由N个元素组成的数组，并且提供了Q个查询，那么有两个选择。如果范围和查询只在“所有”更新操作之后出现，这些操作在数量上是Q‘。然后，您可以在O(N+Q')时间内对数组进行预处理，并在O(1)时间内回答任何查询(存储前缀和)。如果没有强制执行这样的命令怎么办？为此，您可以使用带有延迟传播的Segment Tree。它可以在O(N log N)时间内构建，每次查询可以在O(log N)时间内执行。所以总共需要O((N+Q)log )时间。同样，如果所有这些操作都支持插入和删除，该怎么办？您可以使用一个名为Treap的数据结构，它是一种概率数据结构，所有这些操作都可以在O(log )时间内执行。(使用隐式treap)。

注意：在使用Big Oh表示法时省略了常量。它们中的一些在其复杂性中隐藏着很大的常量。

Answer 2

• 从常见的数据结构开始。可以使用数组、哈希表、列表或树(或者它们的简单组合，例如，hastables或类似的数组)有效地解决问题吗？
• 如果有多个选项，只需迭代常见操作的运行时。通常，在为面试设置的场景中，一种数据结构是明显的赢家。如果没有，就告诉面试官你的发现。"A需要O(n^2)来构建，但查询可以在O(1)内处理，而对于B，构建和查询时间都是O(n)。因此，对于一次性使用，我将使用B，否则使用A。“在某些情况下，空间消耗可能也是相关的。
• 高度专门化的数据结构(例如，前缀树，也称为"Trie")通常是:对于特定的特定情况，高度专门化。面试官通常应该更感兴趣的是你从现有的通用库中构建有用东西的能力--而不是了解各种可能在现实世界中没有太多用处的奇异数据结构。也就是说，额外的知识没有坏处，只要准备好讨论你提到的东西的利弊(面试官可能会调查你是否只是在“丢掉名字”)。