最近不是跳槽季嘛，今兒我就來分享一道我之前遇到的筆試題(上機寫代碼，這裡統稱筆試)，這道題遇到的幾率還是比較高的。
很多人可能準備去一波阿裡或者其他大廠，而這些大廠面試過程一般都會有筆試。
不過有很多人可能沒經曆過筆試，是以我先分享一下我之前去面螞蟻金服時候的筆試經曆。
一般沒特意去練練是真的不習慣的。
1
當時我在經曆了 1 個多小時的 BB 之後，面試官就讓我打開郵箱，會有這麼一條郵件。
郵件裡面有網址，打開網址之後，出來的就是這樣的界面：
當然現在截圖上是沒題目的，但真正面試的時候界面上就能看到面試官已經給你準備好的題目。
我當時的題目是實作個 LRU，面試官給了接口的定義，然後一些使用方法，以及一些注釋說明（下文會有具體題目）。
一般而言，看個注釋和使用方式就可以得知要實作什麼東西了。
這裡要注意，不了解題目的要問清楚，不要自己瞎了解，不然咱就漸行漸遠了。
還有一點要注意，這裡寫代碼是不會聯想的，是不會聯想的，是不會聯想的。
是以所有的類名、方法名都得你一個字母一個字母的敲。
這對于習慣用 IDE 的我們來說，是個緻命打擊。
你可以試試看看優先隊列、鎖這些類名能不能敲出來。
其實這些名字還好，打個八九不離十也差不多了，就是一些方法名想不起來就很蛋疼，是以一些常用的還是得注意一下。
如果你實在敲不出來，次一級做法就是和面試官說你得在 idea 裡面打。
我之前問過一位在螞蟻的小姐姐，她說最好是在網頁上敲了，網頁上敲的話基本上隻會看邏輯，不會運作，也不會扣的太細。
如果你拷到 idea 上寫的話，那面試官估計得把你代碼要拷下來運一運，而且可能會問的比較細。
畢竟網頁上寫代碼，面試官是能實時看到的，idea 可看不到。
基本上就是這個樣子了，我當時在網頁上寫的，面試官順着邏輯看一遍就 ok 了。
2
再說下筆試的小技巧。
我推薦先和面試官說我能在紙上畫畫嗎？
答案肯定是能。
然後在紙上畫畫圖，理一理思路，然後把思路講出來給面試官聽，得到一些回報。
畢竟面試是要交流的。
思路得到認可了，那就大膽的寫呗，就怕一開始思路就是錯的，然後埋頭寫。
或者沒一點思路，埋着頭，像線程被阻塞一樣。
要注意交流。
至于題目的話，推薦自頂向下的寫。
舉個經典的例子：排序裡面數組交換資料。
int temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
這種一般都會封裝成 swap 方法 書寫的時候就直接先寫個 swap 方法，當做已經實作了邏輯，然後之後再補上實作。
這樣思路先沿着主線執行完，然後再去完成支線，在面試場景尤為重要，畢竟那時候是緊張的。
這個 swap 可能太簡單的感受不到，看看下面的題就能感受到了。
3
回到我之前的那個筆試題，LRU。
至于 LRU 是什麼我就不提了，不明白的同學自行查閱下，我們直接看題目。
public class LRUCache<K, V> {
public LRUCache() {
}
public V get(K k) {
}
public void put(K k, V v) {
}
} 當時面試官給的就這麼個類，幾個未實作的方法，還有個 main 方法我就沒寫了，就是使用例子。
現在你可以停下，思考下，你看看這樣你能寫的出來不？
好了，我貼下答案，這題 LeetCode 上也有的，第 146 題，可以去練練。
public class LRUCache<K,V> {
class Node<K,V> {
K key;
V value;
Node<K,V> prev, next;
public Node(){}
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private HashMap<K,Node> map;
private Node<K,V> head;
private Node<K,V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity);
head = new Node<>();
tail = new Node<>();
head.next = tail;
tail.prev = head;
}
public V get(K key) {
Node<K,V> node = map.get(key);
if (node == null) {
return null;
}
moveNodeToHead(node);
return node.value;
}
public void put(K key, V value) {
Node<K,V> node = map.get(key);
if (node == null) {
if (map.size() >= capacity) {
map.remove(tail.prev.key);
removeTailNode();
}
Node<K,V> newNode = new Node<>(key, value);
map.put(key, newNode);
addToHead(newNode);
} else {
node.value = value;
moveNodeToHead(node);
}
}
private void addToHead(Node<K,V> newNode) {
newNode.prev = head;
newNode.next = head.next;
head.next.prev = newNode;
head.next = newNode;
}
private void moveNodeToHead(Node<K,V> node) {
removeNode(node);
addToHead(node);
}
private void removeNode(Node<K,V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void removeTailNode() {
removeNode(tail.prev);
}
public static void main(String[] args) {
LRUCache<Integer,Integer> lruCache = new LRUCache<>(3);
lruCache.put(1,1);
lruCache.put(2,2);
lruCache.put(3,3);
lruCache.get(1);
lruCache.put(4,4);
System.out.println(lruCache); // toString 我就沒貼了，代碼太長了
}
} 這個題目就适合我上面說的自頂向下了。
addToHead、moveNodeToHead、removeNode這幾個我建議在主流程寫完之前不要實作，把 get、put 寫完之後，再實作邏輯，這樣比較清晰，也不會亂。
這種，我稱之為自頂向下或者 BFS 寫法。
LRU還有一種取巧的實作，就是利用LinkedHashMap，繼承實作removeEldestEntry方法，這種很簡單，不過面試官不會讓你用這種的，因為我當時提了哈哈哈。
連結清單類題目或者二叉樹之類的在紙上畫畫，還是比較容易的。
-END-