首先感謝熱心助人的崔同學(xué)侮东，耐心給我講解猿題庫的面試風(fēng)格圈盔，讓我能安心只準(zhǔn)備了算法和system design。不過算法也沒準(zhǔn)備悄雅，最近正常刷題而已驱敲；system design也只是復(fù)習(xí)了下搜狗的項目。相當(dāng)于是裸面了宽闲。众眨。。萬幸其他方面一點都沒有問容诬，最后也拿到了實習(xí)offer娩梨。

一面

一面的面試官看起來不到30，應(yīng)該是普通研發(fā)览徒，當(dāng)然很可能是準(zhǔn)mentor狈定。進(jìn)屋介紹了下面試流程和公司，然后讓我問問題习蓬。我覺得過不過都沒準(zhǔn)呢有什么好問的纽什，所以接話茬問了幾個面試流程相關(guān)的問題。

算法

都說猿題庫主要考算法躲叼，我以為是暴力的上來就寫題芦缰，這面試官不錯，先讓我自我介紹放松了一下押赊，然后就說饺藤，“我們寫個題吧”包斑。

鏈表流礁，交換兩元素

給定一個單鏈表的頭結(jié)點head，兩個值v1罗丰、v2神帅，在鏈表中找到這兩個結(jié)點并交換。

跟面試官確定的信息：

• 有無prev
• Node的結(jié)構(gòu)（val萌抵，next）
• 返回值

題目很簡單找御，那很可能在考察邊界條件和coding style；算法方面cc大神說的好绍填，鏈表靠畫圖霎桅；交換數(shù)組需要記錄前置節(jié)點，給頭結(jié)點增加前置節(jié)點dummyNode讨永，簡化代碼滔驶，也簡化邊界條件。

剛要寫卿闹，面試官就攔住我揭糕，跟我說可以先聊聊思路萝快，能先動嘴皮我萬分感謝啊，著角，揪漩，“邊界條件先不管，算法的主要過程是……”吏口。面試官肯定之后才讓我寫代碼奄容。

算法很簡單，直接看代碼吧：

// define of Node(val, next)
public Node swap(Node head, int v1, int v2) {
  // no need to swap
  if (head == null || head.next == null) {
    return head;
  }
  // no need to swap
  if (v1 == v2) {
    return head;
  }
  
  Node dummy = new Node(0, head);
  Node prev1 = dummy;
  Node prev2 = dummy;
  Node prev = dummy;
  while (prev.next != null) {
    if (prev.next.val == v1) {
      prev1 = prev;
    }
    if (prev.next.val == v2) {
      prev2 = prev;
    }
  }
  
  // no need to swap
  if (prev1 == dummmy || prev2 == dummmy) {
    return head;
  }
  
  internalSwap(prev1, prev2);
  return dummy.next;
}

private void internalSwap(Node prev1, Node prev2) {
  if (prev1.next == prev2) {
    internalSwapNextTwo(prev1);
    return;
  }
  if (prev2.next == prev1) {
    internalSwapNextTwo(prev2);
    return;
  }
  
  Node next1 = prev1.next;
  Node next2 = prev2.next;
  prev1.next = next2;
  prev2.next = next1;
  Node tmp = next1.next;
  next1.next = next2.next;
  next2.next = tmp;
  return;
}

private void internalSwapNextTwo(Node first) {
  Node second = first.next;
  Node third = second.next;
  second.next = third.next;
  third.next = second;
  first.next = third;
  return;
}

寫完代碼产徊，面試也是先讓我拿著代碼講講思路嫩海。這部分主要是免去面試官硬讀代碼的麻煩，也方便面試官考察你代碼的模塊性囚痴，甚至一些變量叁怪、函數(shù)的命名。算法主體剛才講過深滚，于是我一句話帶過奕谭，重點講了swap方法中的邊界條件，然后面試官就開始自己看代碼痴荐。之后又讓我講internalSwap方法的原理血柳，我也是先講算法主體，再講邊界條件生兆。

矩陣旋轉(zhuǎn)

面試官說這個題很常見难捌，但是我只聽說過，鸦难，根吁，后悔自己當(dāng)時沒看。

給定一個n*n的矩陣合蔽，元素為整數(shù)击敌，將矩陣旋轉(zhuǎn)。

跟面試官確定的信息：

• 是按照旋轉(zhuǎn)后的順序輸出矩陣元素即可拴事，還是要改變原來的矩陣
• 返回值

