с чего начать изучение алгоритмов
Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных
Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.
Лекция 1. Основы
Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.
Лекция 2. Элементарные структуры данных
Вторая лекция посвящена изучению элементарных структур данных. В начале даётся определение понятия «абстрактного типа данных». Далее лектор рассказывает о том, что такое амортизационный анализ и каковы его особенности.
Лекция 3. Сортировки (часть 1)
Лекция 4. Сортировки (часть 2)
Лекция 5. Хеш-таблицы
Из этой лекции вы сначала узнаете, что такое метод поиска хешированием, какие бывают хеш-функции (в том числе хеш-функции строк). Затем идёт подробное рассмотрение хеш-таблиц и способов их применения: что они собой представляют, каковы основные методы разрешения коллизий (метод цепочек и метод открытой адресации), а также методы вставки, удаления и поиска элементов. Напоследок проводится сравнение хеш-таблиц по затратам времени и памяти.
Лекция 6. Деревья
Последняя лекция в рамках курса АиСД посвящена таким структурам данных, как деревья. Разумеется, в начале лекции дается определение понятия «деревья», рассматриваются их характеристики и приводятся примеры. Затем вы узнаете, как деревья представлены в памяти, какие есть способы обхода дерева. Далее рассматриваются так называемые двоичные деревья поиска и группа самобалансирующихся деревьев: декартовы и АВЛ-деревья. И в завершение лекции рассказывается об абстрактном типе данных «ассоциативный массив».
Как освоить алгоритмы?
Чтобы что-то было сделано компьютером, нужно указать ему, как это сделать. Нужно написать программу с пошаговым объяснением: какие задачи компьютер должен выполнить и каким образом. В этом нам помогают алгоритмы.
Алгоритмы — это набор инструкций, используемых компьютерами для решения тех или иных задач, ведущих к достижению конечной цели.
Знание алгоритмов имеет важнейшее значение для создания и разработки эффективных компьютерных программ. В этой статье я хотел бы поделиться своим опытом изучения алгоритмов в университете и рассказать о том, как он помог мне в учебе и карьере.
Первое знакомство
Я начал программировать, когда ещё учился в средней школе. А первые шаги делал, создавая калькуляторы и светофоры на Visual Basic. Позже освоил HTML и Java. В то время я разрабатывал настольные и веб-приложения. Я просто писал хоть какой код, о внутренней логике и не задумывался.
Поступив в университет на специальность компьютерных наук, на втором курсе я начал изучать структуры данных и алгоритмы. Это был обязательный курс, поэтому его должен был пройти каждый.
Из программиста в разработчики
Изучение структур данных и алгоритмов стало поворотным пунктом в моём понимании компьютерного программирования: теперь я думал больше как инженер-разработчик, а не как программист. Почему я так говорю? Приведу несколько примеров.
Пример 1: алгоритмы сортировки
Алгоритмы сортировки — это одна из базовых тем, которую в первую очередь проходят на курсе по изучению структур данных и алгоритмов в университете.
Различают следующие алгоритмы сортировки:
Изучив различные алгоритмы сортировки, я понял, что для каждой задачи нужен свой алгоритм сортировки. Все алгоритмы сортировки различаются по временной сложности, которая зависит от размера данных. Наибольшее значение имеет их время выполнения при разработке приложений, даже если это всего лишь несколько секунд. Кроме того, я узнал о внутренних алгоритмах сортировки (сортировка элементов на месте) и внешних алгоритмах сортировки (требуют дополнительного пространства для хранения элементов во время сортировки). Всё это заставило меня тщательно обдумывать выбор алгоритмов сортировки для каждого конкретного приложения, принимая во внимание ограничения по времени и памяти.
Пример 2: синтаксический анализ математических выражений
При вводе какого-нибудь математического выражения в калькулятор или в ячейку электронной таблицы, например MS Excel, оно автоматически вычисляется, и мы получаем ответ. Вы когда-нибудь задумывались о том, как это выражение высчитывается? А вот нам пришлось разработать программное обеспечение для работы с электронными таблицами и реализовать парсер выражений. Именно тогда я узнал о популярном алгоритме сортировочной станции. В нём используется очередь для хранения значений и стек для хранения операторов. Я узнал о реальных приложениях, в которых применяются такие структуры данных, как очереди и стеки (изучал их на курсе по структурам данных и алгоритмам), и понял лежащую в их основе логику. Меня так и распирала гордость оттого, что удалось самостоятельно реализовать алгоритм сортировочной станции, хотя таких реализаций тогда было уже полным-полно. 😃
Пример 3: списки, множества и словари
Когда нужно сохранить кучу значений, я применяю списки. Раньше я не задумывался, нужно ли соблюдать очерёдность или нужно ли допускать дубли: просто использовал список для всего подряд. Узнав о том, что, помимо списков, существуют ещё словари и множества, я понял, что всё это можно применять в различных сценариях. Так, сделав правильный выбор в той или иной ситуации и отдав предпочтение, скажем словарю, можно фактически ускорить выполнение кода. Например, если надо проверить принадлежность элемента, гораздо быстрее это будет сделать во множестве или словаре (на это требуется константное время), чем при использовании списка (требуется время, пропорциональное длине списка). Кроме того, список допускает наличие дублей, в то время как множество — нет.
Всё это примеры из моего опыта, иллюстрирующие переход от мышления программиста к мышлению инженера-разработчика. Когда я делал выбор в пользу более подходящей структуры данных или более быстрого алгоритма, происходило значительное улучшение производительности моего кода.
С чего начать?
Изучаем концепции программирования
Прежде чем приступать к изучению алгоритмов, я бы порекомендовал освоить такие понятия программирования, как переменные, функции, классы и особенно понятия объектно-ориентированного программирования (ООП). Это будет вашим фундаментом для понимания более продвинутых концепций из области компьютерных наук.
Осваиваем алгоритмы и их принципы работы
Анализ временной и пространственной сложности — это очень важная тема, которую необходимо освоить, чтобы анализировать алгоритмы. Затем можно перейти к более продвинутым алгоритмам, таким как алгоритмы на графах.
Самое важное — чётко понимать, что происходит внутри алгоритма. Раньше я брал простые примеры и применял алгоритм, чтобы посмотреть, что происходит на каждом его шаге. Проработка примеров помогала мне лучше понять, что происходит в алгоритме, причём мне никогда не приходилось эти алгоритмы запоминать. Если меня попросят написать псевдокод для алгоритма, я смогу легко связать его с примером и проработать его, вместо того чтобы запоминать каждый шаг.
Погружаемся в код с головой
На курсе нам предлагалось реализовать различные структуры данных с нуля, используя основные их операции. Например, двоичные деревья поиска (BST) в C++ с операциями вставки, удаления, поиска, обхода с предварительной выборкой, обхода с отложенной выборкой и обхода с порядковой выборкой. Приходилось создавать класс BST и реализовывать все эти операции в виде функций. Предлагалось даже сравнивать время выполнения определённых операций с различными размерами наборов данных. Это был отличный опыт. Я многому научился благодаря этим занятиям и стал лучше разбираться в операциях. Такой учебный процесс с практическими заданиями помог мне лучше понять концепцию алгоритмов.
Можно начать программировать с языков, поддерживающих ООП. Это легко с очень простыми в освоении языками:
Для новичков один из этих языков будет в самый раз.
Ресурсы для обучения
Онлайн-курсы
Можно заниматься дистанционно на:
и многие другие платформы. Для лучшего понимания можно попробовать приведённые там упражнения.
Средства интерактивной визуализации алгоритмов
Кроме того, можно попробовать платформы визуализации алгоритмов:
Они доступны в Интернете и понимают пошаговый механизм работы алгоритмов.
Упражнения на закрепление
Освоив азы, можно переходить к практическим занятиям, закрепляя пройденный материал в упражнениях. Вот платформы, на которых собраны очень хорошие задачи самых разных уровней сложности:
Чем больше практики, тем лучше понимание. Закрепление учебного материала в упражнениях — это хороший способ узнать, как изученные теории можно применить в решении задач.
Подводя итоги
Резюмируем статью списком из десяти рекомендаций для тех, кто приступает к изучению алгоритмов:
Дополнительные материалы для чтения
Если хотите узнать больше о структурах данных и алгоритмах, то можете ознакомиться со следующими статьями:
Заключение
Не забывайте о том, что путь к совершенству — практика!
Надеюсь, для вас эта статья была полезной и познавательной.
Про алгоритмы для новичков
Если вы когда-либо слышали, что алгоритмы нужно знать всем разработчикам, но что это такое представляете с трудом – вам сюда.
Для опытных программистов некоторые понятия, в том числе и алгоритмы, настолько фундаментальны, что не возникает даже мыслей о том, что, то или иное определение может оказаться непонятным, сложным или вообще, пугающим, для новичка.
Алгоритм – вызывает ассоциации ни то с логарифмами, ни то с арифметикой.
И это слово действительно пришло из математики и использовалось для описания алгоритма Евклида, который применяется для нахождения наибольшего общего делителя двух целых чисел.
Если говорить нормальным языком, алгоритм – это пошаговая инструкция, где результат прошлого шага строго определен и используется в качестве входных данных для следующего шага.
Однако, поскольку в реальной жизни при написании программы совсем нечасто нужно искать общий делитель у целых чисел, раскладывать на множители и вообще думать о математиках, творивших в 300-е года до н.э., рассмотрим немного более жизненный пример применения алгоритмов.
Давайте представим, что телефонный справочник все еще актуален (да, тот бумажный, если вы их застали). Допустим, мы хотим набрать Николая Должанского. Принимая во внимание, что Николай есть в телефонном справочнике, мы можем найти его номер несколькими различными способами.
Метод полного перебора или линейный/последовательный поиск
Самый простой способ найти что-то в списке – пройти по нему по порядку, сравнивая с искомым значением. То есть:
1. Надежда Александрова –> не подходит
2. Николай Алексеев –> не подходит
И так далее, пока вы не найдете наконец Николая Должанского. Вероятно, понадобятся десятки и даже сотни операций сравнения. То есть, если вы захотите поболтать с Ярославом Яковлевым, то это займет порядком больше времени.
Как вы уже поняли, смысл алгоритма линейного поиска заключается в простом переборе значений от начала списка и до конца (или искомого результата). Это брутфорс. Этот алгоритм крайне прост и может возникнуть множество ситуаций, где его использование будет иметь смысл.
Например, если нужно найти телефон приятеля не в целой книге, а, предположим, на клочке бумаги, где помимо его номера всего десяток других записей – пройти список сверху вниз, в этом случае, будет умным решением.
Поиск по частям
У большинства людей просто не хватит терпения перебирать весь справочник. Поэтому они пойдут более прагматичным путем – будут разделять книгу на части.
Процесс деления на части предполагает сначала нахождение основной области, где, предположительно, находится искомое значение. Мы тут все еще ищем Николая Должанского.
Поиск начнем, перелистнув книгу на 30 страниц вперед. Мы увидим, что все фамилии начинаются на «Б». Перейдем еще на 60 вперед и увидим «Г». Достоверно известно, что «Г» находится прямо перед «Д», а значит, Коля где-то рядом и с этого момента мы будем двигаться осторожнее.
Этот алгоритм описывает, как большинство людей ищут что-то в справочниках. Но поскольку мы, люди, часто выбираем неоптимальные пути решения задач, рассмотрим правильный подход к делению на части – бинарный алгоритм поиска.
Бинарный алгоритм поиска
Вот это уже звучит серьезно, да? На самом деле, ничего сложного. Бинарный поиск предполагает, что мы будем делить исходный массив данных пополам, отбрасывать ту часть, где искомого значения быть не может и делить остаток пополам снова, пока область поиска не сократится до минимально возможной.
В терминах телефонной книги, работа будет строиться следующим образом. Наш справочник содержит 400 страниц. Даже если мы все еще ищем Николая Должанского, который находится на 136 странице, мы можем воспользоваться бинарным поиском. Делим книгу пополам и по счастливой случайности попадаем прямо между буквами «М» и «Н» на 199 и 200 страницах соответственно. Мы знаем, что буква «Д» в алфавите находится перед «М», так что справедливо будет утверждение:
Николай Должанский находится на странице между 0 и 199
Ту часть, что начинается с «Н» мы выбрасываем.
Далее, мы делим на две части первые 200 страниц телефонного справочника и видим, что попали мы прямо на страницу с буквой «Г», а «Г», как известно, идет перед «Д». То есть нам снова стал известен неоспоримый факт:
Телефон Николая Должанского находится между 99 и 199 страницами
И вот, стартовав с 400 страниц, мы, всего через две операции сравнения, сократили область поиска на 3/4. Учитывая, что телефон Коли находится на 136 странице, нам предстоит сделать следующие операции:
Еще 6 сравнений. Чтобы рассчитать количество операций необходимых для нахождения нужной страницы бинарным поиском, мы можем взять логарифм от количества страниц с основанием 2 и получим:
то есть, округлив, в худшем случае – 9 операций сравнения. Рядом с исходным числом страниц, конечно, ерунда. Но давайте поговорим о по-настоящему серьезных книгах. Пусть в нашем справочнике будет не 400, а 4 000 000 страниц. Попробуйте представить, сколько операций сравнения нам потребуется? На самом деле, немного:
то есть, 22 раза нужно будет провести сравнение частей справочника, прежде, чем 4 000 000 превратятся в 1.
Сравните скорость работы линейного и бинарного алгоритмов поиска для такого количества страниц.
Заключение
В общем, так и со всеми алгоритмами. Изучение алгоритмов – это изучение способов решать проблемы и задачи наиболее оптимальным путем. Алгоритм – это решение, рассмотренное со всех сторон и преобразованное в эдакий todo-list действий, которые нужно совершить, чтобы воспроизвести его.
И отдельная тема, это преобразование алгоритма в код на конкретном языке, ведь в разных языках алгоритмы (особенно поисковые) могут реализовываться по-разному. Иногда, это может быть уже встроенная в язык функция, которая выдаст нужный результат из массива одной строкой, а где-то понадобиться пара-тройка десятков строк.
И, для примера, вот так будет реализован бинарный поиск на Ruby:
Как я изучал структуры данных и алгоритмы для собеседования в FAANG
Продолжая тему устройства в FAANG, которую уже мы поднимали в нашем блоге, и специально к старту нового потока нашего курса по алгоритмам сегодня делюсь описанием пути Эско Обонга, старшего инженера-программиста Uber.
Эта история началась в 2015 году, когда стартап, к которому я присоединился как «сотрудник-основатель», закрылся через шесть месяцев после первого раунда инвестиций, и я искал новую работу. Первое моё собеседование было с Codecademy, где на этапе телефонного разговора меня заверили: «Не волнуйтесь, мы не задаём сумасшедших вопросов об алгоритмах или что-то в этом роде». И я им поверил…
Во время собеседования было два раунда вопросов об алгоритмах, которые в ретроспективе были чрезвычайно простыми. Я помню, как один из собеседников спросил, как пройти из точки A в точку И по сетке. Я понятия не имел, как это сделать, поэтому наделал какой-то ерунды. Написал на доске бесконечный цикл while:
В цикле точка меняла направление на каждой итерации в зависимости от того, столкнулась ли она со стеной, цикл прерывался, если не находилась конечная точка. Внутри себя мой собеседник, похоже, думал: «WTFFF», но сохранял хладнокровие и продолжал обсуждать мои идеи.
Фиаско в Codecademy открыло мне глаза на пробелы в моих знаниях. Два с половиной месяца спустя я прошёл телефонный скрининг в Google, Uber, Shutterstock и Rent the Runway. Были собеседования на месте в Shutterstock, Rent the Runway и Uber – и я прошёл их все. Google перенёс моё собеседование на две недели вперёд в последнюю минуту. К тому времени у меня уже было три предложения, и я был в восторге от Uber, поэтому я нажал на спуск – присоединился к Uber.
Я прошёл с нуля до профессионального уровня всего за несколько месяцев, но не делал ничего особенного, только последовательно учился. Вот почему я твёрдо верю, что любой инженер может справиться с этими вопросами об алгоритмах и структурах данных и попасть в F.A.A.N.G. или на аналогичные должности с высокой зарплатой. Сначала казалось, что мне не хватает квалификации, потому что для собеседования приходилось усердно учиться. В 2019 году, после того как я управлял собственной консалтинговой фирмой и стартапом в течение почти двух лет, я решил вернуться к постоянной работе и оказался в том же положении, что и в 2015 году.
На этот раз у меня было больше друзей в Uber и других ведущих компаниях, таких как Google и Facebook, которые помогли мне понять суть дела. Так же усердно пришлось учиться им всем. Даже тем, кто не бросил колледж, как и я.
Учиться приходилось всем тем, кто остался, окончил курсы по алгоритмам и получил степень в области компьютерных наук.
Я отказался от представления о мифическом инженере, который может по щелчку пальцев пройти техническое собеседование, и начал понимать реальность ситуации: технические собеседования похожи на SAT [прим. перев. — «Scholastic Aptitude Test» и «Scholastic Assessment Test», дословно «Академический оценочный тест») — стандартизованный тест для приема в высшие учебные заведения в США] в школе. Не важно, что вы потратили четыре года, чтобы изучить всё, чему учатся в старшей школе. Если вы хотите сдать экзамен, вам всё равно нужно подготовиться. Как и в случае с SAT, все ваши прошлые работы и оценки не влияют на результат. Ваш успех полностью зависит от того, насколько хорошо вы сдали тест.
Как только я понял истину, что учиться нужно всем, то обрёл достаточно мотивации, чтобы трудиться усердно. Я понял, что труд обучения – это именно то, чем заняты мои конкуренты. Это послужило толчком, чтобы сформировать процесс обучения, который помог мне пройти все технические тесты и собеседования в 2019 году. Я бросил колледж и прошёл технические тесты Stripe, Coinbase и Triplebyte. Прошёл скрины и собеседования на местах в Google, Amazon, Uber (снова), Reddit, Squarespace и Braze. Я не ждал, что пройду всё идеально, но считаю, мне помогло то, что я сосредоточился на основных принципах.
Google отправляет вам сувениры, когда вы проходите собеседование.
Переход не был плавным. Когда я только начал готовиться к собеседованию, мне потребовалось более 2 часов, чтобы почти решить задачу, которую теперь можно было бы назвать «leetcode easy», а в то время это казалось невозможным! Я искренне верил, что просто недостаточно умён от природы и мне придётся учиться ещё усерднее, чтобы достичь уровня, на котором смогу решить задачу с той же скоростью, что и инженер Google. Я понял одно: мне нужно практиковаться.
Чего я не понимал, так это того, что такого уровня сложности и разочарования вначале следует ожидать всем начинающим, включая инженеров Google.
Я всё тот же человек. Единственная разница между мной тогда и сейчас – практика, практика, практика. У людей часто возникает вопрос: «Как мне учиться?» Трудно понять, с чего начать, что делать дальше, добиваетесь ли вы прогресса, и ещё труднее оставаться на верном пути. Чтобы решить многие из этих вопросов, когда я учился, я создал доску Trello со всеми темами, которые хотел охватить. Доска помогла мне сосредоточиться на самых важных темах и управлять временем, чтобы прогресс был стабильным.
Я написал пост о доске Trello в LinkedIn, этот пост стал вирусным. Менеджер Trello связался со мной по поводу создания для него официального шаблона Trello, который теперь находится здесь: Interview Study Tracker.
Чтобы учиться, в трекере есть шаблон. Он требует определения списка тем и двух или более ресурсов, которые могут научить чему-то по теме. Затем нужно задать себе 2–3 практических задачи, чтобы укрепить понимание. Задачи могут быть из любого источника, главное – это сам контент. Я нашёл большую часть своего контента с помощью простого поиска в Google, темы были ключевыми словами.
Изучайте одно и то же с разных точек зрения, это поможет лучше понять тему. Например, о двоичных деревьях поиска я бы прочитал статью на geeksforgeeks.org, а также главы о них в Cracking the Coding Interview. Затем я задал бы себе 2–3 практических задачи, или достаточно задач, чтобы почувствовать себя комфортно, прежде чем двигаться дальше.
Мой экземпляр «Cracking The Coding Interview 6th Edition», подписанный Гэйл Лакман Макдауэлл
Список тем для изучения
Ниже привожу список почти всех структур данных и алгоритмов, с которыми вы можете столкнуться во время технического собеседования, а также очень краткое описание и некоторые ресурсы – с их помощью можно приступить к составлению плана обучения. Цель списка – дать вам отправную точку, чтобы вы разработали план, а не подробно объяснять, что представляет собой каждая тема. Часть вашего плана – найти ресурсы, чтобы узнать больше о каждой теме с разных точек зрения.
Если вы не слышали о некоторых структурах данных в списке или мало что знали о них раньше, они могут показаться сложными. Но по мере продвижения вы почувствуете примерно то же, что чувствовали, когда узнали о массивах.
Эти структуры данных – всего лишь основные строительные блоки, которые помогают создавать алгоритмы, они на самом деле упростят работу, если вы потратите время на то, чтобы понять их. Подобно тому, как массив выполняет большую часть работы, чтобы поддерживать список элементов, эти структуры имеют функции и контейнеры, чтобы эффективно работать с данными.
Базовые структуры данных
Они считаются основными. Каждый должен знать, как они работают и когда их использовать, как их реализовать, знать аргументы в их пользу и компромиссы, которые за ними скрываются:
Продвинутые структуры данных
После освоения базовых структур данных, знание этих, более продвинутых, даст вам больше шансов на успех. Некоторые из них очень часто всплывают на собеседовании, например, кучи или бинарное дерево поиска. Кэши LRU и префиксные деревья появляются реже, но становятся всё более распространёнными. Непересекающиеся множества и списки с пропусками всплывают редко, но не важно, спрашивают ли о них явно. Они могут оказаться мощными инструментами, которые помогут вам найти быстрые и эффективные решения.
Кучи, также известные как очереди приоритетов, – это тип дерева, которое ведёт себя как очередь. Бинарное дерево поиска (BST) – это дерево, которое ускоряет поиск узлов. AVL и красно-чёрные деревья – два популярных специфических типа сбалансированных BST. Кэш LRU – это кэш с эффективным использованием памяти, он создаётся объединением Hashmap [прм. перев. — хэшмэпы — специфический тип хэш-таблицы] со связным списком. Trie – это ещё один тип дерева, который ускоряет поиск по подстроке. Непересекающиеся множества – это особый тип множества, которые разделяют элементы на неперекрывающиеся подмножества, полезные для алгоритма поиска объединения. Skip List – это оптимизированный LinkedList, он сокращает время поиска определённых узлов.
Основные алгоритмы поиска и обхода
Все структуры данных создаются, чтобы хранить информацию. Некоторым из них нужны специальные способы эффективного доступа к этой информации. Они сложнее, чем простой доступ по индексу массива или ключу хэшмэпа. Структуры данных, которые содержат коллекции данных, например деревья и графы, для доступа к внутренней информации используют несколько основных алгоритмов:
Продвинутые алгоритмы поиска и обхода
В этой области проводится много исследований, но для целей технического собеседования наиболее продвинутые алгоритмы поиска, с которыми вы, вероятно, столкнётесь:
Алгоритмы сортировки
Сортировка – это распространённый инструмент, используемый для повышения производительности решения. Существует множество алгоритмов сортировки, но самые популярные на собеседовании перечислены ниже. Нужно знать, как реализовать всё это, никуда не подсматривая:
Важные темы
Рекурсия – крайне важная тема, которая не так часто поднимается в повседневной разработке программного обеспечения, как во время собеседований. Поначалу битовые манипуляции могут показаться пугающими, но, как только вы потратите время, чтобы понять формат двоичных чисел и операции, вы поймёте, насколько это просто.
Распространённые шаблоны
Эти шаблоны можно использовать, чтобы разобраться со многими алгоритмами:
Математические задачи
Другие общие задачи
Практика
Самостоятельная практика
Обучение ничего не значит без практики. Каждый раз, когда вы изучаете новую тему из своего учебного плана, вы должны использовать знания из неё. Это поможет вам лучше запомнить тему, даст понимание глубже. Задайте самому себе несколько практических задач по каждой завершённой теме. На таких сайтах, как leetcode.com, можно найти практические вопросы, воспользовавшись тегами «trees» или «graphs».
Практика должна проходить в два этапа. Первый – когда вы изучаете тему впервые. На этом этапе вы должны сосредоточиться на реальном понимании того, что задействовано в решении и почему оно работает. Второй этап – после того, как вы освоите понятия. На этом этапе вы должны рассчитать время и стремиться ко всё более быстрому решению.
Во время собеседования вы должны решить задачу за 15–45 минут в зависимости от сложности. Вначале вам, скорее всего, понадобится несколько часов, чтобы решить первую задачу. В первые несколько недель это время должно начать сокращаться. Через месяц или два месяца постоянной практики (а не просто времени) вы должны научиться решать приличное количество задач вовремя. Иногда ваша задача – реализовать единственную структуру данных, например LRU-кэш или Trie. В других случаях нужно выполнить только одну операции над структурой данных, например удаление элемента в двоичном дереве.
Практикуйтесь в реализации всех упомянутых здесь структур данных до тех пор, пока вам не придётся ничего искать, и вам будет очень легко отвечать на перечисленные выше вопросы, когда собеседование будет настоящим. Сосредоточьтесь на понимании того, почему код написан именно так, а не на попытках запомнить код точно. Когда вы пишете код, исходите из понимания того, что должно произойти дальше, а не ориентируйтесь по памяти. Вероятно, вас не попросят реализовать массив или сбалансированные деревья BST, такие как деревья АВЛ/красно-черные, но вы должны знать, как они работают.
Практика с ассистентом (имитация собеседования)
Одной практики по темам и вопросам недостаточно. Во время собеседования вы будете общаться с реальным человеком, который оценивает ваши навыки прямо здесь и сейчас. Это ситуация более напряжённая, чем когда вы учитесь дома. Чтобы обойти неловкость и беспокойство настоящего собеседования, заранее проведите много имитационных собеседований. Это поможет вам чувствовать себя комфортно и сосредоточиться на вопросе собеседования, а не отвлекаться на что-то нетехническое. Вы можете попросить друга помочь вам или найти в Интернете сервис, который подберёт вам человека, чтобы пройти имитационное собеседование.
Когда вы будете готовы?
Вы никогда не почувствуете себя «готовым», как бы долго вы ни учились. Всегда есть множество тем, в которые можно погрузиться глубже, или требующие больше практики слабые места. Во всем этом определённо есть элемент удачи. Вполне возможно, что вам зададут вопрос по теме, к которой совсем не подготовились или где очень слабы. Также возможно, что вы получите все вопросы по темам, в которых вы действительно сильны два месяца назад, и вам не нужно было тратить дополнительное время на изучение, чтобы сдать экзамен. Вы не можете подготовиться ко всем возможным исходам, но ваши шансы на успех будут выше, чем у других, если вы будете больше практиковаться.
Очень важно отслеживать прогресс и получать обратную связь, чтобы знать, когда вы действительно готовы выступить на настоящем собеседовании, не полагаясь только на эмоции. Следите за временем выполнения, когда вы задаёте себе практические задачи, и старайтесь не более 40 минут на ответы на большинство вопросов среднего уровня и 1 час на ответы на сложные вопросы на leetcode.com или hackerrank.com.
Большая часть кода на собеседовании оценивается на небольшом наборе крайних случаев, и небольшие ошибки всегда пропускаются или считаются несущественными. Люди не ждут совершенства, но они должны увидеть достаточно «сигналов», чтобы убедиться в том, что вы подходите. Пройдите как минимум три фиктивных собеседования, прежде чем идти на настоящее. Двигайтесь вперёд только в момент, когда сможете стабильно хорошо работать во время тренировки.
Крупные технологические компании нанимают сотрудников постоянно, поэтому они могут очень гибко планировать или переносить дату собеседования. Я перенёс свои собеседования в Google и Uber на 2 и 1 месяц соответственно, потому что не был готов. В прошлом я делал ещё более длительные переносы. Чтобы перенести собеседование, не нужно никаких особых оправданий. Я просто говорил: «Мне нужно больше времени на подготовку». Эти компании тратят много денег на ваше собеседование. 5–6 штатным сотрудникам платят за собеседование в течение 4–5 часов с последующей оценкой результатов. Учитывайте зарплаты рекрутеров, они нашли время, чтобы найти вас и обработать лишь небольшой процент заявок от людей, которые прошли через них, и это как минимум несколько тысяч долларов за собеседование. Компании хотят, чтобы люди приходили подготовленными. Они будут ждать, а не тратить время, деньги (и не только их) на отказ от инженера, который мог бы подойти, если бы они просто подождали ещё месяц или два. Так что отложите мероприятие, если не готовы. Никогда не идите на собеседование, не будучи готовым!
Если вы будете следовать вышеизложенному, узнать, когда вы готовы, будет легко. Возможно, вы всё ещё чувствуете, что не готовы, но вы будете знать наверняка, потому что знаете свой темп и прошли множество имитационных собеседований. Быть готовым означает, что вы, несомненно, на практике доказали, что можете проходить собеседования, на которых задаются те же самые сложные вопросы, в те же сроки, что и на настоящем собеседовании.
В этой статье рассматриваются только вопросы о структурах данных и алгоритмах. Вопросы проектирования систем и вопросы о поведении также играют большую роль, когда принимается решение о найме. Эти темы я оставлю для другой статьи.
Книги
Сайты
Буткэмпы
Практика
Самостоятельная работа
Надеюсь, данная статья была вам полезна. Главная мысль, которую я хотел донести — чтобы устроиться на работу в ведущую технологическую компанию, вам не нужно специальное высшее образование (хотя оно будет полезно), гены счастливчика или длинный послужной список. Единственное, что вам нужно, – это уделять время последовательному обучению и практике и не забывать про промокод HABR, который добавит дополнительно 10% к скидке на баннере.