---

數據結構與算法面試題

數據結構

紅黑樹說一下

紅黑樹(Red-Black Tree)是一種自平衡的二叉搜索樹，它在插入和刪除操作后能夠通過旋轉和重新著色來保持樹的平衡。紅黑樹的特點如下：

• 每個節點都有一個顏色，紅色或黑色。
• 根節點是黑色的。
• 每個葉子節點（NIL節點）都是黑色的。
• 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
• 從根節點到葉子節點或空子節點的每條路徑上，黑色節點的數量是相同的。

紅黑樹通過這些特性來保持樹的平衡，確保最長路徑不超過最短路徑的兩倍，從而保證了在最壞情況下的搜索、插入和刪除操作的時間復雜度都為O(logN)。epoll 用了紅黑樹來保存監聽的 socket。

跳表說一下？

跳表（Skip List）是一種基于鏈表的數據結構，它通過添加多層索引來加速搜索操作。

• 跳表中的數據是有序的。
• 跳表中的每個節點都包含一個指向下一層和右側節點的指針

跳表通過多層索引的方式來加速搜索操作。最底層是一個普通的有序鏈表，而上面的每一層都是前一層的子集，每個節點在上一層都有一個指針指向它在下一層的對應節點。這樣，在搜索時可以通過跳過一些節點，直接進入目標區域，從而減少搜索的時間復雜度。

跳表的平均搜索、插入和刪除操作的時間復雜度都為O(logN)，但空間復雜度稍高。跳表常用于需要高效搜索和插入操作的場景，如數據庫、緩存等。redis 用了跳表來實現 zset。

LRU是什么？如何實現？

LRU 是一種緩存淘汰算法，當緩存空間已滿時，優先淘汰最長時間未被訪問的數據。

實現的方式是哈希表+雙向鏈表結合。

• 使用哈希表存儲數據的鍵值對，鍵為緩存的鍵，值為對應的節點。
• 使用雙向鏈表存儲數據節點，鏈表頭部為最近訪問的節點，鏈表尾部為最久未訪問的節點。
• 當數據被訪問時，如果數據存在于緩存中，則將對應節點移動到鏈表頭部；如果數據不存在于緩存中，則將數據添加到緩存中，同時創建一個新節點并插入到鏈表頭部。
• 當緩存空間已滿時，需要淘汰最久未訪問的節點，即鏈表尾部的節點。

上面這種思想方式，LRU 算法可以在 O(1) 的時間復雜度內實現數據的插入、查找和刪除操作。

布隆過濾器怎么設計？時間復雜度？

「布隆過濾器」可以用來解決類似的問題，具有運行快速，內存占用小的特點，它是一個保存了很長的二級制向量，同時結合 Hash 函數實現的。

而高效插入和查詢的代價就是，它是一個基于概率的數據結構，只能告訴我們一個元素絕對不在集合內，對于存在集合內的元素有一定的誤判率。

• 初始化：當我們創建一個布隆過濾器時，我們首先創建一個全由0組成的位數組（bit array)。同時，我們還需選擇幾個獨立的哈希函數，每個函數都可以將集合中的元素映射到這個位數組的某個位置。
• 添加元素：在布隆過濾器中添加一個元素時，我們會將此元素通過所有的哈希函數進行映射，得到在位數組中的幾個位置，然后將這些位置標記為1。
• 查詢元素：如果我們要檢查一個元素是否在集合中，我們同樣使用這些哈希函數將元素映射到位數組中的幾個位置，如果所有的位置都被標記為1，那么我們就可以說該元素可能在集合中。如果有任何一個位置不為1，那么該元素肯定不在集合中。

排序算法

排序算法及空間復雜度

• 插入類排序：
  • 直接插入排序：將待排序元素逐個插入到已排序序列的合適位置，形成有序序列。
    • 時間復雜度：平均為O(N^{2)，最好情況下為O(N)，最壞情況下為O(N}2)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)。
    • 穩定性：穩定。
  • 折半插入排序：將排好元素一分為二來進行查找插入的位置。
    • 時間復雜度：平均為O(N^2)，最好情況下為O(NlogN)，最壞情況下為O(N2)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)。
    • 穩定性：穩定。
  • 希爾排序：將待排數組分成若干個稀疏的子序列，分別進行直接插入排序，使得稀疏的子序列較為有序，然后再全部進行次直接插入排序，即可完成。
    • 時間復雜度：業界統一認為為O(N^1.3)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)
    • 穩定性：不穩定。
• 交換類排序：
  • 冒泡排序：在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。
    • 時間復雜度：平均為O(N^{2)，最好情況下為O(N)，最壞情況下為O(N}2)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)。
    • 穩定性：穩定。
  • 快速排序：
    • 時間復雜度：平均為O(NlogN)，最好情況下為O(NlogN)，最壞情況下為O(N^2)。
    • 空間復雜度：使用遞歸進行深搜，所以為O(NlogN)。
    • 穩定性：不穩定。
• 選擇排序：
  • 簡單選擇排序：從第一個記錄開始，通過n-1次關鍵字比較，從n個記錄中選擇出關鍵字最小的記錄，并和第一個記錄進行比較。
    • 時間復雜度：平均為O(N^{2)，最好情況下為O(N}2)，最壞情況下為O(N^2)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)。
    • 穩定性：不穩定。
  • 堆排序：把待排序的數字看成一顆完全二叉樹的順序表示，每個結點表示一個記錄，第一個記錄作為二叉樹的根，對剩下的記錄依次逐層從左到右順序排序，（i從0開始）任意節點r[i]的左孩子是r[2r+1]，右孩子是r[2i+2]，雙親是r[(i+1)/2-1]。對這顆完全二叉樹進行調整。大根堆： r[i]>r[2i+1]且r[i]>r[2i+2]，也就是父節點大于孩子節點的完全二叉樹稱為大根堆。
    • 時間復雜度：平均為O(NlogN)，最好情況下為O(NlogN)，最壞情況下為O(NlogN)。
    • 空間復雜度：因為每回只移動一個所以空間復雜度為O(1)。
    • 穩定性：不穩定。