Шпаргалка для технического собеседования
Эта шпаргалка поможет вам подготовиться к техническому собеседованию, чтобы вы могли освежить в памяти ключевые вещи. По сути, это содержание курса по информатике безо всяких подробностей.
Основы структур данных
Массив
Определение:
- Хранит элементы данных на основе последовательного индекса, чаще всего с нулевой базой.
- В его основе лежат кортежи из теории множеств.
- Массив — одна из старейших и наиболее используемых структур данных.
Что вам нужно знать:
- Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива).
- Основная разновидность — линейные массивы, или одноразмерные.
- Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
- При заполнении динамического массива его содержимое копируется в массив большего размер.
Эффективность («О» большое):
- Индексирование: линейный массив — O(1), динамический массив — O(1).
- Поиск: линейный массив — O(n), динамический массив — O(n).
- Оптимизированный поиск: линейный массив — O(log n), динамический массив — O(log n).
- Вставка: линейный массив — недопустимо, динамический массив — O(n).
Связный список
Определение:
- Данные хранятся в узлах, указывающих на другие узлы.
- Узел содержит один элемент данных и одну ссылку (на другой узел).
- Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.
Что вам нужно знать:
- Связный список разработан для оптимизирования вставки и удаления. Медленно работает при индексировании и поиске.
- Двусвязный список содержит узлы, которые ссылаются на предыдущие узлы.
- Кольцевой связный список — это простой связный список, хвост которого (последний узел) ссылается на голову (первый узел).
- Стек обычно реализуется с помощью связных списков, но может быть создан и из массивов.
- Стеки — это LIFO-структуры данных (last in, first out).
- Голова связного списка, лежащего в основе стека, единственное место для вставки и удаления элементов.
- Очереди — это FIFO-структуры данных (first in, first out).
- Очередь представляет собой двусвязный список, в котором элементы удаляются из головы, а добавляются в хвост.
Эффективность («О» большое):
- Индексирование: связный список — O(n).
- Поиск: связный список — O(n).
- Оптимизированный поиск: связный список — O(n).
- Вставка: связный список — O(1).
Хэш-таблица
Определение:
- Данные хранятся в виде пар ключ-значение.
- Хэш-функции принимают ключ и возвращают выходные данные, соответствующие только этому ключу.
- Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.
- Хэш-функции возвращают для данных уникальные адреса в памяти.
Что вам нужно знать:
- Хэш-функции разработаны для оптимизирования поиска, вставки и удаления.
- Хэш-коллизиями называются ситуации, когда для двух разных входных данных функция возвращает одинаковые выходные данные.
- Эта проблема свойственна всем хэш-функциям.
- Часто она решается с помощью увеличения хэш-таблиц до огромного размера.
Эффективность («О» большое):
- Индексирование: хэш-таблицы — O(1).
- Поиск: хэш-таблицы — O(1).
- Вставка: хэш-таблицы — O(1).
Двоичное дерево
Определение:
- Двоичное дерево — это такая структура данных, в которой каждый узел имеет максимум два дочерних элемента.
- Дочерние элементы бывают левым и правым.
Что вам нужно знать:
- Деревья разработаны для оптимизирования списка и сортировки.
- Вырожденное дерево — это несбалансированное дерево. Если оно полностью одностороннее, то представляет собой, по сути, связный список.
- Деревья относительно просты в реализации по сравнению с другими структурами данных.
- Используются для создания двоичных деревьев поиска.
- Двоичное дерево с помощью сравнивания ключей решает, в каком направлении следовать к дочернему узлу.
- Ключ левого дочернего узла меньше, чем у родительского.
- Ключ правого дочернего узла больше, чем у родительского.
- Не может быть дублирующих узлов.
- В связи с вышесказанным такое дерево чаще используется как структура данных, чем двоичное дерево.
Эффективность («О» большое):
- Индексирование: двоичное дерево поиска — O(log n).
- Поиск: двоичное дерево поиска — O(log n).
- Вставка: двоичное дерево поиска — O(log n).
Поиск
Поиск в ширину
Определение:
- Поиск в ширину — это алгоритм, ищущий по дереву (или графу), просматривая по уровням начиная с корня.
- Алгоритм находит все узлы текущего уровня, обычно двигаясь слева направо.
- В ходе этого процесса он регистрирует все дочерние узлы, связанные с узлами на текущем уровне.
- По завершении поиска на текущем уровне, алгоритм переходит на крайний левый узел следующего уровня.
- Последним анализируется крайний правый узел самого нижнего уровня.
Что вам нужно знать:
- Поиск в ширину оптимален для поиска по дереву, чья ширина превышает глубину.
- Во время хождения по дереву, алгоритм сохраняет информацию о нём в очереди.
- В связи с использованием очереди такой метод поиска потребляет больше памяти, чем поиск в глубину.
- Очередь использует память для хранения указателей.
Эффективность («О» большое):
- Поиск: поиск в ширину — O(|E| + |V|).
- E — количество рёбер (граней?).
- V — количество вершин.
Поиск в глубину
Определение:
- Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.
- Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.
- Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.
- Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.
- Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).
Что вам нужно знать:
- Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
- Для работы алгоритма используется стек.
- Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.
- Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.
Эффективность («О» большое):
- Поиск: поиск в глубину — O(|E| + |V|).
- E — количество рёбер (граней?).
- V — количество вершин.
Сравнение поисков в ширину и в глубину
- Выбирайте тип поиска в соответствии с размером и формой дерева.
- Для широких, мелких деревьев используйте поиск в ширину.
- Для глубоких, узких деревьев используйте поиск в глубину.
Нюансы:
- Поскольку поиск в ширину использует очереди для хранения информации об узлах и их детях, то он может занять больше памяти, чем доступно на вашем компьютере. (Но вам вряд ли придётся об этом беспокоиться.)
- Если применять поиск в глубину по очень глубокому дереву, то алгоритм может уходить слишком далеко вниз. Подробнее об этом читайте здесь.
- Поиск в ширину — циклический алгоритм.
- Поиск в глубину — рекурсивный алгоритм.
Эффективная сортировка
Сортировка слиянием
Определение:
- Сравнение данных с помощью алгоритма сортировки:
- Весь набор данных делится минимум на две группы.
- Пары значений сравниваются между собой, наименьшее перемещается влево.
- После сортировки внутри всех пар, сравниваются левые значения двух левых пар. Таким образом, создаётся группа из четырёх значений: два наименьшие — слева, наибольшие — справа.
- Процесс повторяется до тех пор, пока не останется только один набор.
Что вам нужно знать:
- Это один из фундаментальных алгоритмов сортировки.
- Данные делятся на как можно более маленькие наборы, которые потом сравниваются.
Эффективность («О» большое):
- Наилучший вариант сортировки: сортировка слиянием — O(n).
- Средний вариант сортировки: сортировка слиянием — O(n log n).
- Худший вариант сортировки: сортировка слиянием — O(n log n).
Быстрая сортировка
Определение:
- Алгоритм сортировки на основе сравнения.
- Весь набор данных делится пополам путём выбора среднего элемента и перемещения всех, кто меньше него, влево.
- Затем такая же процедура итерационно выполняется с левой частью до тех пор, пока не останутся только два элемента. В результате левая часть окажется отсортированной.
- Затем всё то же самое делается с правой частью.
Что вам нужно знать:
- Хотя «О» большое здесь имеет те же значения (а в ряде случаев — хуже), что и у многих других алгоритмов сортировки, но на практике этот алгоритм зачастую работает быстрее, например, той же сортировки слиянием.
- Данные будут последовательно делиться пополам, пока не будут целиком отсортированы.
Эффективность («О» большое):
- Наилучший вариант сортировки: быстрая сортировка — O(n).
- Средний вариант сортировки: быстрая сортировка — O(n log n).
- Худший вариант сортировки: быстрая сортировка — O(n^2).
Пузырьковая сортировка
Определение:
- Алгоритм сортировки на основе сравнения.
- Итерирует слева направо, сравнивая значения внутри каждой пары и перемещая наименьшее влево.
- Процесс повторяется до тех пор, пока ни одно значение уже не может быть перемещено.
Что вам нужно знать:
- Алгоритм очень прост в реализации, но наименее эффективен из всех трёх, описанных здесь.
- Сравнив два значения и переместив наименьшее влево, алгоритм переходит на одну позицию вправо.
Эффективность («О» большое):
- Наилучший вариант сортировки: пузырьковая сортировка — O(n).
- Средний вариант сортировки: пузырьковая сортировка — O(n^2).
- Худший вариант сортировки: пузырьковая сортировка — O(n^2).
Сравнение алгоритмов сортировки слиянием и быстрой сортировки
- Быстрая сортировка на практике зачастую эффективнее.
- Сортировка слиянием сразу делит набор данных на наименьшие возможные группы, а затем восстанавливает набор, инкрементально сортируя и укрупняя группы.
- Быстрая сортировка последовательно делит набор по среднему значению, пока он не будет отсортирован рекурсивно.
Основные типы алгоритмов
Рекурсивные алгоритмы
Определение:
- Как следует из определения, этот алгоритм вызывает самого себя.
- Рекурсивный сценарий — когда условный оператор используется для запуска рекурсии.
- Базовый сценарий — когда условный оператор используется для прерывания рекурсии.
Что вам нужно знать:
- Слишком глубокий уровень стека и переполнение стека.
- Если при работе рекурсивного алгоритма вы столкнулись с чем-то из перечисленного, значит, вы всё испортили.
- Это означает, что базовый сценарий не был ни разу запущен из-за ошибок, либо проблема была столь серьёзной, что у вас кончилась память, прежде чем рекурсия была прервана.
- Знание того, сможете ли вы достичь базового сценария, является неотъемлемой частью правильного использования рекурсии.
- Такие алгоритмы часто используются при поиске в глубину.
Итеративные алгоритмы
Определение:
- Итеративным называется алгоритм, вызываемый неоднократно, но ограниченное количество раз. Каждый вызов является отдельной итерацией.
- Часто применяются для инкрементального прохождения по набору данных.
Что вам нужно знать:
- Обычно итерации представлены в виде циклов, выражений for , while и until .
- Итерация — это однократный проход по набору данных.
- Такие алгоритмы часто применяются для обработки массивов.
Сравнение рекурсивности и итеративности
- Отличить рекурсивность от итеративности бывает сложно, поскольку обе они используются для реализации друг друга. Однако:
- Рекурсивность обычно более выразительна и проста в реализации.
- Итеративность потребляет меньше памяти.
Псевдокод прохождения по массиву (вот почему для этого применяется итеративность)
Рекурсивность | Итеративность ----------------------------------|---------------------------------- recursive method (array, n) | iterative method (array) if array[n] is not nil | for n from 0 to size of array print array[n] | print(array[n]) recursive method(array, n+1) | else | exit loop |Жадные алгоритмы
Определение:
- Жадными называют алгоритмы, выбирающие только ту информацию, которая удовлетворяет определённым критериям.
- Жадный алгоритм содержит пять основных компонентов:
- Набор кандидатов (candidate set), на основе которого создаётся решение.
- Функция выбора, которая решает, какой лучший кандидат будет добавлен в решение.
- Функция обоснования (feasibility function), которая решает, может ли кандидат внести вклад в решение.
- Целевая функция (objective function), которая присваивает значение решению или частичному значению.
- Функция решения (solution function), которая сигнализирует о том, что мы нашли полное решение.
Что вам нужно знать:
- Жадные алгоритмы используются для поиска оптимального решения данной проблемы.
- Обычно они применяются к наборам данных, в которых лишь небольшая порция обработанной информации даёт желаемый результат.
- Часто жадные алгоритмы могут помочь в уменьшении «О» большого другого алгоритма.
Псевдокод жадного алгоритма для поиска самой большой разницы между двумя числами в массиве
greedy algorithm (array) var largest difference = 0 var new difference = find next difference (array[n], array[n+1]) largest difference = new difference if new difference is > largest difference repeat above two steps until all differences have been found return largest differenceЭтому алгоритму не нужно сравнивать друг с другом все разницы, что экономит нам целую итерацию.
Какие алгоритмы спрашивают на собеседовании
Чего хотят работодатели?
Программисты уровня junior и middle для рекрутеров ИТ-компаний – темные лошадки. Какой-нибудь senior или team lead гораздо понятнее работодателю, поскольку уже имеет имя, послужной список и большое количество реализованных проектов в портфолио. Чего ждать от новичков или специалиста среднего уровня, никому не известно, а значит и собеседовать их станут основательно – к этому стоит быть готовым. Требования к потенциальным кандидатам разнятся от компании к компании, но некоторые общие принципы выделить можно.
О чем на собеседованиях спрашивают в корпорациях?
Крупные ИТ-компании не ждут от начинающих разработчиков совершенного владения современными технологическими приемами. Даже программисту middle-уровня на сей счет может быть сделано послабление, но к вопросам наличия у соискателя теоретического базиса гиганты относятся очень серьезно. Список требований обширен и включает весь джентльменский набор из программы профильного вуза. Наличие академических познаний не гарантирует получения места, но их отсутствие точно не даст пройти HR-квест до конца. Как сказал бы математик: теория необходима, но недостаточна для трудоустройства.
О чем спрашивают в средних и небольших компаниях?
Здесь требования попроще, однако блеснуть знаниями на собеседовании стоит. ИТ-компании из сегмента малого и среднего бизнеса активно развиваются и могут очень критично отнестись к способностям разработчика оптимизировать код. Скорее всего вопросы будут касаться неких точечных теоретических областей, в которых заинтересован тот или иной работодатель, но без целостного базиса ответить на них не получится. В переводе на русский язык это означает, что учить опять-таки придется все. Там, где гиганты ведут массовый набор с готовыми скриптами собеседований и последующим отсевом сотрудников на испытательном сроке, игроки среднего размера выбирают лучших кандидатов. Может статься, что пройти их версию квеста по найму будет еще сложнее.
Чего хотят от соискателей стартапы?
Собеседования в стартапы – всегда лотерея. Слишком они разные, чтобы можно было выделить общий подход к найму. Вопросы об алгоритмах и абстрактных структурах данных могут не возникнуть вовсе или стать главными при отсеве негодных соискателей. Предсказать это не получится, но одна закономерность есть: обычно стартаперы ищут единомышленников. Тут нужно понять, разделяете ли вы идеи проекта, а потом уже думать, какие знания понадобятся для успешного трудоустройства. Учить тем не менее придется, смиритесь. Лишним это точно не будет.
Какие знания необходимо освоить?
Если вопрос с подвохом может прилететь откуда угодно, потенциальному кандидату в разработчики нужно уметь отбивать все хитрые «подачи». Для этого его теоретические познания в сфере компьютерных наук должны быть достаточно широкими и целостными. Учебная программа выглядит примерно так:
- Основные структуры данных и алгоритмы: сюда входят стеки, очереди и связные списки, битовые операции, циклы, рекурсия и алгебраические алгоритмы;
- Алгоритмы сортировки: простые сортировки, линейная сортировка, пирамидальная сортировка, а также быстрая и внешняя сортировка;
- Деревья: двоичные, красно-черные и прочая, прочая, прочая;
- Хэш-таблицы: сюда же входят хэш-функции, универсальное и идеальное хэширование, а также разрешение коллизий;
- Теория графов и комбинаторная оптимизация: владеть этой областью нужно на уровне студента-математика первого курса. Ничего сложного, все сводится к основным определениям и решению типовых задач, вроде задачи коммивояжера.
- Алгоритмы на строках: тут придется вспомнить забытые со студенческих времен фамилии: Ахо-Корасика, Бойера-Мура и прочего Кнута-Морриса-Пратта. Еще потребуется подучить алгоритмы сжатия и шифрования;
- Вероятностные алгоритмы: MinHash, SimHash, HyperLogLog, Count-Min Sketch, фильтр Блума и вот это все;
Помимо перечисленного багажа, нужно освоить концепции динамического программирования, научиться решать олимпиадные задачи (некоторые работодатели дают их на собеседованиях), а также иметь представление об основах проектной работы. Стоит овладеть азами комбинаторики и численных методов, хотя это уже математика.
Где можно научиться?
Перечисленные выше темы изучаются в вузах, но уже к старшим курсам ударившиеся в современные технологии студенты забывают о классике. У пришедших в программирование из других профессий специалистов теоретический базис тоже хромает, и это вполне естественно. Заполнить пробелы в знаниях помогают книги. В интернет-магазинах доступны неплохие работы: от модной «Грокаем алгоритмы», которую написал Адитья Бхарагава, до классической «Introduction to Algorithms» издательства MIT Press. Некоторым нравится «The Algorithm Design Manual» Стивена Скиены – выбрать есть из чего, но на изучение теории по книгам у работающих программистов не хватает ни времени, ни мотивации. Это тоже вполне естественно.
Не стоит заниматься ̶с̶а̶м̶о̶л̶е̶ч̶е̶н̶и̶е̶м̶ самообучением, когда можно обратиться за помощью к профессионалам. Каждый хорош в своей работе: кто-то умеет писать программы, а кто-то – еще и учить этому других. Если вы хотите получить целостные и системные знания, компания OTUS предлагает IT-специалистам более 60 авторских курсов. Сейчас идет набор на пятимесячную программу онлайн-обучения « Алгоритмы и структуры данных »: вступительное тестирование можно пройти на сайте . Желающим также предлагают посетить бесплатный демо-урок , который пройдет 22 января.
Теоретический базис – фундамент вашей карьеры, а дом без фундамента построить невозможно.
Как быстро подготовиться к вопросам по алгоритмам на IT-собеседовании — отвечают эксперты
Как в сжатые сроки подготовиться к собеседованию по алгоритмам? На этот вопрос вам подробно ответят наши эксперты.
Когда знаешь, что на собеседовании будут задавать вопросы про алгоритмы, хочется хорошо подготовиться в сжатые сроки и понять, что вообще нужно повторить. Мы решили спросить у экспертов, как быстро подготовиться к такому собеседованию.
Как быстро подготовиться к вопросам по алгоритмам на IT-собеседовании?
Игорь Павлов
руководитель группы разработки Waves NodeНачните с поиска примеров возможных вопросов в Интернете и самостоятельно порешайте задачи. Что нужно повторить в первую очередь:
- Структуры данных — массивы, списки, деревья, двоичное дерево поиска, очереди, стек, хэш-таблица (конечно, нужно знать, что такое хэш). Как устроен каждый тип структур данных. Обратите внимание на то, какие структуры данных лучше всего подходят для конкретных задач.
- Алгоритмы сортировки — метод пузырька, сортировка Хоара (quick sort), сортировка слиянием. Здесь необходимо понимание и способность объяснить, как работает каждый из алгоритмов.
- Алгоритмы поиска — линейный и бинарный (метод деления пополам).
Затем нужно вспомнить или разобраться со сложностью алгоритмов и стандартных операций со структурами данных (доступ, вставка, удаление, поиск элементов). Ключевые слова для поиска: «O» большое, временная сложность алгоритма.
Думаю, что знаний по этим вопросам должно будет хватить для прохождения первичного собеседования, однако требования к специалистам могут отличаться от компании к компании.
Рейтинг полезности ответа:
Даниил Каневский
директор по аналитике компании GoodsForecastЧтобы быстро подготовиться к такому собеседованию, представьте себя на месте работодателя: чаще всего он задаёт вопросы по алгоритмам, чтобы понять, хорошо ли вы соображаете и насколько легко сможете решать самые разнообразные аналитические задачи. Быстро научиться хорошо соображать, к сожалению, невозможно. Но можно потренироваться, чтобы «расшевелить мозги» и вспомнить кое-что, чему учили в университете.
На интервью в GoodsForecast мы в основном предлагаем решать задачи трёх типов:
- Базовые алгоритмы и их алгоритмическая сложность. Например: какие вы знаете алгоритмы сортировки массивов, чем одни лучше других и почему? Помимо сортировки, это могут быть основы дискретной математики, теории графов и т. д. Если вы сильно «плаваете», исправить это быстро будет сложно, но вспомнить университетский курс или почитать специальную книжку точно не будет лишним.
- Задачи «на сообразительность», не требующие специальных знаний, но требующие гибкости, мышления и логики. Лучше всего их решают «олимпиадники», но даже если вы к ним не относитесь, навык решения подобных заданий можно натренировать. Задач такого типа полно в Интернете, решайте их десятками, чем больше, тем лучше.
- Геометрические задачи. Например, как найти геометрическое место точек, равноудалённых от концов заданного отрезка. Для тренировки можно взять хороший задачник по геометрии для 9-го класса. Уверяю вас, получите удовольствие.
Удачи на собеседованиях и хорошей работы!
Рейтинг полезности ответа:
Сергей Сердюкметодист образовательного курса «Андроид-разработчик» университета онлайн-профессий «Нетология», главный разработчик «Альфа-банка»
Фундаментально и быстро к собеседованию подготовиться довольно сложно, но возможно. Как бы я стал готовиться и на какие моменты обратил внимание при подготовке?
День 1
Рекомендую начать с тем, которые вам нужно вспомнить/почитать/посмотреть. Выберите сами:
- что такое сложность алгоритма, какая бывает;
- от чего зависит потребляемая память алгоритма и его скорость;
- как самому рассчитать вышеперечисленные признаки.
День 2
Повторите базовые алгоритмы сортировки:
- пузырьком;
- выбором;
- слиянием;
- быстрая сортировка.
Обязательно посмотрите примеры кода и визуализацию.
День 3
Обязательно пройдитесь по базовым алгоритмам поиска:
- поиск в хэш-таблице;
- бинарный поиск;
- деревья (красно-чёрное дерево).
В интернете довольно много вариантов реализации этих алгоритмов на разных языках. Нужно посмотреть каждый из них на примерах и, конечно, визуализацию. Почитайте про их сравнение и детально разберитесь в работе каждого.
День 4
Рассмотрите применение алгоритмов на практике — где применяются деревья и почему? Отмечу, что (в зависимости от специфики собеседования) существуют узконаправленные алгоритмы, например, для параллельной обработки данных, блокчейн, алгоритмы машинного обучения. Важно выбрать направление и просмотреть материалы, отражающие сегодняшние тренды определённой технологии.
День 5
Берите план и кратко пересказывайте коллеге всё то, что освоили/повторили/изучили за предыдущие 4 дня.
Если у вас в запасе больше двух месяцев на подготовку, я рекомендую пройти следующие курсы:
- практика на HackerRank;
- специализация Algorithms на Coursera;
- специализация Data Structures and Algorithms на Coursera.
Желаю успехов на собеседовании!
Рейтинг полезности ответа:
Данил Головизин
продакшн-директор digital-агентства RutorikaСамое главное: если вы никогда не работали с алгоритмами — от быстрой подготовки толку не будет. Программист должен уметь распознавать алгоритмы в бизнес-задачах, выводить собственные и знать, какие алгоритмы используются в его инструментах. Если вы просто погуглили популярные алгоритмы, на собеседовании вас подловят на вопросе, для ответа на который нужен боевой опыт. Лучше сразу сказать, что у вас небольшой опыт работы с алгоритмами, и получить работу с другими компетенциями.
А если с опытом всё в порядке — просто освежите теорию по алгоритмам сортировки (от простых вроде пузырька до гибридных) и алгоритмам поиска (алгоритмы бинарных деревьев, алгоритмы хэш-таблиц).
Рейтинг полезности ответа:
Итак, как быстро подготовиться к собеседованию, на котором будут задавать вопросы по алгоритмам?
Если вы ничего не знаете, то лучше так и скажите — толку от изучения всей доступной теории с нуля не будет. Если у вас с этим всё не так плохо, то повторите базовые структуры данных, алгоритмы сортировки и поиска. Изучите их реализации, вспомните, в чём их разница и в каких случаях стоит их применять. Попробуйте разобраться, почему тот ли иной алгоритм эффективнее в конкретно взятом случае. Закрепите знания на практике — решайте побольше задачек.
Помните, что при должном уровне усердия и подготовки у вас обязательно всё получится!
Напоминаем, что вы можете задать свой вопрос экспертам, а мы соберём на него ответы, если он окажется интересным. Вопросы, которые уже задавались, можно найти в списке выпусков рубрики. Если вы хотите присоединиться к числу экспертов и прислать ответ от вашей компании или лично от вас, то пишите на experts@tproger.ru, мы расскажем, как это сделать.
Грокаем алгоритмы: Гайд по алгоритмам для тех, кому сложно решать задачи
Эта статья — для разработчиков, которые частично уже знают алгоритмы. Если вы еще не знакомы с ними, советуем пройти трек «Алгоритмы и структуры данных» в Хекслете. Вы изучите списки, стеки, очереди, структуры данных, которые помогут проектировать структуры и алгоритмы.
Бесплатные курсы по программированию в Хекслете
- Освойте азы современных языков программирования
- Изучите работу с Git и командной строкой
- Выберите себе профессию или улучшите навыки
Грокать алгоритмы или не грокать? Что делать, если вам не хочется решать сто задач к вашему следующему собеседованию?
Часть меня ненавидит технические собеседования, в первую очередь из-за того, что мне нужно повторять много материала. Кроме того, в процессе самого собеседования мне часто приходится предлагать какое-то особенное решение, а не то, которое я бы выбрал в своей будничной практике.
Несмотря на это, я люблю алгоритмы и люблю решать задачки по программированию. Для меня это веселое времяпровождение и хорошая тренировка для мозга. Учитывая все это, хочу рассказать вам о моей собственной технике подготовки к собеседованиям, которая намного интереснее и волнительнее, чем обычная подготовка.
Коротко расскажу о себе, чтобы вы убедились в моей экспертности. Я программирую уже 20 лет, за это время я много раз менял место работы. Всего я прошел около 30 воронок найма — больше 120 собеседований. Плюс к этому у меня есть опыт с той стороны баррикад: я провел около 300 технических собеседований и больше 200 собеседований по системному дизайну .
Где мы грокаем алгоритмы
Если вы когда-нибудь искали работу, то знаете, что есть ресурсы, которые собирают задачи с собеседований . Один из них — LeetCode, это самый популярный сайт, где очень много задач. Плюс вокруг него сложилось развитое сообщество, где можно обсуждать задачки с другими инженерами. Если выдается свободная минутка, я всегда не прочь провести ее на LeetCode. Там я решаю задачи или читаю чужие решения, после чего сравниваю со своими.
Самая большая проблема LeetCode в том, что сайту не хватает продуманной системы обучения. У него много разных задач, в которых легко потеряться. Сколько нужно таких задач, чтобы подготовиться к собеседованию? Я бы предпочел двигаться по продуманной программе, в конце которой я смогу ощутить уверенность в собственных знаниях. Но системы нет, а я ленивый, и вообще — не хочу решать 500+ задач.
Одно из популярных решений для этой проблемы — решать задачи, которые относятся к одной структуре данных (например, прорешать несколько задач с деревьями). Какая-то система обучения появляется, но это решение меня все равно не устраивает. Например, что делать, если задачу можно решить при помощи разных структур данных?
Какую систему обучения придумал я
Я бы предпочел такую систему, в которой задачи распределены по паттернам, а не по структурам данных. Мои любимые паттерны — скользящее окно, нахождение цикла и топологическая сортировка. Когда я научился пользоваться этими методами, я стал решать незнакомые задачи по аналогии с задачами, которые решал до этого. Благодаря этому весь процесс подготовки к собеседованиям стал более интересным и веселым. Ну и конечно же, более систематичным.
Я обнаружил 25 паттернов, которые лежат в основе решения большинства задач. Думаю, эти паттерны помогут кому угодно показывать на собеседованиях красивые и элегантные решения. Вся фишка этих паттернов в том, что понимая один из них, вы научитесь решать сразу несколько задач, десятки задач.
Самые распространенные паттерны для решения задач
- Метод скользящего окна
- Метод двух указателей
- Нахождение цикла
- Интервальное слияние
- Цикличная сортировка
- In-place Reversal для LinkedList
- Поиск в ширину
- Поиск в глубину
- Двоичная куча
- Подмножества
- Усовершенствованный бинарный поиск
- Побитовое исключающее ИЛИ
- Top K Elements
- K-образное слияние
- Задача о рюкзаке 0-1
- Задача о неограниченном рюкзаке
- Числа Фибоначчи
- Наибольшая последовательность-палиндром
- Наибольшая общая подстрока
- Топологическая сортировка
- Чтение префиксного дерева
- Задача: количество островов в матрице
- Метод проб и ошибок
- Система непересекающихся множеств
- Задача: найти уникальные маршруты
Читайте также: Это снова я, резиновая уточка: что такое метод Фейнмана и почему с его помощью так просто изучать программирование
Метод скользящего окна
Контекст: Мы используем этот метод, когда у нас есть входные данные с заданным размером окна.
Задачи для этого паттерна:
- Longest Substring with K Distinct Characters
- Fruits into Baskets
- Permutation in a String
Метод двух указателей
Контекст: Мы используем два указателя, чтобы перебрать все входные данные. Обычно два указателя движутся в противоположных направлениях с фиксированным интервалом.
Задачи для этого паттерна:
- Squaring a Sorted Array
- Dutch National Flag Problem
- Minimum Window Sort
Нахождение цикла
Контекст: Еще этот алгоритм называют алгоритмом черепахи и зайца. В отличие от предыдущего метода, два указателя тут движутся с разной скоростью.
Задачи для этого паттерна:
- Middle of the LinkedList
- Happy Number
- Cycle in a Circular Array
Интервальное слияние
Контекст: Этот метод применяют, если есть пересекающиеся интервалы. Например, на этом изображении мы видим, что интервалы a и b могут пересекаться шестью разными способами:
Задачи для этого паттерна:
- Intervals Intersection
- Conflicting Appointments
- Minimum Meeting Rooms
Цикличная сортировка
Контекст: Если входные данные лежат в заданном интервале, используйте цикличную сортировку.
Задачи для этого паттерна:
- Find all Missing Numbers
- Find all Duplicate Numbers
- Find the First K Missing Positive Numbers
In-place Reversal для LinkedList
Техника: Эта техника описывает эффективный способ перевернуть связи между узлами в LinkedList (класс Java). Часто мы ограничены in-place, то есть мы должны использовать исходные узлы.
Задачи для этого паттерна:
- Reverse every K-element Sub-list
- Rotate a LinkedList
Поиск в ширину
Контекст: Это метод для решения задач с деревьями.
Задачи для этого паттерна:
- Binary Tree Level Order Traversal
- Minimum Depth of a Binary Tree
- Connect Level Order Siblings
Поиск в глубину
Контекст: Тот же, что для предыдущего метода.
Задачи для этого паттерна:
- Path With Given Sequence
- Count Paths for a Sum
Двоичная куча
Контекст: Во многих задачах у нас есть набор элементов, который можно разделить на две части. Тогда мы могли бы выяснить, какой элемент является наименьшим в первой куче и какой является наибольшим во второй куче.
Задачи для этого паттерна:
- Find the Median of a Number Stream
- Next Interval
Подмножества
Контекст: Если задача требует перестановки или комбинаций элементов, используйте подмножества.
Задачи для этого паттерна:
- String Permutations by changing case
- Unique Generalized Abbreviations
Усовершенствованный бинарный поиск
Контекст: Эта техника использует логический оператор для наиболее эффективного поиска элементов.
Задачи для этого паттерна:
- Two Single Numbers
- Flip and Invert an Image
Наибольшее K элементов
Контекст: Эта техника используется, чтобы найти наибольший/наименьший или наиболее часто встречающийся набор k-элементов в коллекции.
Задачи для этого паттерна:
- ‘K’ Closest Points to the Origin
- Maximum Distinct Elements
Читайте также: Как решить задачу, если непонятно, с чего вообще начать: советы от Хекслета
K-образное слияние
Контекст: Используйте эту технику, если у вас есть список отсортированных массивов.
Задачи для этого паттерна:
- Kth Smallest Number in M Sorted Lists
- Kth Smallest Number in a Sorted Matrix
Рюкзак 0-1
Контекст: Этот паттерн используют для задач на оптимизацию. Используйте эту технику, чтобы выбирать элементы, которые дают максимум выгоды в данном наборе ограничений по вместимости. Учитывая то, что каждый элемент может быть выбран лишь единожды.
Задачи для этого паттерна:
- Equal Subset Sum Partition
- Minimum Subset Sum Difference
Неограниченный рюкзак
Контекст: То же самое, что в предыдущем паттерне, но только каждый элемент может быть выбран повторно сколько угодно раз.
Задачи для этого паттерна:
- Rod Cutting
- Coin Change
Числа Фибоначчи
Контекст: Как очевидно из названия, это паттерн для чисел Фибоначчи. Это последовательность, в которой каждое последующее число равно сумме двух предыдущих чисел.
Задачи для этого паттерна:
Наибольшая последовательность — палиндром
Контекст: Имеется в виду задача, которая может быть использована как для последовательности, так и для строк . По сути это задача на оптимизацию.
Задачи для этого паттерна:
- Longest Palindromic Subsequence
- Minimum Deletions in a String to make it a Palindrome
Наибольшая общая подстрока
Контекст: Как понятно из названия, это паттерн для работы со строками или другими последовательностями, а также для работы с наборами строк или последовательностей.
Задачи для этого паттерна:
- Maximum Sum Increasing Subsequence
- Edit Distance
Чтение префиксного дерева
Контекст: Это специфичная для структуры данных техника, с помощью которой читают или создают префиксное дерево.
Задачи для этого паттерна:
- Longest Word in Dictionary
- Palindrome Pairs
Острова в матрице
Контекст: Этот паттерн подходит для чтения любого двумерного массива, где нам нужно обнаружить связанные между собой элементы.
Задачи для этого паттерна:
- Number of Distinct Islands
- Maximum Area of Island
Путь проб и ошибок
Контекст: Этот паттерн подойдет для того, чтобы пройтись по массиву в поисках подходящего под требования элемента.
Задачи для этого паттерна:
- Find Kth Smallest Pair Distance
- Minimize Max Distance to Gas Station
Система непересекающихся множеств
Контекст: Если данные раскиданы по непересекающимся множествам, то они решаются одним и тем же способом.
Задачи для этого паттерна:
- Number of Provinces
- Bipartite Graph
Поиск уникального маршрута
Контекст: Этот паттерн подойдет для прохождения по любому многомерному массиву.
Задачи для этого паттерна:
- Find Unique Paths
- Dungeon Game
Бесплатные курсы по программированию в Хекслете
- Освойте азы современных языков программирования
- Изучите работу с Git и командной строкой
- Выберите себе профессию или улучшите навыки