alexlyk314 13 мая в 18:07

Альтернативная математика или математика собеседований

Простой

8 мин

15K

Автор: Лыков А., к.ф.‑м.н., академический руководитель Школы Высшей Математики и ШАДХелпера.

Устройство в крупную IT компанию — непростой и порой длительный процесс. Работодатели в ходе многочисленных собеседований проверяют кандидата со всех сторон. В частности, оценивают его способности решать задачи и технические навыки. В статье мы расскажем о том, как готовиться к прохождению технических собеседований по математике и алгоритмам в IT компании, как в целом проходит процесс устройства на работу. (1)

При устройстве в иностранный хедж‑фонд XQuant на среднюю позицию у вас будет два тестирования по математике и программированию, одно hr собеседование, шесть технических собеседований, три интервью с биг боссами, одно интервью на сошиал фит, часть интервью на английском языке. При устройстве аналитиком в российские IT‑компании (Яндекс, Авито, Тинькофф,...) количество технических собеседований может варьироваться (по нашим оценкам от 2 до 7), но минимум два по алгоритмам и математике пройти придётся.

Для оценки IQ кандидата (2) или того, насколько быстро, оригинально и глубоко он может мыслить, ему предлагают решить задачи по математике, алгоритмам, а также брейнтизеры — головоломки на общую сообразительность. Некоторые задачи стандартные, из школьных и вузовских учебников, но часто на собеседованиях предлагают нестандартные задачи. Такие, которые не встречались ни в школе, ни в вузе (и даже ни в баре и ни на дискотеке). Например, такого характера (3):

В ряд стоят n гномов. На каждом гноме колпак одного из трёх цветов, какого именно он не знает. Гном с номером 1 видит всех гномов с номерами от 2 до n. Гном с номером 2 видит всех с номерами от 3 до n. и т. д.. Каждый гном, начиная с первого пытается угадать цвет своего колпака, озвучивая его вслух, так что все слышат. После первого второй и т. д.. Найти алгоритм для гномов, чтобы максимальное число из них угадало цвет своего колпака (решение в книге [1], Prisoner problem, в статье Андрея Канунникова серия аналогичных задач).
Два города А, Б на расстоянии 1000 км.. Из города А верблюд может перевозить бананы в Б. В городе А есть три тысячи бананов. Верблюд в ходе поездки съедает один банан в 1 км.. Максимальное количество бананов, которое может взять на себя верблюд — 1000 штук. Как перевезти максимальное количество бананов? (решение в книге [2], 1.10).
Дан круговой поезд. Мы можем включать и выключать свет в каждом вагоне и переме‑ щаться по поезду в любом направлении. В начальный момент времени свет во всех вагона как‑то случайной вкл‑выкл.. Нужно придумать алгоритм определения числа вагонов. Оценить его сложность. Предложить алгоритм как можно «лучше». (фольклор, видео разбор от Бориса Трушина).
Нерадивый программист направил указатель конца односвязнго списка в какой‑то элемент списка. Помогите программисту восстановить список. Длина изначального списка неизвестна. В решении можно использовать O(1) памяти (собеседование в гугл, разбор от Александра Рубцова на семинаре ШАДХелпера).

При этом для некоторых компаний неважны прошлые заслуги кандидата. Опыт в построении точных гомологических последовательностей когерентных пучков на схемах, умение анализировать устойчивость разностных схем нелинейных уравнений в частных производных, знание теории некоммутативных колец, эргодической теории, случайных матриц. Всё это не играет ни какой роли и никак не поможет при решении математических задач на собеседованиях. Нужно готовиться к колпакам, верблюдам, поездам. В некоторой мере это оправдано. Компаниям нужны люди, умеющие быстро находить решения в незнакомых условиях. Однако глубокий анализ эффективности текущего формата собеседований — тема отдельной статьи. Интересно отметить в этом контексте исследования гугла десятилетней давности о неэффективности брейнтизеров на собеседованиях.

Однако иногда всё‑таки встречаются задачи, при решении которых знание высшей математики может сильно упростить решение. Пример такой фольклорной задачи:

прямоугольник со сторонами покрывают без наложений конечным числом маленьких прямоугольничков со сторонами параллельными исходному, большому. Известно, что одна из сторон каждого маленького прямоугольника является целым числом. Доказать, что либо , либо является целым числом (фольклор).
Указание.
Рассмотреть реобразование Фурье от индикаторной функции большого прямоугольника.
Решение.
- Обозначим ${\Pi}$ большой прямоугольник, ${\Pi_k}$ маленькие, покрывающие. Тогда по условию имеем равентство
  ${\Pi} = \bigcup_{k} \Pi_k$
  при этом $\Pi_i\cap \Pi_j = \emptyset$ при $i\ne j$ . Для индикаторных функций имеем равенство:
  $\mathbf{1}_{\Pi}(x,y) = \sum_{k} \mathbf{1}_{\Pi_k}(x,y)$
  где индикаторная функция множества определяется равенством:
  $\mathbf{1}_{A}(x,y) = \begin{cases} 1, & (x,y)\in A \\ 0,& (x,y) \notin A \end{cases}.$
  Рассмотрим преобразование Фурье индикаторных функций:
  $\hat{\mathbf{1}}_{\Pi}(u,v) = \int_{\mathbb{R}^2} e^{-2 \pi i (ux+vy) } \mathbf{1}_{\Pi}(x,y) dxdy.$
  Имеем равенства:
  $\hat{\mathbf{1}}_{\Pi}(u,v) = \sum_{k} \hat{\mathbf{1}}_{\Pi_k}(x,y) .$
  Так как одна из сторон каждого прямоугольника ${\Pi_k}$ целая, то
  $\hat{\mathbf{1}}_{\Pi_k}(x,y) = \int_{\mathbb{R}^2} e^{-2 \pi i (ux+vy) } \mathbf{1}_{\Pi_k}(x,y) dxdy = \int_{a_1(k)}^{a_2(k)} e^{-2 \pi i ux }dx \int_{b_1(k)}^{b_2(k)} e^{-2 \pi i vy } dy =0 ,$
  где мы обозначили прямоугольник $\Pi_k = [a_1(k),a_2(k)]\ \times [b_1(k),b_2(k)]$ . Следовательно, $\hat{\mathbf{1}}_{\Pi}(u,v)=0$ , что, как легко видеть, влечёт то, что одна из сторон большого прямоугольника целая.

Нашего знакомого, кандидата физико‑математических наук, на собеседовании попросили найти вероятность того, что сумма очков на двух симметричных брошенных костях будет больше семи. При этом, в момент прохождения собеседования он преподавал на мехмате МГУ теорию вероятностей. На его замечание об этом интервьюеры сказали, что «не дочитали резюме до конца, так как оно длинное», и перешли к следующей задаче. Такие комичные случаи скорее исключение, но встречаются. Пишите в комментариях свои забавные истории о прохождении или проведении собеседований.

Встречаются более привычные на вид задачи, но требующие нестандартного подхода.

Игра состоит в подбрасывании двух игральных костей. Первый игрок ставит на то, что сумма выпавших очков будет 12. Второй игрок ставит на то, что сумма очков два раза подряд будет равна 7. Найти вероятность победы первого игрока (решение в книге [1], Dice question)
Функция возрастает. Доказать, что уравнения и эквивалентны (задачи со вступительных экзаменов в ШАД).

Нужно иметь в виду, что задачи со вступительных экзаменов в ШАД нередко дают на собеседованиях. Проект ШАДХелпер собрал задачи и решения всех лет у себя на сайте. Ими можно пользоваться как для подготовки, так и для проведения собеседований.

По нашим оценкам большая часть людей, успешно проходящих собеседования, видели похожие «нестандартные» задачи ранее, в школе, в вузе, слышали от знакомых. Возникает вопрос можно ли научиться решать нестандартные задачи или это особый дар? Конечно, можно, прикладывая достаточно усилий. Опишем возможные траектории подготовки.

