確認(rèn)我返回亞馬遜實(shí)習(xí)的截止期限是10月28日，但是我的朋友Daniel說服我如果我被Twitter錄取，我就不用參加任何面試了。所以我去Twitter面試了。

首先他們讓我在一個(gè)小時(shí)內(nèi)完成兩道編程能力的問題。問題很有意思：“這是回文（譯注：正著讀和倒著讀是一樣的）嗎？”以及“計(jì)算二維數(shù)組的平衡點(diǎn)”。我不是很有自信，但是Twitter的一個(gè)招聘人員Judy給我發(fā)了email并安排了周三5:30的電話甄選。

我不知道你怎么樣，反正我在面試前是很緊張的。我覺得這主要是因?yàn)槲也幌胱屆嬖嚬僬J(rèn)為我很蠢。所以你可以想象，5:20我清空了桌子，記事本上標(biāo)注了“Twitter面試，十月23日，周三”，還有為涂畫準(zhǔn)備的兩只削尖的鉛筆。然后5:30到了，我開始盯著我的電話。

5:35我去google了一下“加利福尼亞時(shí)間”來確定我的時(shí)差計(jì)算是正確的。沒問題：Google說是太平洋標(biāo)準(zhǔn)時(shí)間2:30，美國東部時(shí)間5:30。

5:48我給Judy發(fā)了email，請(qǐng)她看下情況。10分鐘后我接到了一個(gè)來自舊金山的電話。Judy對(duì)她搞砸了這件事情道歉，并告訴我Justin現(xiàn)在可以面試我。

深呼吸

“棒極了，我們開始吧！”

Justin同樣對(duì)這個(gè)行程安排錯(cuò)誤道歉，并很快深入到編程問題中：

“看下面這個(gè)圖片”

“在這個(gè)圖片里我們有不同高度的墻。這個(gè)圖片由一個(gè)整數(shù)數(shù)組所代表，數(shù)組中每個(gè)數(shù)是墻的高度。上邊的圖可以表示為數(shù)組[2,5,1,2,3,4,7,7,6]”

“假如開始下雨了，那么墻之間的水坑能夠裝多少水呢？”

“以1×1的方塊為單位計(jì)算容積。所以，在上邊的圖中下標(biāo)為1以左的都會(huì)漏掉。下標(biāo)7以右的也會(huì)漏掉。剩下的只有在1和6之間的一坑水，容積是10”

// 給好奇的讀者的旁注：我在底部附上了正確答案的要點(diǎn)。你可以繼續(xù)閱讀而不怕劇透。:)

我首先試圖做的事情是搞清楚在給定的兩個(gè)下標(biāo)之間到底有多少水。這個(gè)過程跟微積分很像，所以我立即想起可以用極大值。實(shí)際上在上邊的圖片中，下標(biāo)2以上的水是由周圍的兩個(gè)極大值下標(biāo)1和6約束的。

我把我的想法說了出來：“如果我們找到所有的極大值，然后在他們之間填水。這樣做有用么？”

“恩，這樣應(yīng)該有用” Justin回復(fù)。

我去給這個(gè)解答寫代碼。然后Justin讓我提供一套測(cè)試用例。我們討論的所有測(cè)試用例似乎也挺好。

“你有問題問我嗎？”Justin問我。“我做的怎么樣？”“還算不錯(cuò)。你的方法用了兩次遍歷，但有一個(gè)更有意思的方法只用一次遍歷。”

然后我們聊了一小會(huì)關(guān)于在twitter的生活。

我掛掉電話的那一秒我意識(shí)到了我的答案是錯(cuò)的。

想想這個(gè)輸入：

我的答案計(jì)算的是極大值之間的水，就像這樣。

但是答案應(yīng)該是在兩個(gè)高塔之間只有一池水：

第二天我把這個(gè)問題給我的技術(shù)支持看，他是理論計(jì)算科學(xué)的博士生。40分鐘之后他還是卡在這個(gè)問題上。

今天早上我?guī)е诔艉挽`光一閃起床。答案是簡(jiǎn)單而漂亮的。

現(xiàn)在我捫心自問：在這件事我學(xué)到了什么？客觀地說——不多。對(duì)于面試官?zèng)]有問我正確的問題來引導(dǎo)我向正確的方向思考，我 很難過。當(dāng)我的解答實(shí)際上不正確的時(shí)候，我不知道為什么Justin告訴我“這應(yīng)該有用”。我知道解答中的問題應(yīng)該在他要求的測(cè)試用例中顯示出來，但既然 我在思考算法的時(shí)候沒有考慮到，我就不可能想到要測(cè)試它。

我跟亞馬遜簽了合約明年夏天上班，并且對(duì)此我很興奮。同時(shí)，我也禁不住問一句“如果我通過了面試會(huì)怎么樣？”

這里是答案的概要。

邏輯如下：

如果我們從左至右遍歷列表，每個(gè)下標(biāo)水的量最多是到現(xiàn)在為止***的數(shù)。這表示如果我們已知右邊有相等或更大的，我們可以知道存下的水有多少。反向遍歷的時(shí)候也一樣：如果我們知道左邊有比右邊***的數(shù)更大的，我們裝水是毫無問題的。

基于這個(gè)想法，一個(gè)解決方法是：先找到***值，從左遍歷到***值，然后從右遍歷到***值。這個(gè)方法需要兩次遍歷：一次找到***值，另一次分成了兩個(gè)子遍歷。

一次遍歷的方法通過兩端的指針相向移動(dòng)避免了尋找***值。如果（左指針找到的左指針以左的***值）小于（右指針找到右指針以右的***值），將左指針向右移動(dòng)一位。否則右指針向左移動(dòng)一位。重復(fù)過程直到兩個(gè)指針相遇。（解釋起來很麻煩，但是代碼很簡(jiǎn)單）

譯者注：

這是我用python實(shí)現(xiàn)的作者的最終算法：

def calculate(testcase): 
    max_l = p_l = 0 
    max_r = p_r = len(testcase) - 1 
  
    puddle_volumes = [] 
    volume = 0 
    while p_r > p_l : 
        if testcase[max_l] < testcase[max_r]: 
            p_l = p_l + 1 
            if testcase[p_l] >= testcase[max_l]: 
                max_l = p_l 
            else: 
                volume = volume + (testcase[max_l] - testcase[p_l]) 
                pass 
            pass 
        else: 
            p_r = p_r - 1 
            if testcase[p_r] >= testcase[max_r]: 
                max_r = p_r 
            else: 
                volume = volume + (testcase[max_r] - testcase[p_r]) 
                pass 
            pass 
        pass 
    pass 
  
    return volume 

用了3個(gè)不同的測(cè)試用例,其中兩個(gè)是文中給出的：

testcase_1 = [2,5,1,2,3,4,7,7,6] 
testcase_2 = [2,5,1,3,1,2,1,7,7,6] 
testcase_3 = [6,1,4,6,7,5,1,6,4] 
print "case %s total volume : %s " % (testcase_1, calculate(testcase_1)) 
print "case %s total volume : %s " % (testcase_2, calculate(testcase_2)) 
print "case %s total volume : %s " % (testcase_3, calculate(testcase_3)) 

輸出如下：

D:\PyWorkspace\pool>pool.py 
case [2, 5, 1, 2, 3, 4, 7, 7, 6] total volume : 10 
case [2, 5, 1, 3, 1, 2, 1, 7, 7, 6] total volume : 17 
case [6, 1, 4, 6, 7, 5, 1, 6, 4] total volume : 13 

原文鏈接：http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/

譯文鏈接：http://blog.jobbole.com/50705/