我只知道有矩陣旋轉(zhuǎn)這道題沃斤，所以剛聽完題目的我是懵逼的。那沒辦法刃宵，只能硬著頭皮上衡瓶。

這道題我開始沒溝通好，沒有問返回值牲证，以為只要按照旋轉(zhuǎn)后的順序輸出矩陣元素即可（控制循環(huán)順序）哮针。說完思路，面試官意識到我理解錯了題意，耐心告訴我要返回一個矩陣诚撵。但也沒有急著否定我的方法缭裆，而是問我這種方法的時間復(fù)雜度和空間復(fù)雜度。那就都是O(n^2)了寿烟，面試官就說也可以改變原來的矩陣澈驼，降低空間復(fù)雜度。

我想了一會筛武，想到reverse操作一般是O(1)的缝其，而且經(jīng)常能通過各種reverse的組合達(dá)到神奇的效果。于是就想著先按照斜主對角線reverse一下徘六，也就是斜翻——還差點内边；再按照豎中軸線reverse一下，也就是對翻待锈，握草正好搞定漠其。

我用3*3的矩陣跟面試官說了思路后，面試官又讓我實驗4*4的矩陣竿音，和屎，，我以為有問題春瞬，結(jié)果畫完發(fā)現(xiàn)是正確的柴信。面試官就說，“恩宽气，實驗了也對吧随常。這其實是個數(shù)學(xué)問題，跟矩陣的性質(zhì)有關(guān)萄涯，你能不能證明一下绪氛？”我大學(xué)線代課都是睡過去的，跟面試管坦誠線代真的忘光了窃判，于是就直接讓我寫代碼了钞楼。

代碼：

public int[][] transfer(int[][] matrix) {
  if (matrix == null || matrix.length <= 1) {
    return matrix;
  }
  if (matrix[0] == null || matrix[0].length <= 1) {
    return matrix;
  }
  
  xiefan(matrix);
  duifan(matrix);
  return matrix;
}

private void xiefan(int[][] matrix) {
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < i; j++) {
      swap(matrix, i, j, j, i);
    }
  }
}

private void duifan(int[][] matrix) {
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length / 2; j++) {
      swap(matrix, i, j, i, matrix[0].length - 1 - j);
    }
  }
}

private swap(int[][] matrix, int x1, int y1, int x2, int y2) {
  int tmp = matrix[x1][y1];
  matrix[x1][y1] = matrix[x2][y2];
  matrix[x2][y2] = matrix[x1][y1];
}

后面的過程跟上一題一樣，分析時間復(fù)雜度與空間復(fù)雜度等袄琳。

網(wǎng)上更流行的解法是直接旋轉(zhuǎn)一圈，我面試時也想到了燃乍，不過覺得不好推導(dǎo)唆樊，沒有reverse的性質(zhì)通用。不過我覺得需要掌握這種用法刻蟹，也不用硬記逗旁，看過一遍key point，面試時很快能推出來。參考LeetCode：Rotate Image的解法2片效。

簡單聊項目

兩道算法題之后红伦，時間就差不多了，面試官讓我介紹下我在搜狗最滿意的一個項目淀衣，我回答的非常亂昙读，還好這次主要不是面試system design。然后面試官讓我等一下二面就走了膨桥，我趕緊復(fù)習(xí)之前整理的項目介紹蛮浑。

二面

二面的面試官，只嚣，沮稚，確實很帥，讓我想起了去年9月份在nice的面試册舞，不過面到一半去開會了蕴掏，讓我等20分鐘，调鲸，囚似，結(jié)果我等了一個小時。中間還有更尷尬的事情线得，不過這不重要饶唤，也不是人家故意的，面試最重要贯钩。

本來是先考system design募狂，再考算法，不過system design考到一半面試官就去開會了角雷，丟給我一道算法題祸穷，開完會也是先講的算法題，所以這里先介紹算法部分勺三。

算法

非遞歸版歸并排序

只考了一道算法題雷滚，而且面試官說完題意，看我沒有思路就先走了吗坚，留給我20分鐘思考+代碼祈远。

知道歸并排序吧？歸并排序一般用遞歸實現(xiàn)商源，如果不用遞歸怎么實現(xiàn)呢车份？

跟面試官確定的信息：

• 返回值