Самостоятельная подготовка. Процесс подготовки к алгоритмам состоит в прорешивании задач с литкода. По нашим оценкам и опросам нужно решить до 50 задач среднего уровня и непрерывно тренироваться перед собеседованием не менее 2–3 недель для успешного прохождения почти в любую IT компанию. Для подготовки к математике можно использовать книги [1,2,3,4]. Дополнительно посоветуем сборник задач со вступительных экзаменов в ШАД. Для успешного прохождения технических собеседований по математике достаточно будет усердно позаниматься 2–3 недели, прорешивая задачи из указанных книг. Конечно, наши оценки справедливы при условии, что у Вас неплохой «стартовый уровень».
Курсы. На настоящий момент в рунете существует достаточно мало курсов по подготовке к кружковой математике (или математике собеседований) для взрослых. Один из таких курсов подготовила команда Школы Высшей Математики и ШАД Хелпера. Авторы и преподаватели этого курса — кандидаты физико‑математических наук, имеющие опыт в прохождении и проведении собеседований. Отметим, однако, что указанный курс имеет больше фокус на кружковую математику. Тем временем, на некоторые позиции в IT компании часто задают нестандартные задачи по высшей математике. Возможно, у команды Школы Высшей Математики будут новые курсы в этом направлении.

Вывод. Процесс собеседований напоминает спортивные соревнования. К нему можно и нужно готовиться аналогичным образом — регулярно прокачивать свою логико‑математическую сообразительность, поднимать IQ, решая соответствующие задачи. В целом, при правильной подготовке можно раскачать свой IQ достаточно сильно и пройти в любую IT компанию. Но нужно ли Вам это? Сделает ли это Вас счастливее? Важный вопрос, про который не нужно забывать.

Успехов на интервью и собеседованиях!

(1). О неразглашении. Автор статьи проходил (и проводил сам) большое количество собеседований в разные компании. С целью ненарушения прав работодателей название некоторых компаний изменены. Конфиденциальная информация, полученная автором статьи в ходе прохождения собеседований и интервью, в статье не разглашается.

(2). Об IQ тестах. Существуют как сторонники, так и ярые критики IQ тестов (см. книгу Насима Талеба). Про историю и текущее положение интересно рассказано на видео Дерека Мюллера (Veritasium). Наиболее глубоко и ясно, на наш взгляд, про IQ написано в книге Гоулмана про эмоциональный интеллект. Из этой книги «в центре старых концепций IQ помещался узкий диапазон лингвистических и математических способностей. Высокий балл IQ прямо пророчил успех в школе или преподавательской деятельности, но на него все меньше следовало полагаться по мере того, как жизненные пути отклонялись от академической стези». Важно отметить, что IQ это лишь одна из многих составляющих множественного интеллекта человека. IT компаниями и университетами формируется и подстёгивается спрос именно на эту составляющую, так как перед ними стоят соответствующие задачи. Однако для человека важнейшая задача — преуспеть в жизни. Пути по которым решают свои задачи человек и IT компании различаются. В указанной книге Гоулмана есть ссылка на исследование, в котором, ученые приходят к почти очевидному выводу: главная составляющая успеха в жизни человека — социальный интеллект. Всё должно быть в гармонии. Гармоничное сочетание всех видов интеллекта: эмоционального, социального, академического (IQ) залог счастливой человеческой жизни.

(3). О том как собирался материал для статьи. Материал, изложенный в статье, основан на собеседованиях и интервью автора и его знакомых, проводившихся в последние два года. Публикуются только те задачи, которые доступны в открытых источниках. Оригинальные задачи с собеседований в этой статье не приводятся. К слову нужно заметить, что оригинальных задач практически не встречалось.

Ссылки

Xinfeng Zhou, “A practival guide to quantitative finance interviews”, 2008.
T. Crack, “Heard on the street: quantitative questions from Wall Street Job Interviews”, 2014
А. Я. Канель‑Белов, А. К. Ковальджи, «Как решают нестандартные задачи», 2008.
С. А. Генкин, И. В. Итенберг, Д. В. Фомин, «Ленинградские математические кружки», 2008.
Н. Талеб, «Чёрный лебедь», 2007
Д. Гоулман, «Эмоциональный интеллект. Почему он может значить больше, чем IQ?», 1995

Теги:

Хабы:

Альтернативная математика или математика собеседований

Публикации

Истории

Ближайшие события