День триста тридцать второй. #ЗадачиНаСобеседовании
Встречаю много вопросов на тему, чего ждать на собеседовании, к чему готовиться, что нужно знать и т.п. Поскольку лично я работаю в одной компании уже 12 лет, то считать себя экспертом по собесам не могу. Поэтому лучше сошлюсь на хорошее видео на эту тему от АйТиБороды.
А в этом посте хотел бы привести одну из практических задач. Не знаю, как у нас, а на собеседованиях в заграничных «ИТ-гигантах» умение решать задачи ценится больше, чем просто знание технологий. Возможно, это и правильно. Как я упоминал ранее, я нашёл канал одного парня, его зовут Клемент Михалеску, который занимается интервью кандидатов в Гугле. Так вот, в одном видео (не спешите смотреть, чтобы не заспойлерить) мне понравилась задача, которую предлагают решить кандидату на собеседовании.
Дана коллекция точек на плоскости с координатами (x, y). См. рисунок ниже (он немного кривоват, но суть, думаю, понятна). Для простоты допустим, что все координаты целочисленные. Нужно написать функцию, которая будет вычислять количество прямоугольников, образованных этими точками. Очевидные правила:
- прямоугольник должен иметь 4 точки в углах,
- ненулевые длину и ширину,
- прямоугольники, образованные четырьмя одинаковыми точками A,B,E,D (см. рисунок) считаются как один (то есть ABED = BEDA = EDBA и т.п. – все считать за 1).
Итак, что мне понравилось в описании процесса интервью.
Во-первых, интервью длится около часа, и никто не ждёт от вас, что вы тут же напишете идеально правильный, компилирующийся и работающий код. Тем более, что на интервью даётся листок бумаги (документ Google Docs в видео), а не IDE. Интервьюеру интересен ход ваших мыслей. То есть вам даётся задание, вы начинаете рассуждать вслух, возможно записывать какой-то псевдокод. Хороший интервьюер (как в видео) будет рассуждать вместе с вами и задавать наводящие вопросы или корректировать, если вы полезете не в ту степь. Точно так же, как впоследствии вы будете работать и решать задачи в команде.
Во-вторых, сначала вам дают упрощённый вариант задачи. В данном случае допустим, что нужно посчитать прямоугольники, стороны которых параллельны осям координат. То есть пока мы не будем считать прямоугольник BDHF. Кстати, в видео «кандидат» блестяще с этим справляется, можете посмотреть решение до 20й минуты.
Кроме собственно решения интервьюер попросил пройти его по шагам, чтобы убедиться в правильности и понять ход мыслей самому, а также оценить «стоимость» решения как по времени, так и по занимаемой памяти. Вот это тоже нужно уметь делать.
Ну а дальше, если интервьюер действительно хочет оценить силу кандидата, то даст ему попробовать решить и усложнённый вариант. Собственно, Клемент поясняет далее во врезке, что от кандидата не ждут, что он сразу, прямо во время интервью, решит усложнённый вариант (чаще всего это не реально). Интервьюеру интереснее посмотреть на мыслительный процесс кандидата и то, как он справляется с действительно сложными задачами.
Интересно, что я практически уверен, что решение упрощённого варианта в видео правильное, а вот до решения усложнённого варианта, как мне показалось, они так и не дошли.
Итак, теперь нам нужно посчитать все возможные прямоугольники.

У меня есть теория решения, в которой я более-менее уверен, но пока не проверял. Приглашаю всех предлагать варианты решения в чате.