當我最初開始參加編程面試的時候,我所有最心儀的公司都忽視了我。現在回頭看那個時候,我發現自己當時去參加面試都完全沒做任何准備。雖然已經有許多博客文章和書籍在講編程面試,但現在的我作為面試官,坐在桌子的另一邊,還是能看到許多來參加編程面試的人沒做任何准備,或者准備得很糟糕。這也就是為什麼我開始寫這篇指南的原因,剛畢業時的我、第一次參加面試的我一定非常想有這麼一份指南來指引自己。而從現在開始,我自己也會照著這份指南去做。
多年以來,我在好幾家公司工作過,所以我的面試技巧得到了很好的磨煉,而且我參與面試的過程也教會了我該說什麼、該做哪些准備,以及如何面試。在這篇指南裡,你會了解到面試的概況、面試取得成功的六大步驟,以及我在考察數據結構和算法時所考慮的方面。這篇指南無法確保你找到工作,但它能幫助你盡最大可能給面試官留下一個好印象。
聲明:本文中的觀點完全出自個人視角,與我目前或者以前的雇主沒有關系。
本節概述了硅谷公司的面試過程,僅僅是個情況介紹,大家可以跳過去往後看。
除了直接申請面試以外,一般說來,還有兩種途徑來獲得面試的機會:由現在的雇主推薦,或者通過LinkedIn。雖然前者會快一些、更尊敬一些,但後者很可能是大部分應聘者所走的路徑。事實上,每天都有無數的招聘人員趴在LinkedIn上,他們唯一的工作就是尋找和接觸有可能換工作的員工,所以一定要保證自己的信息是最新的,而且要多交人脈、多請別人來認可自己的技能,並且要把你所具備的技能、做過的個人項目或者對開源軟件所做的貢獻加到個人頁面裡去。
最初的接觸一般是通過電子郵件進行的,然後招聘人員會給你打電話,大概了解一下你的技術背景。如果你的技能和他們正在尋找的技能一致,他們就會安排一次電話面試,在電話面試時,你可能就會被要求在一份共享的在線文檔裡編程。那麼你就會知道,這份文檔很可能沒有任何代碼補全和句法高亮的功能。電話面試會持續半小時到45分鐘,如果你表現不錯,就會被邀請去參加現場面試。現在如果沒有電話面試、或者在電話面試之外,你可能還得去參加一個小的編程項目。
現場面試由幾次面試組成,總體會持續45分鐘到一個小時。這些面試會和電話面試非常像,只是問題會更難——不過能親眼見到面試官多少算是有所補償。現場面試數周之後,所有反饋應該都被看過、招聘決定就會做出,招誰不招誰也就定了。如果你沒拿到offer,也要明白面試是一個隨機的過程,包含運氣的成分,不妨把它看作是一次學習的經歷。可能你還會想起布萊恩·阿克頓(BrianActon)面試Facebook和Twitter不成、後來成為WhatsApp聯合創始人的故事。
理論上講,用哪種編程語言並不重要,但你面試需要用某種特定語言來完成的工作時除外,比如iPhone開發者或者前端開發者。我強烈建議你用正在面試的公司所使用的一種編程語言來編程(以及練習面試問題)。
編程面試的目的,是為了確定你的編程水平有多高。一般來說,你將被要求用編程來完成一個功能或者方法,但有時候,你會需要編輯一個類的定義,或者設計一系列相關的代碼模塊。在任何一種情況下,你都要有條不紊地解決問題,並遵循以下六個步驟:
1、首先,要確保你理解了面試官的問題。許多問題都是故意措辭模糊或者模稜兩可,這個時候你可以請面試官把問題說清楚,從而確保你真正回答面試官的問題。你的提問同時還有一個好處,就是它能給你自己一些時間,讓你的腦子轉起來。
2、用一到兩個例子來確定問題的限制條件和要求(在現場面試時在白板上完成這個過程,在電話面試時在筆記本上完成)。嘗試用中等規模的例子,以便覆蓋到一些特殊情況。如果你能想到可能相關的表格,就把它畫出來。事實上,把你想到的任何東西都寫下來是會有幫助的,因為它能為你提供一個視覺錨點,從而讓你在走不通時或者思考過程中隨時返回某一個點。
3、把話說清楚,這可能是最重要的一步。要試著讓面試盡可能有更多的互動,面試官不知道你在想什麼,而讓他們參與到你的思考過程裡,會讓她給你一些有用的提示,防止你偏向錯誤的方向。你的目標就是要先和面試官確證你的答案,然後再去寫代碼,而且你考慮答案越清晰、越高效,你得到的即時反饋也就越好。
4、通過應用以下技巧來找到答案:回想一下你遇到的類似問題,再想想它們是如何被解決的,嘗試各種不同的算法(分治算法、貪心算法、遞歸、排序,等等),把問題分解成更小的、可處理的小問題(這樣你就能得到相應部分的分數),最後再通覽一遍你列出的數據結構,因為有時候,只要想到了正確的數據結構,就能給出正確的答案。
5、當你向面試官問清楚了問題、並向她解釋了你的答案之後,就可以開始寫代碼了。要記住,在共享文檔裡寫代碼的時候,你可以復制粘貼、寫評論,而且能回過頭來完成骨架算法和功能。但在白板上寫代碼就不一樣了,它需要你的頭腦很清醒,而且需要你具備管理白板空間的技能。如果足夠幸運的話,現在當你開始在白板左上角動筆的時候,應該非常明白你要寫些什麼東西,而且你要確保在你寫答案的時候,沒有擋住面試官的視線。花點兒時間把代碼寫得緊湊而美觀一點兒,因為你的代碼也會是面試反饋的一部分。在你寫代碼的時候,要大聲解釋你在寫什麼,這會讓你的面試官更容易地跟上你的思路。
6、最後,用不同的例子和特殊案例驗證一下你的代碼,並且要一行一行地過。這會展示你的思考過程,讓你檢查出小錯誤,並告訴面試官你的辦法是可行的。如果你想得到額外加分的話,甚至可以把單元測試的代碼寫下來!最後再和面試官聊一下你的答案在空間和時間利用方面的復雜性,然後結束整場面試。
電話面試值得特別一提,因為這是大多數人失利的地方。之所以會這樣,部分原因在於電話面試是招聘過程中第一道真正的關卡,但也有一部分原因在於,這種形式容易造成溝通的錯誤,而且缺乏可視化線索,所以電話面試是特別嚴酷的。
電話面試有兩大障礙。第一大障礙是,在電話面試的一開始,雙方都能看到的唯一的東西就是一個空白的共享文檔。這會讓面試者傾向於過度補償非語言溝通的缺失,從而著急忙慌地在屏幕上進行溝通。令人遺憾的是,這麼做很少會有好結果。所以當務之急並不是去關注那個正在盯著你的空白文檔,而是要首先理解和評估問題(也就是完成上述六個步驟中的前四個),同時通過盡可能地沉浸到面試中來彌補現實存在感的缺失(要記住,電話的另一頭是一位可以很容易就被別的事情[比如查看郵件]分心的面試官)。
電話面試的第二大障礙,就是要同時在電腦上打字和在電話上聊天的後勤保障問題。你不必一只手敲代碼、一只手打電話,也不必把電話調到揚聲器模式,我建議你用電腦上的Google Hangouts接面試電話(你得有一個GoogleVoice號碼,而且得在面試前測試一下)。你還可以用耳麥或者耳機來進一步降低不好的接收效果、提高溝通質量。
算法+數據結構=程序 如果你正在思考為什麼軟件工程的面試和日常編程不一樣,那你可能有興趣讀一下Quora上的這條回答。最根本的原因在於:面試是為了測試你在計算機技術方面的基礎,所以會非常偏重算法和數據結構,因此你可能需要練習一些面試問題,從而讓自己具備解決面試問題的心態。
從短期來看,你所能做的最好的准備工作就是買一塊白板,並通讀一遍《程序員面試金典》(Cracking The Code Interview),裡面都是很好的建議,而且裡面的許多面試問題和答案會幫助你確定問題所在,並匹配好回答模式。請參閱本指南最後列出的常用面試問題。
當然了,長遠來看,我們都會死掉,所以我會把事情搞簡單,說一些你絕對應該復習一下的關鍵概念。
大部分數組和字符串是可互換的,事實上,你遇到的大部分字符串處理的問題,都可以在理解數組的基礎上得到解決。記住這一點之後,你應該懂得如何遍歷數組,知道如何訪問、轉換和調換其中的每一個元素,而且要懂得如何對它們進行各種不同的集合運算。和其他算法相比,二分法檢索(Binary search)可能會更多地成為面試問題的核心內容(如果你曾經碰到過有分類數組的問題,那麼二分法檢索有可能應該是你答案的一部分),你絕對必須知道如何使用它。
和數組密切相關的,是排序算法。你不大可能會被要求重復使用一個排序算法,但很可能你至少知道排序是如何在O(nlogn)的時間裡完成的就行。不過你應該大概知道歸並排序(merge sort)或者快速排序(quicksort)和基數排序(radix sort)的執行細節。
動態數組/可增數組 動態數組可以按需重新調整自己的大小,同時依然提供分時平攤的持續時間訪問。一種典型的做法是,當在一個全排列數組中增加一個元素的時候,會形成一個新的、更大的數組,而舊數組中的元素也會被復制到新數組裡。你應該在面試時做到完成一個動態數組。
如果你拿到一個非數組類問題,但你在答題中需要用到像數組結構這樣的數組,不妨少給自己惹麻煩,直接用動態數組吧。
哈希映射/哈希表/詞典/哈希集合 哈希表(Hash tables)是編程時的瑞士軍刀,很多不同類型的問題(檢查存在、計算頻率、排序,等等)都能用哈希表來完美解決。它幾乎肯定會出現在你的面試中,而你應該理解它的原理(哈希功能的角色、沖突如何解決、什麼時候要調整大小、為什麼)以及如何運用它們。
鏈表問題在C和C++的面試中最常見,因為它們是弄清楚應聘者是否理解指針的一種簡單的辦法。不過這個點太初級、太基礎了,所以不管用哪種語言,你都應該知道該如何從零做起應用它們。而且由於大部分鏈表問題不過是與人所周知的遍歷還有刪除和插入相關的問題的變體,所以鏈表問題准備起來很容易,你沒有理由拿不到這部分分數。
許多鏈表問題中都會用到一個小技巧,那就是慢速/快速指針技術。它的簡單版含義如下:使用兩個指針迭代生成一個列表,其中一個指針在另一個指針的前面。快速模式下的指針可能會是一個位於前面的固定數值(它有助於確定列表有無循環,或者找到列表中的第k個元素),或者也可能會跳過慢速指針經過的多個結點(打個比方,如果快速指針的速度是慢速指針的兩倍,那麼當它到達列表末尾時,慢速指針將會位於列表的中間)。
請注意,當面試官談到鏈表時,他們常常指的是單鏈表,但你無論如何都應該問清楚。
棧和隊列一般會是你用來解題的數據結構的一部分。你應該知道如何用鏈表和數組兩種方式來實現它們。
加練兩道題:利用兩個隊列實現一個棧,以及利用兩個棧來實現一個隊列。
你可能不會每天都見到樹和圖,但你很可能會在面試時遇到它們,所以你要徹底地看一下這些數據結構。
樹最一般的定義,是和其他結點沒有或者有一個以上關系的結點的集合,但在實踐中,當面試官說“樹”的時候,他們指的是一種叫二叉樹的東西。二叉樹是一種樹的類型,它的每個結點都至多有兩個子樹,一般被稱為左子樹和右子樹。
你不應該把二叉樹和二叉搜索樹混淆起來,後者是一種特殊的二叉樹,它的左子樹結點上的值都比父結點小,而右子樹結點上的值都比父結點大或者相等。二叉搜索樹的優點是,如果樹的結構相對平衡(向面試官問清楚這個問題),那麼查找、插入和刪除就可以在O(log n)的時間裡完成。二叉搜索樹的其他重要屬性,就是你跟著所有的左子樹走,就能得到這個樹上最小的元素,而跟著所有的右子樹走,就能得到這個樹上最大的元素。
請注意,是有辦法讓樹一直保持平衡的,最常用的辦法就是紅黑樹和AVL樹。我不會去弄清楚它具體實現的細節,只要知道有這些數據結構就行。
不過你絕對必須知道遍歷樹(tree traversal)算法:廣度優先搜索(breadth-first-search)、深度優先搜索(depth-first-search),以及中序遍歷、後序遍歷和前序遍歷之間的差別。
以下是在Java實現中序遍歷的例子,它可以打印出一個樹的所有值(前序遍歷和後序遍歷幾乎和這個一樣):
void inOrderTraversal(Node
root) {
if (root == null) return;
inOrderTraversal(root.getLeft());
// System.out.println(root.getValue());
inOrderTraversal(root.getRight());
}
字典樹(trie,讀“tree”)常常被用在字符串問題裡,它是一個n元樹,除了根結點以外的每個結點都代表一個字符或者部分或完整的單詞,而且沿著樹的每一條路徑都代表一個單詞。實際上它真的沒有聽起來那麼復雜,只要讀一下維基百科上的頁面、了解該如何構建一個字典樹以及如何查詢其中的數值就行。請注意,你可以通過前序遍歷輸出字典樹中的所有鍵。作為一個練習,你可以想一想自己會如何利用字典樹實現自動完成功能。
最後是堆(heaps),它也被稱為優先隊列,是你應該了解的最後一種數據結構。它們通常都是滿足堆屬性的二叉樹:每個結點的子樹的值都比結點本身的值小,或者與它相等。所以根結點的值總是最大的,也就是說你總能找到最大值,但代價就是尋找其他任何一個值所需的時間都是O(n)。插入和刪除所需的時間依然是O(logn)。
和樹一樣,圖也是由帶子集的結點組成的,但和樹不一樣的地方在於,這些結點可以有多個父結點,所以可能會形成自環(loop)或者圈(cycle)。除了鏈接——也被稱作邊(edges)——之外,兩個結點之間可能地有比指針更多的信息,而且可能會有值和權重。邊有方向的圖被稱為有向圖,而只有雙向指針的圖被稱為無向圖。邊上有權重的圖被稱為加權圖。
有三種方法來表示圖,但你只要搞清楚鄰接矩陣(adjacency matrices)和鄰接表(adjacency lists)就行了。你應該了解它們計算的復雜程度、它們需要折衷的地方,以及如何在現實的代碼中實現它們。用哪種方法取決於你有的圖的類型,比如連接完整的簡單圖可能用鄰接矩陣來實現更好,而稀疏一些的圖則可能用鄰接表來表示更好。
請注意,如果你是在實現加權圖,很可能需要定義一個Edge類。
圖論是一個非常寬泛的話題,所以很難知道一個人應該為一場面試去熟悉多少種圖論算法,所以我只是列出了我認為可以覆蓋90%圖論問題的內容:你絕對必須知道該如何遍歷一個圖(深度優先或者廣度優先),以及如何做拓撲排序(topological sorting),你應該知道如何實現迪傑斯特拉(Dijkstra)的最短路徑算法(這裡有一個制作精巧的視頻解釋了這一算法),同時也要知道如何實現普裡姆(Prim’s)算法。最後,如果你還知道如何實現A搜索算法(Asearchalgorithm),那就更好了。
使用以上數據結構,你就可能解決絕大多數問題了,但也請盡管在這個部分下留言,為其他讀者推薦其他數據結構。
要想處理位元,你必須先得知道在二進制補碼(two’s complement)標記內部,數字是如何表示的——二進制補碼和無格式二進制標記是一樣的,只是負數要“進行位元翻轉之後再加1”。比如要想得到數字-1,你要從用8位二進制整數表示是00000001的1開始。對每一個位元進行翻轉之後的結果是11111110,再加上1就是11111111,也就成了二進制補碼中的-1。
左移位運算符“<<”會把位元移向左邊,用0來補上移走之後的空位。
右移位運算符“>>”會把一個位模式向右移,但當向右移動負數時,它的作用在不同編程語言中也不一樣,在Java中,右移位會用符號擴充的辦法,用1來填充負數中的空位。
邏輯右移位運算符“>>>”是Java和Javascript中獨有的,無論數值是多少,它都用0來填充空位。
設置某一位:可以用按位或運算符(|)。
num |= 1 << x; //這行代碼將會設置位元x
清除某一位:可以用按位與運算符(&),並且用取反運算符(~)來屏蔽所有你不想清除的位元。
num &= ~(1 << x); //這會清除位元x
清除一直到i的所有有效位元:
num &= (1 << (i + 1)) -1;
切換某一位元:可以用按位異或運算符(^)
num ^= 1 << x; //這會切換位元x
獲得一個位元:對你想檢查的位元用按位與
bit = num & (1 << x);
和面向對象編程相關的問題,一般會涉及到設計相關類裡的集,以便檢驗你對面向對象編程的熟悉程度,並了解你是如何架構代碼的。你可以使用界面和/或抽象的類來說明,並記住用單例模式(Singleton)、工廠方法模式(Factory)和策略模式(Strategy)來解決這類問題,在編寫優雅而可維護的代碼方面,它們能對你有長久的助益。
要知道如何用你正在使用的編程語言來讀取和寫入文件,並且要知道如何生成隨機數。
你並不是在面試數學相關的職位,但考慮到我們被計數和測量的問題所包圍,所以有一些數學概念也成了編程面試時關注的東西,比較重要的有質數、進制轉換(base conversions)和一些基本的組合數學。
對於質數,要大概知道為什麼它們很重要,並且要知道每一個數都可以被分解成質數的和。你還得知道如何實現埃拉托斯特尼篩法(sieve of Eratosthenes)。
對於基本的組合數學,你得知道排列和組合。
排列是對一個集合中的數按照一定的次序或者順序進行整理。比如對於集合{1,2,3},就有6種排列的方式,也就是(1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、(3,1,2)和(3,2,1)。n個不同數字的排列方式一共有n!種。
還有一種排列叫部分排列,也就是從n個數字的集合中取出k個不同的元素,然後再進行排序。這種排列可以用下面的公式來表達:
組合則是從一個組裡選擇成員的一種方法,因此選擇的順序並不重要。比如一手牌可以被描述成是從52張一摞的牌堆(n=52)中選出5張組成一組(k=5)。從有n個元素的集合中挑出k個元素,當k>n時,不存在相應的組合,否則這k個元素的組合的數量可以用下面的公式來表達:
當k<=n時,從有n個元素的集合中挑出k個元素的組合形式數量的一般公式。
並發 並發問題在面試中並不常見,但也確實有過,所以你肯定不想到時候毫無准備,那就再去看一下如何生成線程、使用同步以及鎖定對共享資源的訪問,並理解會導致死鎖(deadlocks)的幾種情況。准備這個話題有一個好辦法,那就是去做出來一個你最喜歡的數據結構的同步版本。
·要問問題。要真正對你的面試官每天都在做什麼抱有真正的興趣,問問他們工作中遇到的機遇與挑戰,提前准備幾個程式化的問題,顯示一下你對公司和這個職位的興趣。不過無論你做什麼,都別問對方“你感覺如何”。首先,你很可能會收到同樣程式化的回答,其次,把面試你的人擺在那樣一個位置上,也不是什麼好主意。
祝各位職場和面試好運!
原文來自Medium Stefan De Clercq,翻譯由is譯社葛仲君提供。
轉載請注明原作者和來自於Nextoffer。