Собеседование в Яндекс: театр абсурда :/

Хорошо, учту, если вдруг снова пойду на интервью..

Собеседование в Яндекс: театр абсурда :/

Процитирую автора:

я человек ответственный, поэтому к интервью не готовлюсь. Это кстати я не шуткую, реально: если вы ответственный человек, ты вы, когда предстаёте перед компанией, отвечаете за то, что вы заявляете как ваши умения. Можно выучить типовые вопросы и даже казаться умнее и опытнее, чем есть, но по факту это переобучение на тестовых заданиях/вопросах.

И ещё раз себя:

слёту без гугления я его построить не могу, в работе это пригодилось мне примерно никогда

Я не успел построить, так как у нас оставалось 5-10 минут. Я начал описывать класс Node, но не успел сделать методы добавления (вставка не нужна была, только построить дерево на основе отсортированного массива).

---

если бы поиск в ней занимал столько же времени, что и поиск в массиве

Я задаюсь вопросом, какая сложность поиска по отсортированному бинарному дереву, если не O(log(n)) — тот ответ, который я в итоге дал интервьюеру, и который он не принял.

Собеседование в Яндекс: театр абсурда :/

Спасибо за статью! Сам недавно столкнулся с интервью в Яндекс будучи скептично настроенным. Ваш пост отлично выражает моё недоумение. Только я не прошёл даже первое интервью, на второе уже не позвали.

У меня немного бомбило с задач, с того, что нельзя использовать встроенные классы и методы, вот первая задача с пересечением множеств, мой код с интервью без изменений (и сразу же «определите сложность алгоритма»):

[1, 2, 3]
[4, 2, 1]

[1, 2]

res = list(set(n).intersection(set(m)))

# set(n) + set(m) +
O(n) + O(m) + O(m) = O(n) + 2 * O(m)

[1, 2, 3, 2, 0]
[5, 1, 2, 7, 3, 2]

[1, 2, 2, 3]

from collections import defaultdict

d1 = defaultdict(int)
d2 = defaultdict(int)

for elem in a1:
    d1[elem] += 1

for elem in a2:
    d2[elem] += 1

result = []

for v2, count2 in d2.items():
    count1 = d1.get(v2)
    if count1 is None:
        continue

    for _ in range(min(count1, count2)):
        result.append(v2)

Дальше наши интервью уже отличаются. Мне было задано построить бинарное дерево поиска. Но перед этим назвать сложность поиска, если дерево уже отсортировано. Я выдал что-то типа «ну в лучшем случае это O(1) потому что элемент попадётся первым, в худшем мы пройдёмся по всем элементам, поэтому это O(n), а в среднем там какой-то логарифм, сам не помню, как правильно считается». На что последовал ответ «ну вообще-то нет». Я немного опешил и начал визуализировать (тоже код с интервью):

####
n = 15

"""
1 0 1 0 1 0 1 0  # 3 || 8 = 2 ^ 3
 1   0   1   0   # 2 || 4 = 2 ^ 2
   1       0     # 1 || 2 = 2 ^ 1
       1         # 0
"""

elements_in_top_row = (n + 1) // 2

2 ** 3 = elements_in_top_row

2 ** y == elements_in_top_row

y == log2(elements_in_top_row)

#################

На что уже не получил какого-то фидбека, мне сказали строить дерево. Пока я пытался без интернета построить бинарное дерево (в начале интервью было сказано, что гуглить не надо, выполнять код нигде не надо, пишем сразу в этом редакторе), вышло время интервью. Интервьюер быстро попрощался и закончил собеседование.

---

Так я остался с послевкусием недосказанности, у меня были вопросы, которые я просто задал в пустоту, примерно продублирую их тут:

• Какая сложность алгоритма поиска в отсортированном бинарном дереве? Википедия подсказывает, что O(log n)
• Я не имею ничего против бинарного дерева. Но слёту без гугления я его построить не могу, в работе это пригодилось мне примерно никогда. Почему на вакансию веб бекенд спрашивают такое? Это основная задача? И да, я могу построить бинарное дерево поиска. Но с гуглом. Построю и забуду сразу. Но в работе это реально надо? Как часто обращаясь к апишке вы думаете “хм а они фильтрацию/поиск через бинарное дерево сделали? Или линейно ищут”

---

P.S. В тексте статьи возникал вопрос, а на того ли направлены задачи, ведь и методичка про C++ говорит (мне такую тоже высылали) и гоняют только по алгоритмам. Если судить по этому посту, всё так и задумано, и это требуется именно от бекенда (ну, либо в Лавке и Маркете совсем разный отбор).