從 LRU Cache 帶你看面試的本質(zhì)

前言

在講這道題之前，我想先聊聊「技術(shù)面試究竟是在考什么」這個(gè)問(wèn)題。

技術(shù)面試究竟在考什么

在人人都知道刷題的今天，面試官也都知道大家會(huì)刷題準(zhǔn)備面試，代碼大家都會(huì)寫，那面試為什么還在考這些題？那為什么有些人代碼寫出來(lái)了還掛了？

大家知道美國(guó)的大廠面試 80%是在考算法，這其實(shí)是最近 5-10 年以谷歌、雅虎為首才興起的；國(guó)內(nèi)大廠對(duì)于算法的考察雖然沒(méi)有這么狂熱，但也越來(lái)越重視了。

那么算法面試真的只是在考算法嗎？顯然不是。本質(zhì)上考的是思考問(wèn)題的方式，分析、解決問(wèn)題的能力，以及和同事溝通交流的能力，看你能否主動(dòng)推進(jìn)去解決問(wèn)題。

答題思路

套路就是：

• clarify 問(wèn)題
• 分析思路、時(shí)空復(fù)雜度、分析哪里可以優(yōu)化、如何優(yōu)化
• 寫代碼
• run test cases

雖說(shuō)是套路，但何嘗不是一個(gè)高效的工作方式？

那拿到一個(gè)問(wèn)題，首先應(yīng)該是去 clarify 這個(gè)問(wèn)題，因?yàn)楣ぷ骶褪侨绱耍幌裨谒㈩}網(wǎng)站做題什么都給你定義好了，面試官通常都不會(huì)一次性給你所有條件，而是需要你思考之后去問(wèn)他。那通過(guò)這個(gè)環(huán)節(jié)，面試官就知道了你遇到問(wèn)題是怎么去思考的，你考慮的是否全面，怎么去和別人溝通的，今后和你一起工作的狀態(tài)是怎樣的。

就像我們平時(shí)工作時(shí)，需要和 product manager 不斷的 clarify 需求，特別是沒(méi)定義清楚的部分，反反復(fù)復(fù)的討論，也是磨刀不誤砍柴工。那這個(gè)過(guò)程，在我司可能就要 1-2 周，不會(huì)很著急的就開始，否則努力錯(cuò)了方向就是南轅北轍，得不償失。那么面試時(shí)也是一樣，代碼都寫完了面試官說(shuō)這不是我想問(wèn)的，那時(shí)候已經(jīng)沒(méi)時(shí)間了，買單的是我們自己。

第二點(diǎn)分析思路就是重中之重了，也是本文的核心，會(huì)以 LRU Cache 這到經(jīng)典題為例，展示我是如何思考、分析的。

第三點(diǎn)寫代碼，沒(méi)什么好說(shuō)的，終究是需要落到實(shí)處的。

第四點(diǎn)跑測(cè)試，很多同學(xué)可能會(huì)忘，所以如果你能主動(dòng)提出 run test cases，過(guò)幾個(gè)例子檢驗(yàn)一下，是很好的。

• 一來(lái)是給自己一個(gè)修正的機(jī)會(huì)，因?yàn)橛泻芏?bug 是你跑兩個(gè)例子就能發(fā)現(xiàn)的，那即使有點(diǎn) bug 你沒(méi)發(fā)現(xiàn)，只要你做完了這一步，面試官當(dāng)場(chǎng)也沒(méi)發(fā)現(xiàn)的話，那面試結(jié)束后面試官雖然會(huì)拍照留念，但也不會(huì)閑的無(wú)聊再自己打到電腦上跑的；
• 二來(lái)是展示你的這種意識(shí)，跑測(cè)試的意識(shí)，這種意識(shí)是很重要的。

有些人說(shuō)每道題我都做出來(lái)了，為什么還是掛了？那照著這四點(diǎn)對(duì)比一下，看看是哪個(gè)環(huán)節(jié)出了問(wèn)題。

常考不衰的原因

另外這道題為什么各大公司都喜歡考呢？

