數(shù)據(jù)結(jié)構(gòu)靈魂拷問

復(fù)雜度分析

什么是大O復(fù)雜度表示法？

$T(n) = O(f(n))$

T(n)表示代碼執(zhí)行的時間沾谓；n 表示數(shù)據(jù)規(guī)模的大小戳鹅；f(n) 表示每行代碼執(zhí)行的次數(shù)總和。因為這是一個公式昏兆，所以用 f(n) 來表示枫虏。公式中的 O，表示代碼的執(zhí)行時間 T(n) 與 f(n) 表達(dá)式成正比爬虱。

順序執(zhí)行： $O(1)$
循環(huán)： $O(n)$
雙重循環(huán)： $O(n^2)$
循環(huán)中對循環(huán)次數(shù)條件進(jìn)行乘法計算的： $O(logn)$
```
   i=1;
   while (i <= n)  {
   i = i * 2;
   }
```
雙重循環(huán)中隶债，子循環(huán)對循環(huán)次數(shù)條件進(jìn)行乘法計算的： $O(nlogn)$

歸并排序、快速排序

什么是最好跑筝、最壞死讹、平均、均攤時間復(fù)雜度曲梗？

在循環(huán)體內(nèi)有判斷條件赞警，某些情況下執(zhí)行，某些情況下不執(zhí)行虏两。

最好時間復(fù)雜度：執(zhí)行次數(shù)最少的條件下的時間復(fù)雜度

最壞時間復(fù)雜度：執(zhí)行次數(shù)最多的條件下的時間復(fù)雜度愧旦。

平均時間復(fù)雜度：將執(zhí)行條件的每一種情況需要遍歷的次數(shù)乘上這種情況下發(fā)生的概率，也叫加權(quán)平均時間復(fù)雜度定罢。

均攤時間復(fù)雜度：使用攤還分析方法笤虫，將某一次的執(zhí)行情況平攤到每一次的執(zhí)行中，總體下來祖凫，得到算法的執(zhí)行次數(shù)琼蚯。比如某一特定情況下，執(zhí)行情況是 $O(n)$ ,其他情況都是 $O(1)$ ,那么平攤下來惠况，算法時間復(fù)雜度就是 $O(1)$

數(shù)組

如何優(yōu)化數(shù)組的插入和刪除操作遭庶？

一般情況下，插入和刪除會導(dǎo)致后續(xù)節(jié)點的移動售滤，導(dǎo)致復(fù)雜度為 $O(n)$ ,如何將其優(yōu)化為 $O(1)$

插入操作

如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律罚拟，數(shù)組只是被當(dāng)作一個存儲數(shù)據(jù)的集合台诗。

如果要將某個數(shù)據(jù)插入到第 k 個位置，為了避免大規(guī)模的數(shù)據(jù)搬移赐俗，我們還有一個簡單的辦法就是拉队，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個位置阻逮。

3f70b4ad9069ec568a2caaddc231b7dc.jpg

刪除操作

數(shù)組 a[10]中存儲了 8 個元素：a粱快，b，c叔扼，d事哭，e，f瓜富，g鳍咱，h。現(xiàn)在与柑，我們要依次刪除 a谤辜，b，c 三個元素价捧。

為了避免 d丑念，e，f结蟋，g脯倚，h 這幾個數(shù)據(jù)會被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)嵌屎。每次的刪除操作并不是真正地搬移數(shù)據(jù)推正，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲數(shù)據(jù)時编整，我們再觸發(fā)執(zhí)行一次真正的刪除操作舔稀，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

b69b8c5dbf6248649ddab7d3e7cfd7e5.jpg

什么時候使用數(shù)組掌测，什么時候使用容器(ArrayList)?

Java ArrayList 無法存儲基本類型内贮，比如 int、long汞斧，需要封裝為 Integer夜郁、Long 類，而 Autoboxing粘勒、Unboxing 則有一定的性能消耗竞端，所以如果特別關(guān)注性能，或者希望使用基本類型庙睡，就可以選用數(shù)組事富。
如果數(shù)據(jù)大小事先已知技俐，并且對數(shù)據(jù)的操作非常簡單，用不到 ArrayList 提供的大部分方法统台，也可以直接使用數(shù)組.
當(dāng)要表示多維數(shù)組時雕擂，用數(shù)組往往會更加直觀。比如 Object[][] array贱勃；而用容器的話則需要這樣定義：ArrayList <ArrayList<object>> array 井赌。

對于業(yè)務(wù)開發(fā)，直接使用容器就足夠了贵扰，省時省力仇穗。畢竟損耗一丟丟性能，完全不會影響到系統(tǒng)整體的性能戚绕。但如果你是做一些非常底層的開發(fā)纹坐，比如開發(fā)網(wǎng)絡(luò)框架，性能的優(yōu)化需要做到極致舞丛，這個時候數(shù)組就會優(yōu)于容器恰画，成為首選。

