Geekly Articles each Day
📜 ⬆️ ⬇️

How I filled up an interview on Twitter

image


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

At first I was asked to solve a couple of questions with Codility , giving everything for an hour. The questions were 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 resulting decisions, but soon Judy sent me a letter inviting me to a telephone interview on Wednesday at 17:30.

I don’t know about you, but I’m usually very nervous about the interviews - I’m always afraid that the interviewer might think that I’m not smart enough. Therefore, on Wednesday at 5:20 pm, two sharpened pencils and a notebook were already on my empty table, and I myself was on full alert ... It was 5:30 pm, and nothing happened. After waiting another fifteen minutes, I went to Google to find out if I calculated the time difference correctly and what time it was in California. There was no mistake - I unsubscribed to Judy's post, asking her to deal with the situation.
')
Ten minutes later, the bell rang from San Francisco. Judy apologized for the confusion and told me that Justin could interview me right now.

Deep breath

“Great, I'm ready!”

Justin also apologized for a mistake in the schedule and immediately switched to programming.

Take a look at the following picture:

image

In this picture we have walls of different heights. The image is represented by 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 (the value on the Y axis). The picture above corresponds to the array [2,5,1,2,3,4,7,7,6].

Now imagine: it's raining. How much water will gather 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 that is located to the left of point 1 spills out. Water to the right of point 7 is also spilled. We are left with a puddle between 1 and 6 - so the resulting volume of water is 10.

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

The first thing 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 mind — in particular, the idea of ​​searching for local maxima might be useful to me. Indeed, in the previous picture, the water above point 2 is bounded by the smaller of the two maxima surrounding it - at points 1 and 6.

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

"Yes, that should work," Justin replied.

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

"Any more questions for me?" Justin asked. “Well, and 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 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 the local maxima and looked like this:

image

But the result was supposed 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 thinking, he also failed.

But this morning, after waking up, it hit me - the decision turned out to be beautiful and simple.

I ask myself: what did I learn in the end? In fact - a little. I am a little upset that the interviewer did not ask me a guiding 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 requested to carry out, but since I missed one important point during the development of the algorithm, I could not guess it.

Next summer I go to work at Amazon, which can not but make me happy, but the question “what if?” Still does not leave me.


The 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;
	}
}

:

, , . , , - - , , . : , , , .

, : , . : , — .

, «» . , , , . , . , . ( , )

: Q & What?.

Source: https://habr.com/ru/post/200190/

More articles:


All Articles