鍊家面經：一面跪

遠端

關于遠端筆試，隻記得兩道題，詳見：

http://blog.csdn.net/u010429424/article/details/77449966

現場筆試 && 一面

首先進行一個小時的筆試。一面的主要内容就是讨論筆試題，然後聊了一些履歷上的東西。面試官人很和藹，溝通起來不累。筆試題如下：

1、有一個數組包含1000w個整數，給定一個整數n，在數組中找到所有ai和bi，使得ai+bi=n。

首先想到了暴力法，時間複雜度是O(n^2)，然後使用了一個桶排序優化暴力算法。

正解：可以參考Two Sum的解法:http://blog.csdn.net/u010429424/article/details/77648989

以【2，7，11，15】 n=9為例。從2開始掃描整個數組，內插補點9-2=7，此時7 不在HashMap中，就把2和2的下标0添加到HashMap中。此時HashMap中的元素為【(2,0)】。

下一步掃描到7，內插補點9-7=2，發現2已經在HashMap中，說明2和7一個是ai，一個是bi。

整個算法的時間複雜度為O(n)，就是掃描一遍數組的時間。

2、二叉樹，找到兩個節點的最近公共父節點。

由于題目沒有給出二叉樹的輸入形式，是以根據以往的做題經驗，如果二叉樹以數組的形式給出，則直接用公式就能計算出父節點。比如二叉樹【1，2，3，4，5】，則4、5的父節點下标為(3-1)/2 = 1和(4-1)/2 = 1。

如果二叉樹以樹的形式給出，分兩種情況考慮，如果二叉樹節點中有指向父節點的指針，則可以通過這個指針很友善地找到公共父節點。如果二叉樹中沒有指向父節點的指針，則先通過dfs找到根節點到4、5節點的路徑：1、2、4和1、2、5，路徑使用連結清單存儲，然後從4、5向前找到第一次出現的公共節點。

正解：

LeetCode上原題：http://blog.csdn.net/u010429424/article/details/77650420

3、一個袋中有n個球，球上面有标号，标号可以相同也可以不同。如果袋中球的編号之和大于編号之積，則叫做幸運袋，反之就是不幸運的。比如【1、3】1+3 > 1* 3就是幸運的；【2、3】，2+3 < 2 * 3就是不幸運的。現在給出一個數組，可以去掉某些球使得剩餘構成幸運袋，問幸運袋的個數。

沒有思路，笨啊

4、通過IP怎麼查找到城市。給出一組IP位址和對應的城市名，問使用怎樣的資料結構，能夠找到城市。PS：面試官說IP位址要轉成長整型。

第一個思路使用Trie樹來存儲IP，葉子節點對應城市。但看到題目的函數輸入是整型的ip，瞬間感覺也可以用Hash來做，key是ip，value是對應的城市。因為不知道怎樣把ip轉換成int，被面試官鄙視了。。。。（當時說ip本質上也是用二進制來表示的，是以可以通過位運算轉換成int）

ip位址轉long：http://blog.csdn.net/u010429424/article/details/77652216

5、編輯器的undo撤銷，redo恢複怎樣實作，寫出代碼。

看到這道題的第一反應就是git。但是不懂git的資料結構，隻能裝模作樣地設計了一個雙向連結清單。這樣，通過指針的改變就能很快地前移和後退。結構又被面試官鄙視了~

後來聽同學說可以使用兩個棧來實作，參考：http://blog.csdn.net/cb0912cn/article/details/444393

聊履歷時，因為履歷上寫了一個圖像處理方向的項目，面試官對這個項目發問較多。感覺自己回答的思路還算清晰。之前準備的java基礎知識都沒有被問到，可能在這個時候面試官就已經把我pass了吧。

歡迎大神補充，自己太菜，回頭總結一下，再接再厲 :-)， 注：侵必删

注：學渣心裡苦，不要學樓主，平時不努力，考試二百五，哭~