為什么大多數(shù)編程語言數(shù)組從0開始編號瓷马，而不是1？

程序訪問數(shù)組中的元素跨晴，使用尋址訪問欧聘，指針或引用指向的是數(shù)組中的首地址，通過計算尋址公式來得到第k個元素的地址端盆。

如果從0編號：

a[k]_address = base_address + k * type_size

如果從1編號：

a[k]_address = base_address + (k-1) * type_size

從1編號怀骤，每次訪問需要計算k-1，效率不如從0編號好
C 語言設(shè)計者用 0 開始計數(shù)數(shù)組下標(biāo)焕妙，之后的 Java蒋伦、JavaScript 等高級語言都效仿了 C 語言，習(xí)慣如此

鏈表焚鹊、隊列和棧

如何實現(xiàn)LRU緩存淘汰算法痕届？

緩存的大小有限，當(dāng)緩存被用滿時末患，哪些數(shù)據(jù)應(yīng)該被清理出去研叫，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來決定璧针。常見的策略有三種：先進(jìn)先出策略 FIFO（First In嚷炉，F(xiàn)irst Out）、最少使用策略 LFU（Least Frequently Used）探橱、最近最少使用策略 LRU（Least Recently Used）

維護(hù)一個有序單鏈表申屹，越靠近鏈表尾部的結(jié)點是越早之前訪問的绘证。當(dāng)有一個新的數(shù)據(jù)被訪問時，我們從鏈表頭開始順序遍歷鏈表哗讥。

如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了嚷那，我們遍歷得到這個數(shù)據(jù)對應(yīng)的結(jié)點，并將其從原來的位置刪除忌栅，然后再插入到鏈表的頭部车酣。
如果此數(shù)據(jù)沒有在緩存鏈表中，又可以分為兩種情況：
1. 如果此時緩存未滿索绪，則將此結(jié)點直接插入到鏈表的頭部湖员；
2. 如果此時緩存已滿，則鏈表尾結(jié)點刪除瑞驱，將新的數(shù)據(jù)結(jié)點插入鏈表的頭部娘摔。

如何實現(xiàn)瀏覽器的前進(jìn)和后退功能？

我們使用兩個棧唤反，X和Y凳寺，我們把首次瀏覽的頁面依次壓入棧X，當(dāng)點擊后退時彤侍，再依次從棧X中出棧肠缨，并將出棧的數(shù)據(jù)依次放入棧Y中。當(dāng)我們點擊前進(jìn)按鈕時盏阶，我們依次從棧Y中取出數(shù)據(jù)晒奕，放入棧X中。如果點擊其它頁面時名斟，將棧Y清空脑慧。

如何實現(xiàn)表達(dá)式求值？

比如 $3+5*8-6$

使用兩個棧來實現(xiàn)砰盐，一個放數(shù)字闷袒，一個放運(yùn)算符

我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字岩梳，我們就直接壓入操作數(shù)棧囊骤；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較蒋腮，如果比運(yùn)算符棧頂元素的優(yōu)先級低或者相同淘捡，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂依次取兩個操作數(shù)池摧，第一個在運(yùn)算符后焦除，第二個在運(yùn)算符前，然后進(jìn)行計算作彤，再把計算結(jié)果壓入操作數(shù)棧膘魄，繼續(xù)比較乌逐。

bc77c8d33375750f1700eb7778551600.jpg

如何實現(xiàn)括號匹配？