一是因?yàn)樗軌?span style="color:blue;">多方面、多維度的考察 candidate：這道題考察的是基本功，考對(duì)數(shù)據(jù)結(jié)構(gòu)理解使用，考能不能寫出 readable 的代碼。一場(chǎng) 45 分鐘-60 分鐘的面試，如何摸清楚 candidate 的真實(shí)水平，也是不容易的啊。

二是因?yàn)?span style="color:blue;">這道題可難可易，可以簡(jiǎn)單到像 Leetcode 上那樣把 API 什么的都已經(jīng)定義好了，也可以難到把 System Design 的內(nèi)容都包含進(jìn)來(lái)，聊一下 Redis 中的近似 LRU 算法。

所以 follow up 就可以無(wú)限的深入下去，如果面試官想問(wèn)的你都能回答的頭頭是道，那 strong hire 自然跑不掉。那有些同學(xué)只會(huì)到第一層或者第二層，面試是優(yōu)中選優(yōu)的過(guò)程，其他同學(xué)會(huì)的比你多，溝通交流能力又好，自然就是別人拿 offer 了。

那今天就以這道題為例，在這里淺談一下我的思考過(guò)程，為大家拋磚引玉，歡迎在留言區(qū)分享你的想法。

LRU Cache

LRU 是什么

LRU = Least Recently Used 最近最少使用
它是一種緩存逐出策略 cache eviction policies^[1]

LRU 算法是假設(shè)最近最少使用的那些信息，將來(lái)被使用的概率也不大，所以在容量有限的情況下，就可以把這些不常用的信息踢出去，騰地方。

比如有熱點(diǎn)新聞時(shí)，所有人都在搜索這個(gè)信息，那剛被一個(gè)人搜過(guò)的信息接下來(lái)被其他人搜索的概率也大，就比前兩天的一個(gè)過(guò)時(shí)的新聞被搜索的概率大，所以我們把很久沒(méi)有用過(guò)的信息踢出去，也就是 Least Recently Used 的信息被踢出去。

舉個(gè)例子：我們的內(nèi)存容量為 5，現(xiàn)在有 1-5 五個(gè)數(shù)。

我們現(xiàn)在想加入一個(gè)新的數(shù)：6
可是容量已經(jīng)滿了，所以需要踢出去一個(gè)。

那按照什么規(guī)則踢出去，就有了這個(gè)緩存逐出策略。比如：

• FIFO (First In First Out) 這個(gè)就是普通的先進(jìn)先出。
• LFU (Least Frequently Used) 這個(gè)是計(jì)算每個(gè)信息的訪問(wèn)次數(shù)，踢走訪問(wèn)次數(shù)最少的那個(gè)；如果訪問(wèn)次數(shù)一樣，就踢走好久沒(méi)用過(guò)的那個(gè)。這個(gè)算法其實(shí)很高效，但是耗資源，所以一般不用。
• LRU (Least Recently Used) 這是目前最常用了。

LRU 的規(guī)則是把很長(zhǎng)時(shí)間沒(méi)有用過(guò)的踢出去，那它的隱含假設(shè)就是，認(rèn)為最近用到的信息以后用到的概率會(huì)更大。

那我們這個(gè)例子中就是把最老的 1 踢出去，變成：

不斷迭代...

Cache 是什么？

簡(jiǎn)單理解就是：把一些可以重復(fù)使用的信息存起來(lái)，以便之后需要時(shí)可以快速拿到。

那至于它存在哪里就不一定了，最常見的是存在內(nèi)存里，也就是 memory cache，但也可以不存在內(nèi)存里。

使用場(chǎng)景就更多了，比如 Spring 中有 @Cacheable 等支持 Cache 的一系列注解。上個(gè)月我在工作中就用到了這個(gè) annotation，當(dāng)然是我司包裝過(guò)的，大大減少了 call 某服務(wù)器的次數(shù)，解決了一個(gè)性能上的問(wèn)題。

再比如，在進(jìn)行數(shù)據(jù)庫(kù)查詢的時(shí)候，不想每次請(qǐng)求都去 call 數(shù)據(jù)庫(kù)，那我們就在內(nèi)存里存一些常用的數(shù)據(jù)，來(lái)提高訪問(wèn)性能。