對，才開始刷題的我也沒見過這道題牡彻。但是過了一會也想通了扫沼，就是用循環(huán)模擬遞歸版歸并排序的執(zhí)行過程，算法描述如下：

1. 申請數(shù)組B，大小為A.length
2. 設(shè)segLen為1缎除，定義長度為segLen的子數(shù)組為1個seg
3. 每兩個seg為一組严就，分別做2路歸并
4. 將數(shù)組B拷貝回A
5. segLen = segLen * 2
6. 如果segLen小于A.length，則回到步驟3器罐；否則繼續(xù)
7. 返回數(shù)組A

因為面試官出去開會了梢为，所以我直接寫了代碼：

public int[] mergeSort(int[] array) {
  if (array == null || array.length <= 1) {
    return array;
  }
  
  int[] arrA = array;
  int[] arrB = new int[arrA.length];
  for (int seg = 1; seg < arrA.length; seg *= 2) {
    for (int i = 0; (i + 1) * seg < arrA.length; i++) {
      merge(arrA, i * seg, (i + 1) * seg, seg, arrB);
    }
    System.arrayCopy(arrB, arrA);
  }
  
  return arrA;
}

private void merge(int[] arrA, int start1, int start2, int seg,
              int[] arrB){
  int l = start1;
  int r = start2;
  int i = start1;
  while (l < start1 + seg && r < start2 + seg
         && l < arrA.length && r < arrA.length) (
    if (arrA[l] <= arrA[r]) {
      arrB[i] = arrA[l];
      l++;
    } else {
      arrB[i] = arrA[r];
      r++;
    }
    i++;
  )
  while (l < start1 + seg && l < arrA.length) {
    arrB[i] = arrA[l];
    l++;
    i++;
  }
  while (r < start2 + seg && r < arrA.length) {
    arrB[i] = arrA[r];
    r++;
    i++;
  }
  return;
}

后面也是分析時間復(fù)雜度和空間復(fù)雜度等。注意如何分析這道題的時間復(fù)雜度：外層循環(huán)O(logn)技矮，內(nèi)層循環(huán)O(n)抖誉，數(shù)組拷貝O(n)衰倦，所以算法整體是O(nlogn)袒炉。

system design

背景不表，精簡描述如下：

學(xué)生每天都會做題樊零，要求設(shè)計一個架構(gòu)我磁，學(xué)生做題后驻襟，能實時看到自己的排名郁副、前100名的排行榜，作業(yè)量每天更新豌习。

跟面試官確定的信息：

• 排行榜按照什么排序——作業(yè)量
• 作業(yè)量是計算作業(yè)次數(shù)還是總量——總量

有一些system design的題目很經(jīng)典存谎，在面試中經(jīng)常出現(xiàn)。我不知道這種屬于經(jīng)典題還是面試官自己出的題目肥隆，反正我都沒見過既荚，也沒準(zhǔn)備，做起來是一樣的栋艳。不過如果有精力恰聘，建議多看看經(jīng)典案例，真的能學(xué)到不少key point吸占。

題目概括起來有四個要求：

1. 所有查詢都是實時的
2. 學(xué)生能查看自己的排名
3. 維護(hù)排名前100的排行榜
4. 作業(yè)量每天清零晴叨，從新計算

第4點沒什么意思，分庫分表旬昭，甚至每天清空一次數(shù)據(jù)庫都可以篙螟，可以不考慮。對于高并發(fā)的系統(tǒng)而言问拘，可概括為兩個需求：

1. 學(xué)生能實時查詢自己的排名
2. 排行榜能實時更新

我設(shè)計的方案以一個桶為核心——之所以想到桶，多半是因為面試前還在復(fù)習(xí)ConcurrentHashMap的源碼。ConcurrentHashMap是java.util.concurrent包中的一個神器骤坐，也算是面試承餍樱考點，你知道它的size()方法是怎么實現(xiàn)的嗎纽绍？我忘記了蕾久，不過我在書里的筆記討論了三種方案：