假設(shè)表達(dá)式中只包含三種括號创葡，圓括號 ()浙踢、方括號[]和花括號{}，并且它們可以任意嵌套灿渴。比如洛波，{[] ()[{}]}或[{()}([])]等都為合法格式牍帚，而{[}()]或[({)]為不合法的格式盐捷。那我現(xiàn)在給你一個包含三種括號的表達(dá)式字符串，如何檢查它是否合法呢

用棧來保存未匹配的左括號调鲸，從左到右依次掃描字符串棘幸，如果遇到左括號焰扳，入棧，如果遇到有括號误续，從棧頂取出一個元素進(jìn)行比較吨悍，如果能夠匹配，繼續(xù)掃描蹋嵌，直到結(jié)束育瓜。最后檢查棧是否為空，如果為空栽烂，則全部匹配爆雹，否則異常。

為什么函數(shù)調(diào)用要使用“椼倒模”來保存臨時變量呢，用其它數(shù)據(jù)結(jié)構(gòu)不可以嗎慧起？

函數(shù)調(diào)用中菇晃，變量的作用域很重要，先聲明的作用域更大蚓挤，后聲明的更小磺送，函數(shù)的調(diào)用結(jié)束，伴隨著出棧操作灿意，變量的使用就結(jié)束了估灿。

函數(shù)中，調(diào)用函數(shù)的關(guān)系滿足先進(jìn)后出缤剧，后進(jìn)先出原則馅袁，所以使用棧很合適。

循環(huán)隊列的判斷為滿的條件是什么荒辕？

(tail + 1) % n == head

3d81a44f8c42b3ceee55605f9aeedcec.jpg


public class CircularQueue {
  // 數(shù)組：items汗销，數(shù)組大杏贪：n
  private String[] items;
  private int n = 0;
  // head表示隊頭下標(biāo)，tail表示隊尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請一個大小為capacity的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊
  public boolean enqueue(String item) {
    // 隊列滿了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出隊
  public String dequeue() {
    // 如果head == tail 表示隊列為空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

什么是阻塞隊列弛针，什么是并發(fā)隊列叠骑？

阻塞隊列：在隊列基礎(chǔ)上增加了阻塞操作。簡單來說削茁，就是在隊列為空的時候宙枷，從隊頭取數(shù)據(jù)會被阻塞。因為此時還沒有數(shù)據(jù)可取茧跋，直到隊列中有了數(shù)據(jù)才能返回慰丛；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞厌衔，直到隊列中有空閑位置后再插入數(shù)據(jù)璧帝，然后再返回。

我們可以使用阻塞隊列富寿，輕松實現(xiàn)一個“生產(chǎn)者 - 消費(fèi)者模型”２橇ァ！页徐！
并發(fā)隊列：線程安全的隊列叫做并發(fā)隊列苏潜。最簡單直接的實現(xiàn)方式是直接在 enqueue()、dequeue() 方法上加鎖变勇，但是鎖粒度大并發(fā)度會比較低恤左，同一時刻僅允許一個存或者取操作。

實際上搀绣，基于數(shù)組的循環(huán)隊列飞袋，利用 CAS 原子操作，可以實現(xiàn)非常高效的并發(fā)隊列链患。這也是循環(huán)隊列比鏈?zhǔn)疥犃袘?yīng)用更加廣泛的原因巧鸭。

什么場景下會使用隊列？

線程池的池結(jié)構(gòu)使用隊列來排隊請求麻捻。
數(shù)據(jù)庫連接池纲仍，使用隊列連接數(shù)據(jù)庫操作。
消息隊列使用隊列來處理消息的發(fā)送和消費(fèi)贸毕。

如何實現(xiàn)無鎖的并發(fā)隊列郑叠？

使用CAS實現(xiàn)無鎖隊列，在入隊前明棍，獲取tail位置乡革，入隊時比較tail是否發(fā)生變化，如果否，則允許入隊署拟，反之婉宰，本次入隊失敗。出隊則是獲取head位置推穷，進(jìn)行cas心包。

遞歸

使用遞歸算法的條件是什么？

一個A問題可以被分解為不確定的子問題B馒铃、C蟹腾、D等
這個問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同区宇，求解思路完全一樣
存在遞歸終止條件

使用遞歸算法可能會產(chǎn)生什么問題娃殖？

堆棧溢出

函數(shù)調(diào)用會使用棧來保存臨時變量。每調(diào)用一個函數(shù)议谷，都會將臨時變量封裝為棧幀壓入內(nèi)存棧炉爆，等函數(shù)執(zhí)行完成返回時，才出棧卧晓。系統(tǒng)椃沂祝或者虛擬機(jī)棧空間一般都不大逼裆。如果遞歸求解的數(shù)據(jù)規(guī)模很大郁稍，調(diào)用層次很深，一直壓入棧胜宇，就會有堆棧溢出的風(fēng)險耀怜。

重復(fù)值計算

在處理 $f(n) = f(n-1)+f(n-2)$ 的遞歸情況時，會出現(xiàn)以下情況

e7e778994e90265344f6ac9da39e01bf.jpg

從圖中桐愉，我們可以直觀地看到财破，想要計算 f(5)，需要先計算 f(4) 和 f(3)从诲，而計算 f(4) 還需要計算 f(3)狈究，因此，f(3) 就被計算了很多次盏求，這就是重復(fù)計算問題。為了避免重復(fù)計算亿眠，我們可以通過一個數(shù)據(jù)結(jié)構(gòu)（比如散列表）來保存已經(jīng)求解過的 f(k)碎罚。當(dāng)遞歸調(diào)用到 f(k) 時，先看下是否已經(jīng)求解過了纳像。如果是荆烈，則直接從散列表中取值返回，不需要重復(fù)計算，這樣就能避免剛講的問題了憔购。