這種設(shè)計(jì)思想其實(shí)是遵循了著名的“二八定律”。在讀寫數(shù)據(jù)庫(kù)時(shí)，每次的 I/O 過(guò)程消耗很大，但其實(shí) 80% 的 request 都是在用那 20% 的數(shù)據(jù)，所以把這 20% 的數(shù)據(jù)放在內(nèi)存里，就能夠極大的提高整體的效率。

總之，Cache 的目的是存一些可以復(fù)用的信息，方便將來(lái)的請(qǐng)求快速獲得。

LRU Cache

那我們知道了 LRU，了解了 Cache，合起來(lái)就是 LRU Cache 了：

當(dāng) Cache 儲(chǔ)存滿了的時(shí)候，使用 LRU 算法把老家伙清理出去。

思路詳解

說(shuō)了這么多，Let's get to the meat of the problem!

這道經(jīng)典題大家都知道是要用 HashMap + Doubly Linked List，或者說(shuō)用 Java 中現(xiàn)成的 LinkedHashMap，但是，為什么？你是怎么想到用這兩個(gè)數(shù)據(jù)結(jié)構(gòu)的？面試的時(shí)候不講清楚這個(gè)，不說(shuō)清楚思考過(guò)程，代碼寫對(duì)了也沒(méi)用。

和在工作中的設(shè)計(jì)思路類似，沒(méi)有人會(huì)告訴我們要用什么數(shù)據(jù)結(jié)構(gòu)，一般的思路是先想有哪些 operations，然后根據(jù)這些操作，再去看哪些數(shù)據(jù)結(jié)構(gòu)合適。

分析 Operations

那我們來(lái)分析一下對(duì)于這個(gè) LRU Cache 需要有哪些操作：

1. 首先最基本的操作就是能夠從里面讀信息，不然之后快速獲取是咋來(lái)的；
2. 那還得能加入新的信息，新的信息進(jìn)來(lái)就是 most recently used 了；
3. 在加新信息之前，還得看看有沒(méi)有空位，如果沒(méi)有空間了，得先把老的踢出去，那就需要能夠找到那個(gè)老家伙并且刪除它；
4. 那如果加入的新信息是緩存里已經(jīng)有的，那意思就是 key 已經(jīng)有了，要更新 value，那就只需要調(diào)整一下這條信息的 priority，它已經(jīng)從上一次被使用升級(jí)為最新使用的了。

找尋數(shù)據(jù)結(jié)構(gòu)

那第一個(gè)操作很明顯，我們需要一個(gè)能夠快速查找的數(shù)據(jù)結(jié)構(gòu)，非 HashMap 莫屬，還不了解 HashMap 原理和設(shè)計(jì)規(guī)則的在公眾號(hào)內(nèi)發(fā)消息「HashMap」，送你一篇爆款文章；

可是后面的操作 HashMap 就不頂用了呀。。。

來(lái)來(lái)來(lái)，我們來(lái)數(shù)一遍基本的數(shù)據(jù)結(jié)構(gòu)：
Array, LinkedList, Stack, Queue, Tree, BST, Heap, HashMap

在做這種數(shù)據(jù)結(jié)構(gòu)的題目時(shí)，就這樣把所有的數(shù)據(jù)結(jié)構(gòu)列出來(lái)，一個(gè)個(gè)來(lái)分析，有時(shí)候不是因?yàn)檫@個(gè)數(shù)據(jù)結(jié)構(gòu)不行，而是因?yàn)槠渌臄?shù)據(jù)結(jié)構(gòu)更好。

怎么叫更好？忘了我們的衡量標(biāo)準(zhǔn)嘛！時(shí)空復(fù)雜度，趕緊復(fù)習(xí)遞歸那篇文章，公眾號(hào)內(nèi)回復(fù)「遞歸」即可獲得。

那我們的分析如下：

Array, Stack, Queue 這三種本質(zhì)上都是 Array 實(shí)現(xiàn)的（當(dāng)然 Stack, Queue 也可以用 LinkedList 來(lái)實(shí)現(xiàn)。。），一會(huì)插入新的，一會(huì)刪除老的，一會(huì)調(diào)整下順序，array 不是不能做，就是得 O(n) 啊，用不起。

