Собеседование в Яндекс: театр абсурда :/
Привет, хабр!
В прошлой статье меня знатно разбомбили в комментариях, где-то за дело, где-то я считаю, что нет. Так или иначе, я выжил, и у меня есть чем с вами поделиться >:)
Напомню, что в той статье я рассказывал, каким я вижу идеальное собеседование и что я нашёл компанию, которая так и делает — и я туда прошёл, хотя это был адский отбор. Я, довольный как слон, везде отметил, что я не ищу работу, отовсюду удалился и стал работать работу.
Как вы думаете, что делают рекрутеры, когда видят «Alexandr, NOT OPEN FOR WORK»? Правильно, пишут «Алексей, рассматриваете вариант работать в X?» Я обычно игнорирую это, но тут мне предложили попытать счастья с Яндекс.Лавкой, и я не смог пройти мимо — интересно было, смогу ли я устроиться куда-нибудь, когда введут великий российский файерволл. К тому же за последние 3 года я проходил только два интервью, и мне показалось, что я не в теме, что нынче требуется индустрии. Блин, я оказался и вправду не в теме. И вы, скорей всего, тоже — об этом и статья.
Короче, я согласился — буду продавать дошики и похмелье!
Мне назначили дату интервью, и также прислали методичку, чтобы я понимал, что меня ждёт и как готовиться. Чтобы ничего не заспойлерить, я замазал квадратиками важную информацию.
Вы тоже заметили «вопросы на C++» в методичке для питониста? Не то чтобы я знал C++, но в институте проходили, авось что-нибудь да вспомню на интервью.
Тут что-то написано про leetcode, но я человек ответственный, поэтому к интервью не готовлюсь. Это кстати я не шуткую, реально: если вы ответственный человек, ты вы, когда предстаёте перед компанией, отвечаете за то, что вы заявляете как ваши умения. Можно выучить типовые вопросы и даже казаться умнее и опытнее, чем есть, но по факту это переобучение на тестовых заданиях/вопросах. Ребята из ml поймут. Поэтому я гол как сокол и чист как стёклышко или что там ещё блин, если что-то знаю — скажу, что-то не знаю — скажу что не знаю. Таким образом работодатель знает, что он покупает и сколько ещё нужно вложить в меня средств на обучение. Все счастливы.
Интервью 1
Так вот, назначили мне собеседование, и в назначенный час я был в зуме. Сразу скажу, что все — и рекрутер, и интервьюеры — вежливые и приятные в общении люди, тут я подкопаться не могу, ну разве что иногда они слишком корректные: спрашивают, ничего, если будет стажёр-наблюдатель и если они будут делать заметки в ходе интервью. На какой-то из итераций мне даже стало интересно, что будет, если я скажу «нет, нельзя», но именно тогда меня не спросили, так что предлагаю вам проверить самим.
Мне кинули ссылку на Яндекс.Блокнот (это я его так называю, вообще он Яндекс.Код и живёт тут) — там можно вместе писать текст и включать подсветку синтаксиса. Запускать там, естественно, ничего нельзя, потому что это уже реализовано в coderpad, а он недостоин Яндекса. Ну ок, мне на самом деле проще, потому что написать код и написать хотя бы запускаемый код — это очень разные вещи. Минус — нельзя прогнать тесты и вообще тут как битва самураев: ваша правда против правды рекрутера, один доказывает, почему работает, другой — почему нет.
Итак, о чём вас спросит Яндекс на интервью? Выберите один правильный вариант:
1) прежний опыт
2) текущие проекты
3) как вы будете решать вот эту бизнес-задачу
4) как решить вот эту алгоритмически задачу без стандартной библиотеки
Именно так! Так давайте решим эту алгоритмическую задачу. Помните, у нас нет collections.Counter, itertools.groupby, set.intersection, вообще случилась война и стандартная библиотека питона погибла, оставив после себя int, bool, for, if и while. Ну ок, хотят проверить знание каких-то базовых вещей.
Задача 1
Даны два массива: [1, 2, 3, 2, 0] и [5, 1, 2, 7, 3, 2]
Надо вернуть [1, 2, 2, 3] (порядок неважен)
Фактически нам нужно вернуть пересечение множеств, но с повторением элементов. Не включая мозг, я начал сразу кидать что-то вроде
common = set(a).intersection(set(b)) # найдём общие элементы
for el in common:
occurs = min(a.count(el), b.count(el)) # и посчитаем, сколько они встречаютсяНо меня осадили — у нас война, поэтому никаких intersection, только хардкор. После нескольких итераций и намёков интервьюера я родил вот это:
def common_elements(a, b):
b_dict = defaultdict(int) # defaultdict выжил :)
for el in b:
b_dict[el] += 1 # я считаю все элементы из b, т.е. типа collections.Counter
result = []
for el in a:
count = b_dict[el]
if count > 0: # если какой-то элемент из a встречается в b
result.append(a) # то это успех
b_dict[a] -= 1 # и я "вынимаю" его из b, т.е. уменьшаю его количество на 1
return result
Тут же меня спросили, какова сложность алгоритма — ок, норм, это нужно знать, потому что в реальном программировании мне это потребовалось целых 0 раз. Ответил.
После этого задания (и впоследствии) я увидел, что хоть они и принимают рабочие решения, у них есть эталонные, к которым они вас подталкивают, особенно если сложность вашего решения больше сложности эталона. Не то чтобы прям только эталон принимают, но знайте, что он есть.
Кстати, как вы наверно догадываетесь, есть большая разница между решением, написанным в обычной рабочей атмосфере, и решением, написанным на собеседовании в яндекс.блокнотике с интервьюером на связи и ограничением по времени. Здесь и далее я привожу те решения, которые сообразил на интервью, какими бы ужасными они не были. Можно ли написать лучше? Да, в каждой из задач можно лучше.
Задача 2
Ладно, лоу-левел алгоритмическая муть позади, давайте теперь нормальную задачу, распарсить там что-нибудь или накидать архитектуру высоконагруженного прило…
Дана строка (возможно, пустая), состоящая из букв A-Z:
AAAABBBCCXYZDDDDEEEFFFAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBНужно написать функцию RLE, которая на выходе даст строку вида:A4B3C2XYZD4E3F3A6B28
И сгенерирует ошибку, если на вход пришла невалидная строка.
Пояснения: Если символ встречается 1 раз, он остается без изменений; Если символ повторяется более 1 раза, к нему добавляется количество повторений.
Ну ок, хотят проверить знание каких-то базовых вещей.
Вроде просто: for grouper, items in groupby(string)… А, да, у нас была война. Ничего нет.
def convert(s: str) -> str:
result: List[str] = []
last_sym = None # последний символ, что мы видели
count = 0 # и сколько мы его видели
# мы будем идти по строке и записывать в result при смене символа
for sym in (list(s) + [None]): # последний None искусственно триггерит посленюю смену символа
if last_sym and sym != last_sym: # если случилась смена символа
if count == 1:
result.append(last_sym)
else:
result.append(last_sym + str(count))
# начнаем запоминать новый символ
count = 1
last_sym = sym
else: # символ просто повторился
count += 1 # ну ок, запомнили что символ видели на 1 раз больше
return ''.join(result)
Не помню точно, но с вероятностью 3 сигма я продолбал граничные условия — это я делать люблю. Помните, тут нельзя ничего запускать, вместо этого тут принято запускать интервьюера, который интерпретирует ваш код прям в голове и говорит какие случаи не работают, чтобы вы могли пропатчить код.
Так, давайте может что-то другое?
Задача 3
Дан список интов, повторяющихся элементов в списке нет. Нужно преобразовать это множество в строку, сворачивая соседние по числовому ряду числа в диапазоны. Примеры:
[1,4,5,2,3,9,8,11,0] => »0–5,8–9,11»
[1,4,3,2] => »1–4»
[1,4] => »1,4»
Так блин, серьёзно? Я наверно очень мутный тип, если две предыдущие задачи не показали мой скилл на этом классе задач.
Ну ок, хотят проверить знание каких-то базовых вещей.
def repr(group_start, group_end) -> str:
# это просто правильно печатает группу
if last_group_start == last_group_end:
return str(last_group_end)
return f'{last_group_start}-{last_group_end}'
def squeeze(numbers) -> str:
if not numbers: # граничный случай
return ''
numbers_ = sorted(numbers) # сначала располагаем по порядку
groups = [] # тут будем хранить группы
last_group_start = None
last_group_end = None
for n in numbers_:
# это первая итерация, просто говорим, что группа началась и закончилась
if last_group_end is None:
last_group_start = n
last_group_end = n
# если предыдущая группа отличается от текущего числа на 1,
# то это число входит в группу, то есть становится концом группы
elif last_group_end == n-1:
last_group_end = n
# иначе мы понимаем, что группа закончилась,
# мы её запоминаем и начинаем новую
else:
groups.append(repr(last_group_start, last_group_end))
last_group_start = n
last_group_end = n
else:
# посленюю группу придётся обработать вручную
groups.append(repr(last_group_start, last_group_end))
return ','.join(groups)
На этом интервью закончилось, и я стал ждать вестей от рекрутера.
Через пару часов мне сказали, что всё отлично и меня ждут на следующих интервью — 2 штуки подряд — задачи на написание кода. Так, минуточку, а что было до этого — написание говнокода? Ладно, там видно будет. Уж точно что-то новенькое, следующий этап всё-таки.
Интервью 2
В назначенный час я бахнул кофейку и встретился в зуме с новым рекрутером. Интервью #2 началось.
Задача 4
Я, признаюсь, был готов ко всему, но не к этому:
Дан массив из нулей и единиц. Нужно определить, какой максимальный по длине подинтервал единиц можно получить, удалив ровно один элемент массива.
[1, 1, 0]
Ну ок, хотят проверить знание каких-то базовых вещей. Вот такой ужас у меня вышел:
# пример: [0, 0, 1, 1, 0, 1, 1, 0]
def max_ones_length(lst: List[int]) -> int:
max_ones_length = 0
# тут мы хотим получить сгруппированные 0 или 1 и их количество:
subranges = [] # [(0, 2), (1, 2), (0, 1), (1, 2), (0, 1)]
last_el = None # последний элемент, который мы просмотрели
# идём по элементам списка
for el in lst + [0]: # [0] - это ручной триггер для обработки последнего элемента
if last_el != el: # если произошла смена 0 на 1 или наоборот
if el == 0: # если это была смена 1 на 0
# пример: subranges == [(0, 2), (1, 2), (0, 1), (1, 2)]
# у нас произошла смена 1 на 0, до смены единица шла 2 раза
# (см последний элемент subranges) - проверяем, вдруг это
# максимальная длина
try:
last_ones_length = subranges[-1][1]
max_ones_length = max(last_ones_length, max_ones_length)
except IndexError:
pass
# а может если мы удалим один ноль между элементами 1 и 3,
# то получится более длинная последовательность единиц?
try:
gap_length = subranges[-2][1]
if gap_length == 1:
combined_ones_length = subranges[-1][1] + subranges[-3][1]
max_ones_length = max(combined_ones_length, max_ones_length)
except IndexError:
pass
# добавляем новый счётчик последовательности в subranges
subranges.append((el, 1))
else:
# увеличиваем счётчик последней последовательности на 1
subranges[-1] = (el, subranges[-1][1]+1])
last_el = el
# костыль, граничное условие
if len(subranges) == 2 and subranges[1][1] == 1:
return subranges[0][1] - 1
return max_ones_length
Ну что, Яндекс, ты доволен? Ты доволен?! Кто король алгоритмов?! Я король алгоритмов! Давай, удиви меня…
Задача 5
Даны даты заезда и отъезда каждого гостя. Для каждого гостя дата заезда строго раньше даты отъезда (то есть каждый гость останавливается хотя бы на одну ночь). В пределах одного дня считается, что сначала старые гости выезжают, а затем въезжают новые. Найти максимальное число постояльцев, которые одновременно проживали в гостинице (считаем, что измерение количества постояльцев происходит в конце дня).
sample = [ (1, 2), (1, 3), (2, 4), (2, 3), ]
Отлично, тут уже начинает появляться мир — ну там люди, отели, вдруг даже этот код реально где-то когда-то может пригодиться. Я прям вижу, как с каждой задачей будут появляться дороги, поезда, реки, горы и моря, металл, электричество, сервера и датацентры и блин задачи, которые будут работать в дата-центрах и серверах, ну хоть где-нибудь!
Ну ок, хотят проверить знание каких-то базовых вещей.
from collections import defaultdict
def max_num_guests(guests: List[tuple]) -> int:
res = 0
# для каждого дня посчитаем, сколько приехало и сколько отъехало
arriving = defaultdict(int)
leaving = defaultdict(int)
for guest in guests: # O(n)
arriving[guest[0]] += 1
leaving[guest[1]] += 1
current = 0
# едем по дням в порядке увеличения, добавлем приехавших и убавляем уехавших,
# считаем сколько стало
for day in sorted(set(arriving.keys()).union(set(leaving.keys()))): # O(n*log(n)) + O(n)
current -= leaving[day]
current += arriving[day]
if current > res:
res = current
return res
Не без подсказки интервьюера, но я написал это, и теперь менеджер, наверно, может эффективно узнать важную инфу. Круто. Пора прыгать на следующее собеседование (да, они шли одно за другим).
Интервью 3
Новый интервьюер; можно наблюдателя; можно писать заметки; да, я знаю, как работает ваш яндекс.блокнот лучше вас уже, давайте наконец
Задача 6
Sample Input [«eat», «tea», «tan», «ate», «nat», «bat»]
Sample Output [ [«ate», «eat», «tea»], [«nat», «tan»], [«bat»] ]Т.е. сгруппировать слова по «общим буквам».
Смутное чувство дежавю посетило меня… Нет, показалось наверно. Ну ок, хотят проверить знание каких-то базовых вещей.
Эта задача простая, наверно хотят удостовериться, что пока я разруливал дела в отеле, я не забыл, как пользоваться словарём. Не лишено смысла! Давайте накидаем что-нибудь простое.
def group_words(words: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in words: # O(n)
key = sorted(word)
groups[key].append(word)
return [sorted(words) for words in groups.values()] # O(n*log(n))
Тут меня спросили «а какая сложность у сортировки», и я воспользовался лайфхаком. Дело в том, что все собеседования проводятся разными людьми, и они вообще не знают ваш контекст — например, о чём я говорил в предыдущих сериях и, например, кхм, сколько алгоритмических задач я прорешал до этого. На прошлом собеседовании меня спросили, какая сложность у сортировки, я не знал и мне сказали — и на этом собеседовании я уже ответил.
Задача 7
Слияние отрезков:
Вход: [1, 3] [100, 200] [2, 4]
Выход: [1, 4] [100, 200]
Честно говоря, где-то тут мне уже стало плевать на собеседование, Яндекс и все эти алгоритмы, и в реале я бы уже просто послал всех в /dev/null, но мне хотелось знать, что в конце всего этого, ведь конец должен быть? Будет задача, где я завалюсь, и это кончится. Что-то вроде эвтаназии, но в интервью.
Ну ок, хотят проверить знание каких-то базовых вещей.
def merge(ranges: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
if not ranges:
return []
result_ranges = []
last_range = None # последний отрезок, что мы видели
for rng in sorted(ranges): # обязательно сортируем
if not last_range:
last_range = rng
continue
# если начало текущего отрезка меньше конца предыдущего
if rng[0] <= last_range[1]:
# расширяем предыдущий отрезок на текущий
last_range = (last_range[0], max(rng[1], last_range[1])
# старый отрезок всё, начинаем новый
else:
result_ranges.append(last_range)
last_range = rng
else:
# граничный случай для последнего элемента
result_ranges.append(last_range)
return result_rangesЗадача 8
Время собеседования подходит к концу, но всё-таки можно ещё поболтать про кодинг и поспрашивать практические вопросы, например по Django или SqlAlchemy:
Дан массив точек с целочисленными координатами (x, y). Определить, существует ли вертикальная прямая, делящая точки на 2 симметричных относительно этой прямой множества. Note: Для удобства точку можно представлять не как массив [x, y], а как объект {x, y}
Ну ок, хотят проверить знание каких-то базовых вещей.
Тут я как всегда пошёл куда-то не туда и написал вот что:
from statistics import mean
def is_vertical_symmetry(points: List[Point]) -> bool:
# сначала найдём вертикальную прямую в середине всех точек
x_center = mean(p.x for p in points)
# тут будем хранить точки, для которых пока не нашли пары:
unmatched_points = defaultdict(int)
for point in points:
if point.x == x_center: # если точка на прямой, то она сама себе пара
continue
# создадим "брата" - точку, которая симметрична текущей относительно вертикальной прямой
brother = Point(
x = x_center * 2 - point.x,
y = point.y,
)
# если этот брат есть в unmatched_points, то достаём его оттуда и говорим, что текущая точка сматчилась
if unmatched_points[brother]:
unmatched_points[brother] -= 1
# иначе добавляем эту точку в не-сматченные
else:
unmatched_points[point] += 1
return not any(unmatched_points.values())Здесь я прям видел, как интервьюер ожидал что-то другое, а получил меня. Ну бывает. Я тоже, знаете, ожидал собеседование.
Так, третье собеседование пройдено, и эти садисты сказали, что я прошёл дальше. Ну вот за что?
Интервью 4
Честно говоря, вот тут я потерялся, потому что я всё жду, когда начнётся собеседование, ну, человеческое собеседование имеется в виду, а пока вместо этого я превращаюсь в алгоритмэна.
По собственным ощущениям я добрался до какого-то мини-босса и на предстоящем интервью у меня должна была пройти какая-то битва на более общие вопросы. А рекрутер мне пишет: знаете, Яндекс настоятельно советует потренироваться на задачках с leetcode. А там опять алгоритмы. Ох, не к добру это…
Ну тут уж я сломился и решил таки глянуть, что там за задачки, раз мне так настойчиво намекают. Вообще там есть сложные, и над ними было прикольно подумать и порешать в уме, но я так и не понял, как это поможет в интервью. Задачек слишком много и, что более важно, они, блин, разные, и решив одну, я не решаю класс задач — я решаю одну задачу. Соответственно либо я решаю их все и зачем мне тогда ваш Яндекс после такого, либо… короче, я опять не готовился. Ответственный человек, помните?
Кстати, где-то в этот момент я узнал, что я юзаю что-то вроде тора, но для собеседований: я общаюсь с рекрутером, мой рекрутер общается с рекрутером Яндекса, а рекрутер Яндекса общается с собеседователями, а может цепочка ещё больше. Меня это поразило прям: вы меня тут дерёте за O (n^2) в решениях, так может я у вас посчитаю длину цепочки от кандидата до собственно интервьюера и спрошу »а можно оптимальнее?! »
Итак, началась четвёртое (да, ей-Богу) интервью. Интервьюер спрашивает, на каком языке я буду решать задачки. На йоптаскрипте, разумеется. Кстати, по косвенным признакам я понял, что интервьюер больше в C, чем в питон, и это тоже здорово. Итак: после того как компания решила нанять сеньор питон разраба за 200к и сношала его 3 часа на долбанных задачках, она отправляет на собеседование сишника и спрашивает, на каком языке кандидат будет сношаться с долбанными задачками. Л — логика!
Итак, вот задачка от мини-босса:
Задание 9
Даны две строки.
Написать функцию, которая вернёт True, если из первой строки можно получить вторую, совершив не более 1 изменения (== удаление / замена символа).
Погодите, да это же… Ну ок, хотят проверить знание каких-то базовых вещей. Сссссуууу…пер.
Если вы хотите решить задачу не так, как хотел интервьюер, то смотрите:
def no_more_than_one_change(string1: str, string2: str) -> bool:
# string1: a b c d
# string2: a b c
max_length = max(len(string1), len(string2)) # наибольшая длина строк
diff = abs(len(string1) - len(string2)) # разница в длине строк
# дополняем строки до максимальной длины при помощи zip_longest,
# то есть на место "недостающих" элементов ставим None, и строки
# теперь одинаковой длины;
# ---->
# string1: a b c d
# string2: a b c None
# идём слева направо по обеим строкам и сравниваем символы,
# находим индекс, при котором строки начинают отличаться:
change_left = None
for i, (char1, char2) in enumerate(zip_longest(string1, string2)): # O(n)
if char1 != char2:
change_left = i # в нашем примере будет 3
break
else:
# если мы такой индекс не нашли, то строки просто совпадают
return True
# теперь делаем то же, но идём справа налево:
# string1: a b c d
# string2: None a b c
# <----
change_right = None
for j, (char1, char2) in enumerate(zip_longest(reversed(string1), reversed(string2))): # O(n)
if char1 != char2:
# тут строки прям сразу отличаются, т.е. в индексе j=0;
# но это у нас индекс в системе "справа налево",
# а мы его переводим в индекс в системе "слева направо":
i = max_length - j - 1 + diff
break
else:
assert False, 'Я дебил и что-то не учёл'
# ну а теперь смотрим, если строки отличаются в одном и том же месте
# при сканировании слева направо и справа налево, то это нам подходит
return change_left == change_right
Внимательный читатель может заметить, что, по-моему, это даже на приведённом примере не работает :) , хотя пофиксить несложно. Так или иначе, вот такие вещи как я написал лично мне тяжело гонять в голове, и интервьюеру тоже; интервьюер принял это как решение, прогнав несколько тестов в уме. Если хотите возвести это в абсолют, то пишите сразу на brainfucke и с умным видом объясняйте, почему оно будет работать. А вообще я просто тонко намекаю, что всё-таки компилятор/интерпретатор под рукой нужен.
Задание 10
Осталась совсем немного времени, и вот в довершение пара реально сложных заданий на понимание многопоточности и gil в python:
Дан список интов и число-цель. Нужно найти такой range, чтобы сумма его элементов давала число-цель.
elements = [1, -3, 4, 5]
target = 9
result = range (2, 4) # because elements[2] + elements[3] == target
А теперь все вместе хором: НУ ОК, ХОТЯТ ПРОВЕРИТЬ ЗНАНИЕ КАКИХ-ТО БАЗОВЫХ ВЕЩЕЙ. Вы восхитительны. Спасибо.
Здесь я уже не успевал по времени и озвучил идею: мы бежим по списку и сохраняем в память значения сумм для всех range до этого элемета. Иными словами, для каждого элемента мы пробуем делать ranges, которые кончаются на этом элементе, и смотрим на их сумму элементов.
[1, -3, 5, 6, 2, 3, 5]
^____[range(0,1)=1]
[1, -3, 5, 6, 2, 3, 5]
^___[range(0,2)=range(0,1)-3=-2, range(1,2)=-3]
[1, -3, 5, 6, 2, 3, 5]
^___[range(0,3)=range(0,2)+5=3, range(1,3)=range(1,2)+5=2, range(2,3)=5]Не угадал, конечно — «а можно быстрее?». Но тут, к счастью, время вышло, и мой мозг не успел придумать ничего лучше.
>> Сейчас я нахожусь здесь <<
Прелесть ситуации в том, что я ещё не получил фидбек, то есть я кандидат Шрёдингера — я и прошёл (формально я все задачи решил), и не прошёл (== не всё угадал, где-то баги), и суперпозиция сколлапсирует, когда ответ пройдёт через всю цепочку рекрутеров ко мне. А пока я полностью беспристрастен, ведь 1) меня не отшили, то есть это не пост обиженного на компанию человека, и 2) мне плевать на результат, потому что мне и на текущей работе офигенно.
К чему всё это
Вообще это просто так тупо, что забавно, и я не мог с вами не поделиться. Никак не связанные люди тестируют меня на одном и том же типе задач, который максимально оторван от реальности, всё это длится много часов, сложность задач неупорядочена, проверяется всё в голове и никакого фидбека.
Сколько вопросов, блин, можно спросить про http, rest, django orm, sql, python, stdlib, docker, multithreading/multiprocessing/async, да про что угодно — что вы там в лавке делаете? — спросите про похмелье, но зачем 4 часа алгоритмов? Что это показывет — что я устойчив к тупости? Честно говоря, я уже не уверен.
Может кому-то пригодится разбор задачек, ну вдруг вы любитель такого, хотя я уже говорил о качестве решений :)
А если вам нужен вывод, то вот несколько, берите любой:
Тестировать кандидатов нужно на реальных задачах, а не синтетических
Нужно уважать время кандидатов
Кто-то в яндексе пересмотрел «день сурка»
Знаете, когда целое не равно сумме частей? Вот тут так же: люди тебя собеседуют хорошие и встречи приятные, а в целом всё гавно.
Открыто новое достижение: ругательство «да пошёл ты в яндекс!»
Большие компании ай-яй-яй
Какой-то чувак написал смешную статью
И да, если вы ищете работу на питоне — залетайте к нам. У нас не Яндекс.
