[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 задачек, чтобы чувствовать уверенность в каждой из перечисленных структур данных