How I Failed Twitter Interview

Original author: Michael Kozakov
  • Transfer
image


Until October 28, I had to decide whether I would work at Amazon at the end of the internship. There was very little time left, but my friend Daniel convinced me that if I try to get on Twitter, I will just have time to go through all the interviews. I could not resist.

At first I was asked to solve a couple of issues with Codility , giving everything about everything for an hour. The questions came of medium interest (“is the word an anagram of a palindrome” and “count the number of saddle points in a two-dimensional array”). I was not too sure about the solutions, but soon Judy sent me a letter inviting me to do a telephone interview on Wednesday at 17:30.

I don’t know about you, but I usually get very nervous before the interviews - I’m always afraid that the interviewer might think that I’m not smart enough. Therefore, on Wednesday at 17:20 on my empty table were already 2 sharpened pencils and a notebook, and I myself was in full combat readiness ... It was 17:30, and nothing happened. After waiting another fifteen minutes, I went to Google to find out if I correctly calculated the time difference and what time it was in California. There was no mistake - I unsubscribed to Judy's mail, asking her to deal with the situation.

Ten minutes later, a call came from San Francisco. Judy apologized for the confusion and told me that Justin could interview me right now.

Deep sigh

"Great, I'm ready!"

Justin also apologized for the schedule error and immediately proceeded to programming.

Take a look at the following picture:

image

In this picture we have walls of various heights. The picture is an array of integers, where the index is a point on the X axis, and the value of each index is the height of the wall (value along the Y axis). The image above corresponds to an array [2,5,1,2,3,4,7,7,6].

Now imagine: it's raining. How much water will be collected in the “puddles” between the walls?

image

We consider the unit of water volume to be a 1x1 square block. In the picture above, everything located to the left of point 1 splashes out. Water to the right of point 7 will also spill. We have a puddle between 1 and 6 - so the resulting volume of water is 10.


For the most impatient
Link to the histogram with the correct solution to the problem, which is explained in more detail at the end of the post. The rest can read on easily - there will be no spoilers.


First of all, I tried to determine how much water we will have in each of the indices. A connection with mathematical analysis and integrals immediately came to my mind - in particular, the idea of ​​searching for local maxima could be useful to me. Indeed, in the previous picture, the water above point 2 is limited by the smaller of the two maxima surrounding it - at points 1 and 6.

I said aloud: “What if we find all the local maxima and calculate the space filled between them between the water - will this work?”

“Yes, that should work,” Justin answered.

After such an answer, I decided that I had gone in the right direction and coded my decision. Next, Justin asked me to write some tests, which I also did. All the tests that we talked about seem to have worked.

“Will there be any more questions for me?” Justin asked. "Well, how am I to you?" "Not bad enough, although your decision makes 2 passes, but there is another interesting algorithm that makes only one pass."

Then we talked a bit about life on Twitter.

And, at that very moment when I hung up, I suddenly realized: my decision was wrong.

Take the following input:

image

My solution looked for all the water between local maxima and looked like this:

image

But the result was to be one “puddle” between two high towers:

image

The next day I showed this task to a familiar graduate student in theoretical computer science. After 40 minutes of reflection, he also failed.

But this morning, after waking up, it dawned on me - the solution turned out to be beautiful and simple.

I ask myself: what did I learn as a result? In fact, a little. I am slightly upset that the interviewer did not ask me a directing question. I don’t know why Justin told me that this “should work” when in fact my decision was wrong. I know that this should have come out in the tests that he asked for, but since I missed one important point during the development of the algorithm, I couldn’t guess it.

Next summer I’m going to work at Amazon, which cannot but please me, but the question is “what if?” still does not leave me.



Correct solution: gist .
Look
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6}; 
		System.out.println(calculateVolume(myIntArray));
	}
	public static int calculateVolume(int[] land) {
		int leftMax = 0;
		int rightMax = 0;
		int left = 0;
		int right = land.length - 1;
		int volume = 0;
		while(left < right) {
			if(land[left] > leftMax) {
				leftMax = land[left];
			}
			if(land[right] > rightMax) {
				rightMax = land[right];
			}
			if(leftMax >= rightMax) {
				volume += rightMax - land[right];
				right--;
			} else {
				volume += leftMax - land[left];
				left++;
			}
		}
		return volume;
	}
}

The logic is as follows:

If we go through the list from left to right, the amount of water in each index will be no more than the absolute maximum that we find in advance. This means that if we know for sure that there is something greater or equal somewhere on the right, then we can determine exactly how much water we can hold without splashing out. The same is true for the opposite direction: if we know that we have found the left wall above the highest in the right part, this means that we can confidently fill it with water.

So, now the solution is as follows: find the absolute maximum, then go left to the maximum and then go right to the maximum. This solution requires two passes: one to search for the maximum, and the second - divided into two parts.

The solution in the given histogram works in one pass, avoiding the search for a maximum by the passage of two "pointers" towards each other from opposite ends of the array. If the largest value found to the left of the left pointer is less than the largest value found to the right of the right pointer, then we move the left pointer one index to the right. Otherwise, move the right pointer one index to the left. Repeat until the two pointers intersect. (It sounds confusing in words, the code is actually very simple)

Original post: Q & What? .

Also popular now: