面試題分析：我的推ter技術面試失敗了

英文原文： I Failed a 推ter Interview

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

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

        我不知道你怎么樣，反正我在面試前是很緊張的。我覺得這主要是因為我不想讓面試官認為我很蠢。所以你可以想象，5:20 我清空了桌子，記事本上標注了“推ter 面試，十月 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 問我。“我做的怎么樣？”“還算不錯。你的方法用了兩次遍歷，但有一個更有意思的方法只用一次遍歷。”

        然后我們聊了一小會關于在 推ter 的生活。

        我掛掉電話的那一秒我意識到了我的答案是錯的。

        想想這個輸入：

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

        但是答案應該是在兩個高塔之間只有一池水：

        第二天我把這個問題給我的技術支持看，他是理論計算科學的博士生。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

        翻譯： 伯樂在線 - CuGBabyBeaR    譯文鏈接： http://blog.jobbole.com/50705/