English Title: I Failed a Twitter Interview
The deadline for me to confirm my return to Amazon as an intern was October 28, but my friend Daniel convinced me that if I got accepted by Twitter, I wouldn't need to go through any more interviews. So, I decided to attend the Twitter interview.
First, they asked me to solve two programming problems within an hour. The questions were interesting: "Is this a palindrome (a word or phrase that reads the same backward as forward)?" and "Find the balance point in a two-dimensional array." I wasn't very confident, but a recruiter from Twitter named Judy sent me an email and scheduled a phone screening for 5:30 PM on Wednesday.
I don't know about you, but I get really nervous before interviews. I think it's mainly because I don't want the interviewer to think I'm stupid. So, at 5:20 PM, I cleared my desk, wrote "Twitter Interview, October 23, Wednesday" on my notepad, and prepared two sharpened pencils for sketching. Then, at 5:30, I started staring at my phone.
At 5:35, I googled "California time" to double-check my time zone calculations. Everything was fine: Google said it was 2:30 PM Pacific Standard Time and 5:30 PM Eastern Time.
At 5:48, I emailed Judy to check the situation. Ten minutes later, I received a call from San Francisco. Judy apologized for the mix-up and informed me that Justin could now conduct the interview.
I took a deep breath.
"Great, let's get started!"
Justin also apologized for the scheduling mishap and quickly moved into the programming question:
"Look at the image below."
"In this image, we have walls of varying heights. This image is represented by an integer array where each number corresponds to the height of a wall. The figure above can be represented as the array [2,5,1,2,3,4,7,7,6]."
"If it starts raining, how much water can be trapped between the walls?"
"The volume is measured in 1x1 square units. In the image above, everything to the left of index 1 will drain away, and everything to the right of index 7 will also drain. The only water retained is the pool between indices 1 and 6, with a volume of 10."
_________
// For curious readers: I've included the key points of the correct solution at the bottom. You can continue reading without worrying about spoilers. :)
_________
I first tried to determine how much water could be trapped between two given indices. The process reminded me of calculus, so I immediately thought of using local maxima. In fact, in the image above, the water above index 2 is constrained by the two surrounding local maxima at indices 1 and 6.
I verbalized my thoughts: "If we find all the local maxima and fill the water between them, would that work?"
I went ahead and coded the solution. Then Justin asked me to provide a set of test cases. All the test cases we discussed seemed to work fine.
"Do you have any questions for me?" Justin asked. "How am I doing?" "Not bad. Your method uses two passes, but there's a more interesting way that uses just one pass."
We then had a brief chat about life at Twitter.
The moment I hung up, I realized my answer was wrong.
Consider this input:
My solution calculated the water between the local maxima like this.
But the correct answer should show only one pool of water between the two tall towers:
The next day, I showed this problem to my technical support, who is a Ph.D. student in theoretical computer science. After 40 minutes, he was still stuck on it.
This morning, I woke up with bad breath and a sudden realization. The solution is simple and elegant.
Now I reflect on what I learned from this experience. Objectively speaking—not much. I was upset that the interviewer didn't ask the right follow-up questions to guide me toward the correct direction. I don't understand why Justin told me "this should work" when my solution was actually incorrect. I know the issue with my approach should have been revealed in the test cases he requested, but since I hadn't considered it while designing the algorithm, I couldn't have anticipated needing to test for it.
I signed a contract with Amazon to start working next summer, and I'm excited about it. Still, I can't help but wonder, "What if I had passed the interview?"
Here’s a summary of the solution.
The logic is as follows:
If we traverse the list from left to right, the amount of water at each index is determined by the maximum value encountered so far. This means that if we know there's a wall to the right that's equal to or larger than the current maximum, we can calculate the trapped water. Similarly, when traversing from right to left, if we know there's a taller wall to the left, we can confidently calculate the trapped water.
Based on this idea, one solution is: first find the maximum value, then traverse from the left to the maximum, and then from the right to the maximum. This method requires two passes: one to find the maximum and another split into two sub-traversals.
The single-pass method avoids finding the maximum by moving two pointers towards each other. If the maximum value found to the left of the left pointer is less than the maximum value found to the right of the right pointer, move the left pointer one step to the right. Otherwise, move the right pointer one step to the left. Repeat until the two pointers meet. (It's tricky to explain, but the code is simple.)
Translator's note:
Here is my Python implementation of the author's final algorithm:
```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_l]:
max_l = p_l
else:
volume = volume + (testcase[max_l] - testcase[p_l])
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])
return volume
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)))
```
Output:
```
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
```
Translation: BoLe Online - CuGBabyBeaR
Translated article link: http://blog.jobbole.com/50705/