Запись [Tskills] Хакни алгоритмические собеседования (Макс Фатин, Даня Слободенюк)

​

• Почувствуй уверенность на алгоритмическом собеседовании и проходи его успешно даже если интервьюер все время молчит.
• Начни успешно проходить алго-собесы с 1-ой недели курса, даже если до этого частенько их заваливал. P.S. не кликбейт, ведь не во всех компаниях спрашивают сложные темы.
• Освой навык, который позволит увеличить число и качество офферов в 1,5–2 раза.

Алгоритмы сейчас нужны почти в каждой Big Tech компании при трудоустройстве

Для кого прокачать алгоритмы это мастхэв?

• Не получается проходить алгоритмические собесы и получить оффер в компанию мечты
• Усердно готовишься к алго-собесам, но все равно нет легкости на самом собесе
• Хочешь работать над сложными проектами, но не хватает знаний
• Во время собеса интервьюер молчит, а ты не знаешь, что с этим делать

И кто хочет:

• Успешно проходить алгоритмическую секцию и решать задачи с первого раза с полным пониманием происходящего. Как итог — увеличивать число и размер офферов
• Грамотно выбирать структуры данных и алгоритмы для рабочих задач и без проблем делать оценку по времени и памяти в Big O нотации
• Грамотно просить подсказки и приятно удивлять интервьюера
• Видеть паттерны в задачах и уметь их применять, а не зубрить решение каждой задачи

За счет чего ты получишь результат?

• Определим твою цель и найдем кратчайший путь к ней
• Мы проанализировали рынок, изучили самые популярные темы, которые используются в работе и на собесах, и включили их в обучающую программу
• Собрали задачки, которые встречались соискателям на собеседованиях в Яндекс, VK, Ozon, Сбер, Авито, Huawei и другие компании. Мы включили их в лекции и домашку, поэтому уже на первой неделе ты будешь готов к алго-собесу в Авито, на второй в OZON и так далее
• После каждой лекции есть домашка — ты будешь закреплять знания на практике, решая задачи на LeetCode, Codeforces, InterviewBit, которые встречаются на собеседованиях. А после решения сверяться с эталонными решениями.

Важно понять: это не 5 недель уроков, а 5 недель совместной работы, после которой у тебя прокачается алгоритмический скилл. При должном упорстве ты сможешь получить оффер в компанию мечты.

Спойлер: Ты освоишь:

В итоге ты освоишь:

1. Хеш-таблица

Bit map
Bit map или как написать свою хеш-таблицу на битовых манипуляциях, чтобы работала оптимальней, чем встроенная в ЯП (а ее между прочем создавали вполне не глупые люди), но есть хак как ее можно обогнать… Ты не поверишь, но это не только нужно для собесов, но и работы.

Структуры данных
Поиск двух элементов дающих в сумме target уже не в моде и осталось только на страницах учебников. В топ популярных вопросов сейчас входит написание своих структур данных с использованием хеш-таблиц с ними то мы и разберемся.

Я + Ты + ClickHouse = ?
Хочу поделиться с тобой историей как я оптимизировал запросы в ClickHouse на кластере, где более 5 ярдов событий за месяц приходит или как я писал свой bloom filter и для чего он вообще нужен… Ну и конечно расскажу что их этого вышло.

Внутри и снаружи
Снаружи у хеш-таблицы все просто: вставка, поиск, удаление — все за O (1). Но как насчет внутрянки? А ведь есть и такие проблемы как коллизии, подбор хеш-функции, не обоснованное использование фильтра Блюма… Но мы наведем порядок «внутри и снаружи», чтобы интервьюер не поставил в тупик вопросом по реализации хеш-таблицы.

Результат
Решишь топ 6 задач с собеседований на тему «хеш-таблиц», а если быстро справишься, то дам еще задачек для закрепления.

2. Графы для графов

База для графов
Как истинные графы «по привычке» пьют чай с отогнутым мизинцем тебе нужно знать что такое dfs, bfs, когда какой обход выбирать, способы хранения графов…, чтобы «по привычке» успешно решать задачи на эту не простую тему
Шах и мат!
Лошадь с A1 на B3 или нет, на С2… Именно такие раздумия могут быть если заранее не прорешать популярные задачки на шахматные фигуры, но мы это исправим и ты точно будешь знать следующий ход!

Я + Huawei + Графы
Расскажу историю о том, как я придумал параллельный алгоритм поиска пути в графах, который до сих под используется в MPI приложениях для поиска точек оптимизаций при запуске на больших кластерах и что значит работать в R&D или как мне каждый день на работе нужны были алгосы P. S. есть даже статейка с моим алгоритмом, которая опубликована в книге

Карта наше все
Сейчас самые популярные задачки на «карты» и работу с DFS и BFS. Чтобы показать все самые сильные стороны интервьюеру отработаем работу с картами и обходы на них

Результат
Прорешаешь все самые популярные задачи на графы на задачах Яндекса и других Big-tech компаний

3. Не простые массивы