1. 維護(hù)size變量；每次有段更新時拌夏，同步修改size變量僧著。并發(fā)瓶頸在于size變量上的鎖，相當(dāng)于退化回了串行更新障簿。
2. 不維護(hù)size變量盹愚，但維護(hù)每段的segSize；每次有段更新時站故，僅修改segSize皆怕；每次調(diào)用size()方法，把所有segSize加起來西篓∮冢可根據(jù)一致性要求選擇不同的segSize加和策略：要求完全一致性就在計算時所處所有seg，那么調(diào)用size()方法時產(chǎn)生了并發(fā)瓶頸岂津；要求弱一致性虱黄，可直接加和。
3. 維護(hù)size變量吮成；當(dāng)segSize修改時橱乱，將size置為-1；調(diào)用size()方法時赁豆，如果size為-1仅醇，則重新計算size，同上魔种；如果size不為-1析二，則表示期間未修改seg，直接返回size节预。方案3主要針對方案2叶摄，相當(dāng)于緩存了size值，這樣不需要在未修改segSize時重復(fù)計算size安拟。

好好理解這三種方案蛤吓，我的設(shè)計基于方案2.

需求1

對于需求1，相當(dāng)于ConcurrentHashMap中調(diào)用size()方法的操作糠赦。不同的是会傲，可能存在上千萬個學(xué)生锅棕，對每個學(xué)生都維護(hù)size顯然是不合適的，而不需要維護(hù)size的就只有方案2了淌山。

具體來說裸燎，可以認(rèn)為作業(yè)量有上限，一個學(xué)生不可能一天做無數(shù)作業(yè)泼疑。則可以維護(hù)一組有限的有序桶（桶內(nèi)是否有序可根據(jù)讀寫比例調(diào)整）德绿，每個桶代表一段作業(yè)量的范圍（桶的范圍可根據(jù)并發(fā)規(guī)模設(shè)置，作業(yè)量頻率高的桶可繼續(xù)分成更小的桶退渗，作業(yè)頻率低的桶可合并成更大的桶）移稳，桶之間不重合。則：

當(dāng)前學(xué)生的排名 = 當(dāng)前學(xué)生之前所有桶的size之和 + 當(dāng)前學(xué)生在其桶內(nèi)的排名

需求1的實時性要求一般沒有那么高会油，因為用戶只看自己的排名个粱，就算有一定延遲也不會影響用戶體驗，因此钞啸，每次用戶查看排名都計算一次的消耗是可以接受的几蜻。當(dāng)然，我們可以進(jìn)一步優(yōu)化体斩，比如維護(hù)截止到每段開頭的總排名R梭稚，不過這需要增加一個服務(wù)實時去維護(hù)該段之后段的總排名R'，很可能是得不償失的絮吵。

需求2

稱作業(yè)量高的桶為大端桶弧烤，作業(yè)量低的桶和小端桶。對于需求2蹬敲，相當(dāng)于要維護(hù)大端桶中的前100個學(xué)生暇昂。由于假定作業(yè)量是有限的，則可以從最大作業(yè)量所在的桶開始遍歷伴嗡，直到遍歷非空桶急波，且已按照作業(yè)量遞減的順序遍歷了100個學(xué)生為止，返回排行榜瘪校。

可以做一個優(yōu)化——記錄當(dāng)前最大作業(yè)量maxCnt澄暮，則最大桶的上界不超過maxCnt，且最大桶的size也不超過閾值sizeThreshold阱扬，那么每次可直接從最大的空桶開始遍歷泣懊。

可以繼續(xù)優(yōu)化——由于我們關(guān)心的是固定前100個學(xué)生，那么直接維護(hù)一個最大堆maxHeap是更好的選擇麻惶。對于排行榜而言馍刮，顯然只有插入和查詢（取前100）操作，baseline模型相當(dāng)于插入O(1)查詢O(nlogn)窃蹋；或者插入排序卡啰，則插入時O(n)静稻，查詢時O(1)；而最大堆插入時O(logn)碎乃，查詢時O(1)姊扔。

由于作業(yè)量高的學(xué)生總是極少數(shù)的惠奸，所以大端桶的并發(fā)量要遠(yuǎn)小于其他桶梅誓，維護(hù)maxCnt和maxHeap的成本非常小，收益卻相當(dāng)可觀佛南。

最后梗掰，可以在maxHeap前加一層緩存，異步更新嗅回，以加速前端訪問及穗。

follow up

在基本的架構(gòu)介紹完后，面試官又給出了幾個follow up問題：

1. 現(xiàn)在的服務(wù)都是單點的绵载，如何解決單點故障埂陆？
2. 你的桶要保存在內(nèi)存里，發(fā)生了單點故障怎么辦娃豹？

對于問題1焚虱，我把Hadoop的HA方案套上了。面試官似乎不了解Hadoop的內(nèi)容懂版，覺得我答的不錯鹃栽。對于問題2，我清楚分析了不應(yīng)該把桶與服務(wù)保存在同一份內(nèi)存中躯畴，而應(yīng)該盡量讓服務(wù)無狀態(tài)民鼓，桶交給存儲層，不需要關(guān)心桶的結(jié)構(gòu)蓬抄。把問題2轉(zhuǎn)換成了問題3丰嘉，“如何解決存儲的單點故障”。

首先嚷缭，HA的方案仍然有效饮亏。但老一套沒意思，我就說可以換一種方案峭状。服務(wù)端多實例克滴，客戶端掛載服務(wù)端的實例列表，寫數(shù)據(jù)時讓客戶端維護(hù)服務(wù)端的數(shù)據(jù)一致性（全部寫才算寫成功）优床，還順帶解決了讀數(shù)據(jù)時負(fù)載均衡的問題劝赔；用事務(wù)id解決客戶端寫失敗導(dǎo)致的一致性問題。

現(xiàn)在寫面經(jīng)的時候才發(fā)覺這里回答的并不好胆敞。這種方案的寫負(fù)載太高了着帽，而并發(fā)寫時往往涉及同步問題杂伟，就更麻煩了。如果還是基于客戶端掛載的方案仍翰，那么可以參照NRW策略赫粥，只需要保證R+W>N，就可以保證強(qiáng)一致性予借。不過總感覺還是不夠好越平，比如這種設(shè)計沒有考慮到可伸縮性，距離真正的分布式存儲系統(tǒng)差距還非常大灵迫。

PS：

• N代表數(shù)據(jù)所具有的副本數(shù)秦叛。
• R表示完成讀操作所需要讀取的最小副本數(shù)，即一次讀操作所需要參與的最小節(jié)點數(shù)目瀑粥。
• W表示完成寫操作所需要寫入的最小副本數(shù)挣跋，即一次寫操作所需要參與的最小節(jié)點數(shù)目。

總結(jié)

哎狞换，面試完已經(jīng)7點半了避咆。從下午4點半開始，3個小時修噪，還是挺熬人的查库，累累累，不過當(dāng)場拿到offer十分滿足割按。

最后詢問面試官對我的評價：

• 反應(yīng)快——可能因為看出來我后面兩題都沒做過卻自己想出來了膨报。
• 代碼寫的很好——受寵若驚啊，太不好意思了Ｊ嗜佟Ｏ帜！
• 系統(tǒng)設(shè)計也不錯弛矛，給出基本問題够吩，能清楚設(shè)計出可行的方案，雖然可能沒有怎么接觸業(yè)界的方案丈氓，但自己想的方案也比較完整周循。

二面的面試官是部門總監(jiān)（創(chuàng)業(yè)公司的總監(jiān)都相當(dāng)年輕），這么評價万俗，程度上肯定有夸張了湾笛。不過方向上應(yīng)該值得參考，幫助自己揚長避短闰歪。

我還詢問了今天面試跟正式校招的難度差距嚎研。面試官說跟校招難度類似，略微低一些库倘，但差距不大临扮。我挺驚訝的论矾，都說猿題庫面試重算法，比較難杆勇，面試之前我以為自己一道題就會被轟走贪壳，沒想到撐到了最后。蚜退。闰靴。第一場面試經(jīng)歷如此甜美，幸福幸福~

給自己的建議：

• 乖乖刷題关霸，題量太小传黄，碰到新題就龜速
• 聽強(qiáng)爺?shù)亩嗑毩?xí)表達(dá)，特別在系統(tǒng)設(shè)計上队寇，如何做到條理清晰，吐字清晰章姓，表現(xiàn)出自己的能力佳遣，這一點至關(guān)重要
• 盡量不要裸面了，這次多虧面試前碰巧看了相關(guān)內(nèi)容凡伊，否則可能就掛了
• 菜雞零渐，不要膨脹！不要膨脹系忙！不要膨脹诵盼！

本文鏈接：【面經(jīng)】猿題庫-2017年8月25日，散招實習(xí)生
作者：猴子007
出處：https://monkeysayhi.github.io
本文基于 知識共享署名-相同方式共享 4.0 國際許可協(xié)議發(fā)布银还，歡迎轉(zhuǎn)載风宁，演繹或用于商業(yè)目的，但是必須保留本文的署名及鏈接蛹疯。