面試題分析：我的Twitter技術面試失敗了
確認我返回亞馬遜實習的截止期限是10月28日，但是我的朋友Daniel說服我如果我被Twitter錄取，我就不用參加任何面試了。所以我去Twitter面試了。
首先他們讓我在一個小時內完成兩道編程能力的問題。問題很有意思：“這是回文（譯注：正著讀和倒著讀是一樣的）嗎？”以及“計算二維數組的平衡點”。我不是很有自信，但是Twitter的一個招聘人員Judy給我發了email并安排了周三5:30的電話甄選。
我不知道你怎么樣，反正我在面試前是很緊張的。我覺得這主要是因為我不想讓面試官認為我很蠢。所以你可以想象，5:20我清空了桌子，記事本上標注了“Twitter面試，十月23日，周三”，還有為涂畫準備的兩只削尖的鉛筆。然后5:30到了，我開始盯著我的電話。
5:35我去google了一下“加利福尼亞時間”來確定我的時差計算是正確的。沒問題：Google說是太平洋標準時間2:30，美國東部時間5:30。
5:48我給Judy發了email，請她看下情況。10分鐘后我接到了一個來自舊金山的電話。Judy對她搞砸了這件事情道歉，并告訴我Justin現在可以面試我。
深呼吸
“棒極了，我們開始吧！”
Justin同樣對這個行程安排錯誤道歉，并很快深入到編程問題中：
“看下面這個圖片”
“在這個圖片里我們有不同高度的墻。這個圖片由一個整數數組所代表，數組中每個數是墻的高度。上邊的圖可以表示為數組[2,5,1,2,3,4,7,7,6]”
“假如開始下雨了，那么墻之間的水坑能夠裝多少水呢？”
“以1×1的方塊為單位計算容積。所以，在上邊的圖中下標為1以左的都會漏掉。下標7以右的也會漏掉。剩下的只有在1和6之間的一坑水，容積是10”
// 給好奇的讀者的旁注：我在底部附上了正確答案的要點。你可以繼續閱讀而不怕劇透。:)
我首先試圖做的事情是搞清楚在給定的兩個下標之間到底有多少水。這個過程跟微積分很像，所以我立即想起可以用極大值。實際上在上邊的圖片中，下標2以上的水是由周圍的兩個極大值下標1和6約束的。
我把我的想法說了出來：“如果我們找到所有的極大值，然后在他們之間填水。這樣做有用么？”
“恩，這樣應該有用” Justin回復。
我去給這個解答寫代碼。然后Justin讓我提供一套測試用例。我們討論的所有測試用例似乎也挺好。
“你有問題問我嗎？”Justin問我。“我做的怎么樣？”“還算不錯。你的方法用了兩次遍歷，但有一個更有意思的方法只用一次遍歷。”
然后我們聊了一小會關于在twitter的生活。
我掛掉電話的那一秒我意識到了我的答案是錯的。
想想這個輸入：
我的答案計算的是極大值之間的水，就像這樣。
但是答案應該是在兩個高塔之間只有一池水：
第二天我把這個問題給我的技術支持看，他是理論計算科學的博士生。40分鐘之后他還是卡在這個問題上。
今天早上我帶著口臭和靈光一閃起床。答案是簡單而漂亮的。
現在我捫心自問：在這件事我學到了什么？客觀地說——不多。對于面試官沒有問我正確的問題來引導我向正確的方向思考，我 很難過。當我的解答實際上不正確的時候，我不知道為什么Justin告訴我“這應該有用”。我知道解答中的問題應該在他要求的測試用例中顯示出來，但既然 我在思考算法的時候沒有考慮到，我就不可能想到要測試它。
我跟亞馬遜簽了合約明年夏天上班，并且對此我很興奮。同時，我也禁不住問一句“如果我通過了面試會怎么樣？”
這里是答案的概要。
邏輯如下：
如果我們從左至右遍歷列表，每個下標水的量最多是到現在為止***的數。這表示如果我們已知右邊有相等或更大的，我們可以知道存下的水有多少。反向遍歷的時候也一樣：如果我們知道左邊有比右邊***的數更大的，我們裝水是毫無問題的。
基于這個想法，一個解決方法是：先找到***值，從左遍歷到***值，然后從右遍歷到***值。這個方法需要兩次遍歷：一次找到***值，另一次分成了兩個子遍歷。
一次遍歷的方法通過兩端的指針相向移動避免了尋找***值。如果（左指針找到的左指針以左的***值）小于（右指針找到右指針以右的***值），將左指針向右移動一位。否則右指針向左移動一位。重復過程直到兩個指針相遇。（解釋起來很麻煩，但是代碼很簡單）
譯者注：
這是我用python實現的作者的最終算法：
- 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個不同的測試用例,其中兩個是文中給出的：
- 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/
