确认回亚马逊实习的deadline是10月28日，但朋友丹尼尔说服我如果被推特录用，就不用参加任何面试了.所以我去推特面试了。首先，他们要求我在一个小时内完成两道编程能力题。有趣的问题：“这是回文吗？”和“计算二维阵列的平衡点”。我不是很自信，但Twitter招聘人员朱迪给我发了电子邮件，并安排了周三5:30的电话筛选。不知道你怎么想，反正面试前很紧张。我觉得主要是不想让面试官觉得我傻。所以你可以想象，在5:20，我清理了我的桌子，记事本上写着“Twitter采访，10月23日，星期三”，还有两支削尖的绘图铅笔。然后5:30到了，我开始盯着手机看。5:35我用谷歌搜索“加利福尼亚时间”以确保我的时差计算是正确的。没问题：谷歌说现在是太平洋标准时间2:30，美国东部标准时间5:30。5点48分，我给Judy发了邮件，让她看一看。10分钟后，我接到了来自旧金山的电话。朱迪为搞砸了而道歉，并告诉我贾斯汀现在可以采访我了。深吸一口气“太好了，开始吧！”贾斯汀也对调度错误表示歉意，并迅速潜入编程问题：“看下面这张图片”“在这张图片中我们有不同高度的墙。这张图片是由一个整数数组表示的，数组中的每个数字是墙的高度。上图可以表示为数组[2,5,1,2,3,4,7,7,6]""如果开始下雨，那么中间的水坑能积多少水墙能撑得住吗？”》体积是以1×1的方格为单位计算的，所以上图中，1下面和左边的下标会漏掉，7下面和右边的下标也漏了，剩下的就是一滩水1和6，卷10"//好奇读者的旁注：我在底部包含了正确答案的要点。您可以继续阅读而不必担心剧透。:)我要做的第一件事是弄清楚给定的两个下标之间有多少水。这个过程和微积分很像，所以我马上想起来可以用最大值。其实在上图中，下标2上面的水被周围的两个最大下标1和6所约束。我把我的想法说成是：“如果我们找到所有的最大值，然后在它们之间填充。这行得通吗？？”“好吧，这应该行得通”贾斯汀回答道。我将为此解决方案编写代码。然后Justin让我提供一组测试用例。我们讨论的所有测试用例似乎也没有问题。“你有什么问题想问我吗？”贾斯汀问我。“我怎么样？”“不错。你的方法用了两遍，不过还有一种更有趣的方法，只用了一遍。”然后我们在推特上聊了聊生活。挂断电话的那一刻，我意识到我的回答是错误的。想想这个输入：我的答案计算最大值之间的水，就像这样。但答案应该是两座塔之间只有一个水池：第二天我把这个问题展示给我的技术支持，一个理论计算科学博士生。40分钟后，他仍然卡在这个问题上。今天早上我醒来时口臭，灵感一闪而过。答案简单而美丽。现在我问自己：我从这件事中学到了什么？客观地说-不多。我很遗憾面试官没有问我正确的问题来引导我朝着正确的方向思考。我不知道为什么贾斯汀在我的回答实际上不正确时告诉我“这应该有效”。我知道答案中的问题应该会出现在他要求的测试用例中，但由于我没有考虑算法，所以我不可能想到测试它。我与亚马逊签订了一份明年夏天工作的合同，对此我感到很兴奋。同时，我不禁要问“如果我通过了面试呢？”以下是答案的摘要。逻辑是这样的：如果我们从左到右遍历列表，每个下标的水量至多是目前为止最高的数。这意味着如果我们知道右边有一个相等或更大的水，我们就可以知道还剩下多少水。反向遍历时也是如此：如果我们知道左边的数比右边的数大，我们装水就没有问题了。基于这个思路，一个解决方案是：先找到***值，从左边遍历到***值，再从右边遍历到***值。这个方法需要两次遍历：一次是找到***值，一次是分成两次子遍历。一次遍历的方法避免了通过将两端的指针相互移动来寻找最大值。如果（左指针找到的左指针左边的最大值）小于（右指针找到的右指针右边的最大值），则将左指针向右移动一位。否则右指针向左移动一位。重复这个过程，直到两个指针相遇。（解释起来比较麻烦，但是代码很简单）译者注：这是笔者最后用python实现的算法：defcalculate(testcase):max_l=p_l=0max_r=p_r=len(testcase)-1puddle_volumes=[]volume=0whilep_r>p_l:iftestcase[max_l]