BST 同理，時(shí)間復(fù)雜度是 O(logn).

Heap 即便可以，也是 O(logn).

LinkedList，有點(diǎn)可以哦，按照從老到新的順序，排排站，刪除、插入、移動(dòng)，都可以是 O(1) 的誒！但是刪除時(shí)我還需要一個(gè) previous pointer 才能刪掉，所以我需要一個(gè) Doubly LinkedList.

那么我們的數(shù)據(jù)結(jié)構(gòu)敲定為：
HashMap + Doubly LinkedList

定義清楚數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

選好了數(shù)據(jù)結(jié)構(gòu)之后，還需要定義清楚每個(gè)數(shù)據(jù)結(jié)構(gòu)具體存儲(chǔ)的是是什么，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是如何聯(lián)系的，這才是核心問(wèn)題。

我們先想個(gè)場(chǎng)景，在搜索引擎里，你輸入問(wèn)題 Questions，谷歌給你返回答案 Answer。

那我們就先假設(shè)這兩個(gè)數(shù)據(jù)結(jié)構(gòu)存的都是 <Q, A>，然后來(lái)看這些操作，如果都很順利，那沒(méi)問(wèn)題，如果有問(wèn)題，我們?cè)僬{(diào)整。

那現(xiàn)在我們的 HashMap 和 LinkedList 長(zhǎng)這樣：

然后我們回頭來(lái)看這四種操作：

操作 1，沒(méi)問(wèn)題，直接從 HashMap 里讀取 Answer 即可，O(1)；

操作 2，新加入一組 Q&A，兩個(gè)數(shù)據(jù)結(jié)構(gòu)都得加，那先要判斷一下當(dāng)前的緩存里有沒(méi)有這個(gè) Q，那我們用 HashMap 判斷，

• 如果沒(méi)有這個(gè) Q，加進(jìn)來(lái)，都沒(méi)問(wèn)題；
• 如果已經(jīng)有這個(gè) Q，HashMap 這里要更新一下 Answer，然后我們還要把 LinkedList 的那個(gè) node 移動(dòng)到最后或者最前，因?yàn)樗兂闪俗钚卤皇褂玫牧寺铩?

可是，怎么找 LinkedList 的這個(gè) node 呢？一個(gè)個(gè) traverse 去找并不是我們想要的，因?yàn)橐?O(n) 的時(shí)間嘛，我們想用 O(1) 的時(shí)間操作。

那也就是說(shuō)這樣記錄是不行的，還需要記錄 LinkedList 中每個(gè) ListNode 的位置，這就是本題關(guān)鍵所在。

那自然是在 HashMap 里記錄 ListNode 的位置這個(gè)信息了，也就是存一下每個(gè) ListNode 的 reference。

想想其實(shí)也是，HashMap 里沒(méi)有必要記錄 Answer，Answer 只需要在 LinkedList 里記錄就可以了。

之后我們更新、移動(dòng)每個(gè) node 時(shí)，它的 reference 也不需要變，所以 HashMap 也不用改動(dòng)，動(dòng)的只是 previous, next pointer.

那再一想，其實(shí) LinkedList 里也沒(méi)必要記錄 Question，反正 HashMap 里有。

這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是相互配合來(lái)用的，不需要記錄一樣的信息。

更新后的數(shù)據(jù)結(jié)構(gòu)如下：

這樣，我們才分析出來(lái)用什么數(shù)據(jù)結(jié)構(gòu)，每個(gè)數(shù)據(jù)結(jié)構(gòu)里存的是什么，物理意義是什么。

那其實(shí)，Java 中的 LinkedHashMap 已經(jīng)做了很好的實(shí)現(xiàn)。但是，即便面試時(shí)可以使用它，也是這么一步步推導(dǎo)出來(lái)的，而不是一看到題目就知道用它，那一看就是背答案啊。

有同學(xué)問(wèn)我，如果面試官問(wèn)我這題做沒(méi)做過(guò)，該怎么回答？

答：實(shí)話實(shí)說(shuō)。

