- 相關(guān)推薦
面試題分析：我的Twitter技術(shù)面試失敗了
確認(rèn)我返回亞馬遜實(shí)習(xí)的截止期限是10月28日，但是我的朋友Daniel說(shuō)服我如果我被Twitter錄取，我就不用參加任何面試了。所以我去Twitter面試了。
首先他們讓我在一個(gè)小時(shí)內(nèi)完成兩道編程能力的問(wèn)題。問(wèn)題很有意思：“這是回文(譯注：正著讀和倒著讀是一樣的)嗎?”以及“計(jì)算二維數(shù)組的平衡點(diǎn)”。我不是很有自信，但是Twitter的一個(gè)招聘人員Judy給我發(fā)了email并安排了周三5:30的電話甄選。
我不知道你怎么樣，反正我在面試前是很緊張的。我覺(jué)得這主要是因?yàn)槲也幌胱屆嬖嚬僬J(rèn)為我很蠢。所以你可以想象，5:20我清空了桌子，記事本上標(biāo)注了“Twitter面試，十月23日，周三”，還有為涂畫(huà)準(zhǔn)備的兩只削尖的鉛筆。然后5:30到了，我開(kāi)始盯著我的電話。
5:35我去google了一下“加利福尼亞時(shí)間”來(lái)確定我的時(shí)差計(jì)算是正確的。沒(méi)問(wèn)題：Google說(shuō)是太平洋標(biāo)準(zhǔn)時(shí)間2:30，美國(guó)東部時(shí)間5:30。
5:48我給Judy發(fā)了email，請(qǐng)她看下情況。10分鐘后我接到了一個(gè)來(lái)自舊金山的電話。Judy對(duì)她搞砸了這件事情道歉，并告訴我Justin現(xiàn)在可以面試我。
深呼吸
“棒極了，我們開(kāi)始吧!”
Justin同樣對(duì)這個(gè)行程安排錯(cuò)誤道歉，并很快深入到編程問(wèn)題中：
“看下面這個(gè)圖片”
“在這個(gè)圖片里我們有不同高度的墻。這個(gè)圖片由一個(gè)整數(shù)數(shù)組所代表，數(shù)組中每個(gè)數(shù)是墻的高度。上邊的圖可以表示為數(shù)組[2,5,1,2,3,4,7,7,6]”
“假如開(kāi)始下雨了，那么墻之間的水坑能夠裝多少水呢?”
“以1×1的方塊為單位計(jì)算容積。所以，在上邊的圖中下標(biāo)為1以左的都會(huì)漏掉。下標(biāo)7以右的也會(huì)漏掉。剩下的只有在1和6之間的一坑水，容積是10”
我首先試圖做的事情是搞清楚在給定的兩個(gè)下標(biāo)之間到底有多少水。這個(gè)過(guò)程跟微積分很像，所以我立即想起可以用極大值。實(shí)際上在上邊的圖片中，下標(biāo)2以上的水是由周圍的兩個(gè)極大值下標(biāo)1和6約束的。
我把我的想法說(shuō)了出來(lái)：“如果我們找到所有的極大值，然后在他們之間填水。這樣做有用么?”
“恩，這樣應(yīng)該有用” Justin回復(fù)。
我去給這個(gè)解答寫(xiě)代碼。然后Justin讓我提供一套測(cè)試用例。我們討論的所有測(cè)試用例似乎也挺好。
“你有問(wèn)題問(wèn)我嗎?”Justin問(wèn)我。“我做的怎么樣?”“還算不錯(cuò)。你的方法用了兩次遍歷，但有一個(gè)更有意思的方法只用一次遍歷。”
然后我們聊了一小會(huì)關(guān)于在twitter的生活。
我掛掉電話的那一秒我意識(shí)到了我的答案是錯(cuò)的。
想想這個(gè)輸入：
我的答案計(jì)算的是極大值之間的水，就像這樣。
但是答案應(yīng)該是在兩個(gè)高塔之間只有一池水：
第二天我把這個(gè)問(wèn)題給我的技術(shù)支持看，他是理論計(jì)算科學(xué)的博士生。40分鐘之后他還是卡在這個(gè)問(wèn)題上。
今天早上我?guī)е诔艉挽`光一閃起床。答案是簡(jiǎn)單而漂亮的。
現(xiàn)在我捫心自問(wèn)：在這件事我學(xué)到了什么?客觀地說(shuō)——不多。對(duì)于面試官?zèng)]有問(wèn)我正確的問(wèn)題來(lái)引導(dǎo)我向正確的方向思考，我很難過(guò)。當(dāng)我的解答實(shí)際上不正確的時(shí)候，我不知道為什么Justin告訴我“這應(yīng)該有用”。我知道解答中的問(wèn)題應(yīng)該在他要求的測(cè)試用例中顯示出來(lái)，但既然我在思考算法的時(shí)候沒(méi)有考慮到，我就不可能想到要測(cè)試它。
我跟亞馬遜簽了合約明年夏天上班，并且對(duì)此我很興奮。同時(shí)，我也禁不住問(wèn)一句“如果我通過(guò)了面試會(huì)怎么樣?”
這里是答案的概要。
邏輯如下：
如果我們從左至右遍歷列表，每個(gè)下標(biāo)水的量最多是到現(xiàn)在為止最大的數(shù)。這表示如果我們已知右邊有相等或更大的，我們可以知道存下的水有多少。反向遍歷的時(shí)候也一樣：如果我們知道左邊有比右邊最大的數(shù)更大的，我們裝水是毫無(wú)問(wèn)題的。
基于這個(gè)想法，一個(gè)解決方法是：先找到最大值，從左遍歷到最大值，然后從右遍歷到最大值。這個(gè)方法需要兩次遍歷：一次找到最大值，另一次分成了兩個(gè)子遍歷。
一次遍歷的方法通過(guò)兩端的指針相向移動(dòng)避免了尋找最大值。如果(左指針找到的左指針以左的最大值)小于(右指針找到右指針以右的最大值)，將左指針向右移動(dòng)一位。否則右指針向左移動(dòng)一位。重復(fù)過(guò)程直到兩個(gè)指針相遇。(解釋起來(lái)很麻煩，但是代碼很簡(jiǎn)單)
【面試題分析：我的Twitter技術(shù)面試失敗了】相關(guān)文章：
幫你分析面試失敗的要素08-07
硅谷面試題精選02-03
Cisco的面試題09-25
樂(lè)事面試題11-05
文員面試技巧與面試題08-09
名校英語(yǔ)面試經(jīng)典常見(jiàn)的面試題09-25
那些最經(jīng)典的面試題08-20
c面試題目09-25
模擬面試題目09-25