Cate：我是如何準備Google面試的
導讀：Cate 是一位加拿大的軟件工程師，目前就職于 Google 。本文是他在 2010 年在 Google 面試后分享的文章。
也許你可能沒有參加過谷歌面試（或者沒能答出面試中的一些問題），這里我會分享一下上周我的面試經歷。我個人感覺良好——至少已經全力以赴了，無論結果如何都會對我有很大的幫助。
由于已經簽了保密協議，因此我不會寫出面試的問題。然而，我會寫一下我是如何得到這個面試機會以及準備面試的過程。
首先，面試的是谷歌。如果沒有在 Google 工作的朋友和我談起并推薦我，我是不會應聘的。因為我“離得比較近”，因而沒有參加電話面試，直接進行了在線面試。我并不認為渥太華和滑鐵盧（加拿大）離 得很近（也許這是因為我沒有加拿大人的距離感！），但是我確實認為與人面對面的交流會比電話面試好的多。那天我的運氣特別的好，因為那天晚上的經歷就像是 “Ignite! Waterloo”活動，非常酷。
譯注：Ignite! Waterloo：加拿大的一個社區活動，在廣泛的議題上進行五分鐘快速演示，展示了滑鐵盧地區的極客文化。
首先，我和招聘專員簡單聊了聊，他/她告訴我可以使用白板，并且介紹了整個面試流程。接下來我和兩個軟件工程師分別進行了 45 分鐘一對一交流。我驚奇地發現原來面試也可以這么有趣！通常我在面試的時候都會非常緊張，然而這次沒有與很弱的人一起扎堆面試，這真的很酷！第一長面試的 問題非常簡單，第二場雖然難一點但也面得不算太差。最困難的恐怕就是在白板上編程（不能用電腦！）——在白板上很難用 TDD（測試驅動開發）！他們會告訴你不要穿正裝，實際上最好也不要這么做——我費了不少時間坐在地板上寫白板，身邊到處都是各種記號筆。可以想象如果穿裙子會是怎樣的情景！
他們提前會發一份面試需要準備的事項列表，這對我非常有幫助。雖然我大學的課程學得很好，但最好還是有針對性地復習一些專題。除了通常的準備， 這里還有一些額外可以關注的內容——保持與最新的業界資訊更新，大量使用 Google 的產品，思考如何使用技術改變生活，撰寫博客（是的，最后兩項也很有幫助）。與此同時，我已經很好地掌握并運用 Java 5 擴展，像是范型、枚舉、for-each 等等。
下面是我用來準備的相關資料：
讀《Effective Java (第二版)》 –——作為一名合格的 Java 程序員沒有任何理由不推薦這本書。
讀《程序員面試攻略》 并運行所有書中的例子——對于回顧類似樹、列表這樣的數據結構基礎概念非常有幫助。我不是很喜歡遞歸那一章（從我自己使用的角度），我更推薦使用迭代。盡管如此，它真的是一本非常有用的好書。
讀《編程人生》 –——這本書中有很多人在谷歌工作，這從另一方面說明了谷歌的文化。書中同樣還充滿了很多我以前從未注意到的有趣編程故事，還有這些牛人是如何解決問題，討論 API 以及增強程序擴展性等內容。
復習《Combinatorial Algorithms: Generation, Enumeration, and Search》 中的背包問題（Knapsack），旅行商問題（Traveling salesman）以及 NP 完全問題（在秋季學期里我學了組合數學并且從頭到尾讀完了這本書）——坦率的說，我不很喜歡這本書。我感覺這更像是一本數學書。如果你是一名程序員而不是 數學家，用實際的代碼來解決這一類問題可能會更有幫助，而且 Wikipedia 讀起來肯定更容易理解。
做一些《Java 解惑》中的問題，這會幫助鍛煉你閱讀代碼找錯的能力。雖然我沒有被問到這類問題，但是我確實需要仔細檢查自己的代碼。IBM 在我的手機屏幕上給我出過電子商務的問題，我知道谷歌也會使用這類題目。
復習并發問題——死鎖、 活鎖、互斥量、 鎖和信號量等等。在 Java 中什么時候使用synchronized關鍵字？你怎么樣避免死鎖和活鎖？
復習樹的遍歷 ——前序遍歷、中序遍歷和后續遍歷，深度優先搜索 vs 廣度優先搜索、A*算法，Dijkstra 算法等等。
復習平衡二叉樹——紅黑樹、AVL 樹和 伸展樹（Splay-tree）。
復習圖——圖的表示， 最小生成樹，圖的搜索等等。
編程實現 6 種排序算法——包括算法復雜度為O(n log n)的那些算法，使用 TDD 風格編程（我使用的測試用例可以參考這篇博客）。
編程實現哈西表，要求只能使用數組。支持包括：范型，動態數組，延遲初始化，要求測試優先。
練習所有手頭上能夠找到的問題——搜索“Google interview questions”，不用有什么顧慮，可以看看這些問題。有時候我用 Eclipse 寫代碼，但也會用 Google docs。我會找一個朋友審查我的代碼并向我提問。
經常找在谷歌工作的朋友聊天，問很多問題。他非常棒，并且全力幫助我準備面試。不僅如此，通過理解他為什么認為我適合在谷歌工作，我也更深入地理解了自己想去谷歌工作的理由（是的，這的確有點迂腐。但是正如我的導師告訴我的，即使是谷歌，挑選你喜歡的公司和公司挑選你也是同樣重要）。
雖然我自己認為只是準備充分，但在谷歌工作的朋友戲稱我準備得“幾近完美”。除了這些準備之外，我還能做些什么呢？
更多的代碼分析實戰 —— 盡可能多地找代碼去分析。
計算數列的和。例如，你如何計算數字1-n的和？請給出證明。回顧我在第二場面試中的分析，我給出的答案是： (n-1)(n-2) + (n-2)(n-3) + … + (3)(2) + (2)(1)。當然，我沒有及時地給出答案，所以我的時間復雜度上限是O(n³)。
復習 Java 函數庫，數據結構。這個時候，我會認真地回答：“我知道有這樣的數據結構不會接收重復的值，只是現在記不起來叫什么名字了”。實際上只要實現 Set 接口就可以做到，這個我也是下午才剛學會。
復習函數庫中的某些關鍵點——Arrays 和 Strings 非常有用。
練習在白板或者紙上編程。你可能想當然地想在白板上插入一行或者進行重構，這可是非常困難。同樣地，在白板上寫代碼很容易忘記寫 return 語句。Eclipse 從來不會讓我自己寫這些聲明和 reurn 語句，并且會把我的代碼放在函數的中間，而白板可做不到！
接下來該做什么？
等待。
等待。
等待！
無論結果如何，我都希望能得到一些反饋。
把面試的問題寫成代碼（同時寫好測試用例！）
完成《Java 解惑》中的問題。
整理面試經歷——我花了很多時間準備這次面試，相信你可能已經收藏了這些面試題目。
尋找其它的機會。我對 IBM 特別感興趣，找一些在那里工作的朋友看看有沒有什么合適的機會。
和導師們談談這次面試經歷。