鑑於某種情況，如何決定數據結構？

Question

我正準備參加技術面試，並且主要面臨基於情境的問題。通常情況是一個大數據集，我被要求決定哪一個將是最優化的數據結構。

我熟悉大多數數據結構及其實現和性能。但是當我處於困境並對結構產生決定性影響時，我陷入困境。

尋找在給定情況下遵循的步驟/算法，這可以幫助我在面試時間內獲得最佳數據結構。

Answer 1

• 從公共數據結構開始。問題是否可以通過數組，哈希表，列表或樹（或它們的簡單組合，例如hastables或類似的數組）有效地解決？

• 如果有多個選項，只需對通用操作的運行時進行迭代即可。通常情況下，一個數據結構在爲採訪設定的場景中顯然是勝利者。如果不是，只要告訴面試官你的發現，例如「A需要O（n^2）來構建，然後可以在O（1）中處理查詢，而B構建和查詢時間都是O（n）。因此，對於一次性使用，我會使用B，否則A「。在某些情況下，空間消耗也可能是相關的。

• 高度專業化的數據結構（例如前綴樹又名「Trie」）常常是：針對特定的特定情況高度專業化。面試官通常應該對你從現有的通用庫中構建有用的東西的能力更感興趣 - 反對了解可能沒有太多現實世界用法的各種奇特數據結構。也就是說，額外的知識永遠不會受到傷害，只是準備討論你所提到的優點和缺點（面試官可能會探討你是否只是「名字下降」）。

Answer 2

這取決於您需要哪些操作來有效支持。

讓我們從最簡單的例子開始 - 你有一個大的元素列表，你必須找到給定的元素。讓我們考慮各種候選人

您可以使用排序數組使用二進制搜索在O（log N）時間中查找元素。如果你想支持插入和刪除，那該怎麼辦？在最壞的情況下，將元素插入排序數組需要O（n）個時間。 （想想在開始時添加一個元素，必須將所有元素都移到右側）。現在來到二分查找樹（BST）。它們可以支持在O（log N）時間插入，刪除和搜索元素。

現在您需要支持兩項操作，即查找最小值和最大值。在第一種情況下，它只是分別返回第一個和最後一個元素，因此複雜度爲O（1）。假設BST是一個像紅黑樹或AVL樹的平衡類型，找到最小值和最大值需要O（log N）時間。考慮需要返回第k個順序統計量的另一種情況。排序的數組再次勝出。正如你所看到的那樣有一個折衷，它取決於你給的問題。

我們再舉一個例子。您會得到一個V頂點和E邊的圖形，您必須在圖中找到連接組件的數量。它可以在O（V + E）時間內使用深度優先搜索（假定鄰接列表表示）完成。考慮另一種情況，即邊緣增量式增加，並且可以在流程中的任何時間點詢問連接組件的數量。在這種情況下，可以使用具有秩和路徑壓縮啓發式的數據結構，對於這種情況它非常快。

另一個示例 - 您需要支持範圍更新，高效地查找子數組的總和，並且沒有新元素插入到數組中。如果你有一個由N個元素組成的數組，並給出Q查詢，那麼有兩種選擇。如果範圍總和查詢僅在「全部」更新操作的數量爲Q'之後出現。然後，您可以在O（N + Q'）時間內對數組進行預處理，並在O（1）時間（存儲前綴和）中回答任何查詢。如果沒有執行這樣的命令呢？你可以使用帶有惰性傳播的段樹。它可以用O（N log N）時間構建，每個查詢可以在O（log N）時間內執行。所以你總共需要O（（N + Q）log N）時間。同樣，如果插入和刪除與所有這些操作一起支持，會發生什麼？您可以使用名爲Treap的數據結構，它是一種概率數據結構，所有這些操作都可以在O（log N）時間內執行。 （使用隱式衝突）。

注：的常數，而使用大哦省略表述。他們中的一些人常常隱藏在他們的複雜性中。