Как я завалил собеседование в Twitter

До 28 октября я должен был принять решение, буду ли я работать в Amazon по окончанию стажировки. Оставалось совсем немного времени, но мой друг Дэниел убедил меня, что если я попробую попасть в Twitter, то как раз успею пройти все интервью. Я не смог устоять.

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.

Не знаю, как вы, а я обычно сильно нервничаю перед собеседованиями — всегда боюсь, что интервьюер может подумать, что я недостаточно сообразителен. Поэтому в среду к 17:20 на моем опустевшем столе уже лежали 2 остро заточенных карандаша и блокнот, а сам я был в полной боевой готовности… Наступило 17:30, и ничего не произошло. Прождав еще пятнадцать минут, я полез в Google выяснить, правильно ли рассчитал разницу во времени и который час в Калифорнии. Ошибки не было — я отписался на почту Джуди, попросив ее разобраться с ситуацией.

Спустя десять минут раздался звонок из Сан-Франциско. Джуди извинилась за возникшую путаницу и сказала мне, что Джастин может провести со мной интервью прямо сейчас.

Глубокий вздох

«Отлично, я готов!»

Джастин также извинился за ошибку в расписании и сразу перешел к программированию.

Взгляните на следующую картинку:

На этой картинке у нас есть стены различной высоты. Картинка представлена массивом целых чисел, где индекс — это точка на оси X, а значение каждого индекса — это высота стены (значение по оси Y). Картинке выше соответствует массив [2,5,1,2,3,4,7,7,6].

Теперь представьте: идет дождь. Сколько воды соберется в «лужах» между стенами?

Мы считаем единицей объема воды квадратный блок 1х1. На картинке выше все, что расположено слева от точки 1, выплескивается. Вода справа от точки 7 также прольется. У нас остается лужа между 1 и 6 — таким образом, получившийся объем воды равен 10.

Для самых нетерпеливых

Ссылка на гист с правильным решением задачи, которое подробнее разъясняется в конце поста. Остальные могут спокойно читать дальше — спойлеров не будет 🙂

Первым делом я попробовал определить, сколько воды мы будем иметь в каждом из индексов. На ум сразу пришла связь с математическим анализом и интегралами, — в частности, идея поиска локальных максимумов могла бы мне пригодиться. И действительно, на предыдущей картинке вода над точкой 2 ограничена меньшими из двух окружающих ее максимумов — в точках 1 и 6.

Я вслух произнес: «Что, если мы найдем все локальные максимумы и посчитаем заполненное водой пространство между ними — это сработает?»

«Да, это должно сработать», ответил Джастин.

После такого ответа я решил, что пошел в верном направлении, и закодил свое решение. Следом Джастин попросил меня написать несколько тестов, что я также проделал. Все тесты, о которых мы говорили, вроде бы отработали.

«Будут еще какие-либо вопросы ко мне?», спросил Джастин. «Ну и как я вам?» «Достаточно неплохо, хотя ваше решение делает 2 прохода, но есть другой интересный алгоритм, который делает всего один проход».

Затем мы немного пообщались на тему жизни в Twitter.

И, в тот самый момент, когда я повесил трубку, я вдруг понял: мое решение было неверным.

Возьмем следующие входные данные:

Мое решение искало всю воду между локальными максимумами и выглядело следующим образом:

Но результатом должна была быть одна «лужа» между двумя высокими башнями:

На следующий день я показал эту задачу знакомому аспиранту, занимающемуся теоретическим computer science. После 40 минут размышлений у него также ничего не получилось.

Но сегодня утром я после пробуждения меня осенило — решение оказалось красивым и простым.

Я спрашиваю себя: чему я научился в итоге? На самом деле — немногому. Я слегка расстроен из-за того, что интервьюер не задал мне направляющего вопроса. Я не знаю, почему Джастин сказал мне, что это «должно сработать», когда на самом деле мое решение было неправильным. Знаю, что это должно было вылезти в тестах, которые он просил провести, но поскольку я упустил один важный момент во время разработки алгоритма, то и протестировать его не смог догадаться.

Следующим летом я иду работать в Amazon, что не может меня не радовать, но вопрос «а что, если бы?» по-прежнему не оставляет меня.

Правильное решение: gist.

/* 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?.