Кажется, что просто
Найди сумму диагоналей в метрице! Именно такая задача долгое время встречалась в Яндексе и кандидаты забывали, что при нечетном размере элемент в центре складывается дважды. Чтобы так не промахнуться разберем, что спрашивают по этой теме сейчас
Хакаем массивы
Разберем in-place оптимизации, позволяющие без хеш-таблицы искать пропущенные числа за O (n)

Структуры данных
Узнаешь о структурах данных и научишься с ними работать, которые строятся на казалось бы простых массивах, но позволяют отпимально находить максимальные/минимальные элементы в даже на больших данных

Префиксные массивы
Не дай интервьюеру поставить тебя в тупик вопросом: «реализуй структуру данных, которая за O (1) находит сумму на интервалах…». Узнай что такое префиксные массивы, особенности реализации, возможные оптимизации и когда их стоит применять, а когда нет

Результат
Решишь 10 задачек и освоишь все популярные паттерны работы с «не простыми массивами» и оценишь по времени и памяти каждую задачу

4. Два указателя

С двух сторон
Раньше достаточно было знать как проверить слово в нижнем регистре на палиндром, а теперь эта университетская задача эволюционировала в целый паттерн «с двух сторон», которым решается не малый класс задач

Каждому по указателю
Сейчас в тренде задачки не просто на 2 указателя, а с различными сортировками и дальнейшим видами объединения. Так что будем следовать тренду и узнаем, что именно интервьюер хочет получить, когда просит написать условный «UNION» и какие операции нужно уметь делать еще

Fast & slow
Быстрый и медленный указатель. Эххх… Это уже стало баяном так что не знать данный патер стыдно, но мы это исправим

Результат
Узнаешь что хотят услышать от кандидата Сбер, Яндекс и Озон по теме двух указателей и решишь более 5 задач на закрепление темы

5. Плавающее окно

Пересекай и побеждай
Представь, что ты бы мог решать задачи на плавающие окна без ошибок и с первого раза! Так вот это не миф, а реальность. Просто до прохождения программы ты не знал о паттернах про «пересекающиеся» и «не пересекающихся» окна. Каждый их которых имеют свою не изменную структуру в коде

Оцени эффективность
Перед тем как на собеседовании приступить к написанию кода нужно оценить решение по времени и памяти и плавающее окно не исключение. Поэтому рассмотрим как быстро и точно оценивать память для каждого из типов задач

Результат
Прорешаешь минимум 7 задачек для отработки каждого паттерна, чтобы не вспоминать “что там говорил лектор” на собеседовании, а быстро и четко решать задачи

6. Бинарный поиск и Сортировки

Хватит так писать!
Не раз наблюдал как кандидаты судорожно пишут бинарный поиск и мене это надоело! Я хочу, чтобы ты не сомневался ни на секунду, когда будешь решать в очередной раз поиск первого или последнего вхождения элемента в массив, ведь есть очень простой способ это делать и я его тебе покажу (его используют все олимпиадники)
Учимся бинарить все
Научу видеть тебя бинарный поиск даже в тех задачках, где не нужно, ведь осознание простого правила «Какая задача может решаться бинарным поиском?» научит тебя понимать суть бинарного поиска и области его применения далеко за пределами простых задачек

Сортируй с умом
А какая сортировка есть в твоем ЯП? А какая у нее ассимптотика? А точно нельзя оптимальней? Все это базовые вопросы, которые не должны ставить тебя в тупик так что пройдемся по базовым сортировкам и научимся их применять для паттерна с кодовым названием «AНА» и «сортировка событий»

Результат
После лекции про бинарный поиск решишь 5+ задач с собеседований BigTech компаний. А после лекции по сортировкам еще 5+ задач (и все с собесов)

7. Структуры данных

Стек и Очередь
Все уже научились проверять скобочную последовательность “{()[]}” на правильность с помощью стека, поэтому рассмотрим тему чуть глубже и научимся решать не только баянистые задачи, которые важно знать, но и ответим на важные вопросы, такие как: “Что такое VIP очередь?” и “Зачем очередь писать на стеках?”

Связный список
Новый тред задал Sber Devices, когда начал активно спрашивать кандидатов про связный список и умение работать с ним используя паттерны “Быстрый и медленный указатель”. Рассмотрим все что нужно знать, чтобы не оплашать перед интервьюером и даже чуть больше

Деревья
Если собрался идти на собес в Яндекс без знаний по деревьям, то это может быть фатальной ошибкой. Ведь это одна из тем, которую с особым пристрастием спрашивают интервьюеры. Я и сам раньше любил давать такие задачки, поэтому подсвечу все подводные камни

Куча
Мало кто слышал про эту структуру данных и еще меньше кто умеет ее реализовывать и объяснять детали реализации под капотом. А вот если ты решил пойти на высокий грейд в Авито, то эти знания тебе точно понадобятся, поэтому ты отработаешь все на практике + прорешаешь все важные задачи для освоения темы

Результат
Прорешаешь более 15 задачек, чтобы чувствовать уверенность в каждой из перечисленных структур данных