До 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?.
Автор: HotWaterMusic