真誠(chéng)在面試、工作中都是很重要的，所以實(shí)話實(shí)說(shuō)就好了。但如果面試官?zèng)]問(wèn)，就不必說(shuō)。。。

其實(shí)面試官是不 care 你做沒(méi)做過(guò)這道題的，因?yàn)榇蠹叶妓㈩}，基本都做過(guò)，問(wèn)這個(gè)問(wèn)題沒(méi)有意義。只要你能把問(wèn)題分析清楚，講清楚邏輯，做過(guò)了又怎樣？很多做過(guò)了題的人是講不清楚的。。。

總結(jié)

那我們?cè)倏偨Y(jié)一下那四點(diǎn)操作：

第一個(gè)操作，也就是 get() API，沒(méi)啥好說(shuō)的；

二三四，是 put() API，有點(diǎn)小麻煩：

畫圖的時(shí)候邊講邊寫，每一步都從 high level 到 detail 再到代碼，把代碼模塊化。

• 比如“Welcome”是要把這個(gè)新的信息加入到 HashMap 和 LinkedList 里，那我會(huì)用一個(gè)單獨(dú)的 add() method 來(lái)寫這塊內(nèi)容，那在下面的代碼里我取名為 appendHead()，更精準(zhǔn)；
• “踢走老的”這里我也是用一個(gè)單獨(dú)的 remove() method 來(lái)寫的。

當(dāng)年我把這圖畫出來(lái)，面試官就沒(méi)讓我寫代碼了，直接下一題了...

那如果面試官還讓你寫，就寫唄。。。

class LRUCache {
  // HashMap: <key = Question, value = ListNode>
  // LinkedList: <Answer>

  public static class Node {
      int key;
      int val;
      Node next;
      Node prev;
      public Node(int key, int val) {
          this.key = key;
          this.val = val;
      }
  }

  Map<Integer, Node> map = new HashMap<>();
  private Node head;
  private Node tail;
  private int cap;

  public LRUCache(int capacity) {
      cap = capacity;
  }

  public int get(int key) {
      Node node = map.get(key);
      if(node == null) {
          return -1;
      } else {
          int res = node.val;
          remove(node);
          appendHead(node);
          return res;
      }
  }

  public void put(int key, int value) {
      // 先 check 有沒(méi)有這個(gè) key
      Node node = map.get(key);
      if(node != null) {
          node.val = value;
          // 把這個(gè)node放在最前面去
          remove(node);
          appendHead(node);
      } else {
          node = new Node(key, value);
          if(map.size() < cap) {
              appendHead(node);
              map.put(key, node);
          } else {
              // 踢走老的
              map.remove(tail.key);
              remove(tail);
              appendHead(node);
              map.put(key, node);
          }
      }
  }

  private void appendHead(Node node) {
      if(head == null) {
          head = tail = node;
      } else {
          node.next = head;
          head.prev = node;
          head = node;
      }
  }

  private void remove(Node node) {
      // 這里我寫的可能不是最 elegant 的，但是是很 readable 的
      if(head == tail) {
          head = tail = null;
      } else {
          if(head == node) {
              head = head.next;
              node.next = null;
          } else if (tail == node) {
              tail = tail.prev;
              tail.next = null;
              node.prev = null;
          } else {
              node.prev.next = node.next;
              node.next.prev = node.prev;
              node.prev = null;
              node.next = null;
          }
      }
  }


}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

總結(jié)

那再回到面試上來(lái)，為什么很多面試是以算法考察為主的？這樣的面試道理何在？算法題面試真的能衡量一個(gè)人的工作能力嗎？（當(dāng)然了，對(duì)于有些工作經(jīng)驗(yàn)的人還會(huì)考察系統(tǒng)設(shè)計(jì)方面的內(nèi)容。）

這是我一直在思考的問(wèn)題，工作之后愈發(fā)覺(jué)得，這樣的面試真的是有效的。

因?yàn)槲覀冃枰氖悄軌?strong>去解決未知的問(wèn)題的能力，知識(shí)可能會(huì)被遺忘，但是思考問(wèn)題的方式方法是一直跟隨著我們的，也是我們需要不斷提高的。那么在基本功扎實(shí)的前提下，有正確的方法和思路做指引，nothing is impossible.