Руководство по выживанию в Leetcode

На этой неделе я преодолел 500 задач Leetcode. В честь этого я хотел написать статью о том, как я пережил 500 задач Leetcode, которые включают некоторые из самых умопомрачительных структур данных (union find) и алгоритмов (topological sort, kadane’s algorithm и другие).

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

Оглавление

• Руководство
  • Руководство
  • То, что я сделал хорошо
  • То, что у меня не получилось
• ЧАСТО ЗАДАВАЕМЫЕ ВОПРОСЫ
  • Начинаю с нуля
  • Не могу решить проблемы самостоятельно
  • Сколько задач я должен решить, чтобы добиться хороших результатов?
  • LC Premium
  • Чертежный планшет для заметок
  • Язык программирования для Leetcode
  • Глубокое знание языка программирования
  • Застрять на несколько часов, пытаясь придумать решение
  • Сложность пространства
  • Если бы у меня была одна неделя на подготовку к собеседованию
• До и Донты
• Ресурсы
  • Решать
  • Учиться

Руководство

Большинство людей путают простоту с отсутствием вещей. Простота — это отсутствие всего ненужного, устранение всех сложностей и концентрация на самых важных деталях. Здесь я представляю вам простое руководство, которое поможет вам подготовиться к большим техническим собеседованиям.

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

Руководство, которое я написал ниже, предназначено для людей, которые, по крайней мере, знакомы с языком программирования и знают основные структуры данных (массивы, связанные списки, стеки, деревья, графы и т.д.).

Если вы совсем новичок или не уверены в себе, это руководство для вас.

Руководство

Прежде всего, я бы определился со списком задач и начал решать их на Leetcode.

Я сосредоточусь на решении задач только в Leetcode, игнорируя любые другие платформы (сайты соревновательного программирования, такие как codeforces, spoj, google code jam и т.д.).

Моя цель — пройти онлайн-оценку/интервью, а не победить в конкурсах по соревновательному программированию. Хотя конкурсное программирование — это правильный путь, это не основное направление данного руководства. Подготовка, как мне кажется, совершенно другая.

Поскольку Neetcode 150 — мой любимый список, я буду проходить его раздел за разделом. При первом прохождении списка

• Я бы сосредоточился на легких и средних задачах, двигаясь сверху вниз.
• Пропускаю обратный путь, разделы 1-D и 2-D DP и перехожу к графикам.
• Как только я решу все легкие и средние задачи в графиках (в обоих разделах), я перейду к разделам DP и бэктрекингу.
• Если я готовлюсь к собеседованию в Google, я не буду пропускать раздел математики.

После этого следующий шаг будет основан на ситуации.

1. Если предстоит собеседование, я бы сосредоточился на решении часто задаваемых задач компании.
2. Если у меня есть свободное время, я возьму другой список и буду решать задачи из него.

Вот, собственно, и все. Верьте в себя, чтобы стать лучше с регулярной практикой, и вы обязательно добьетесь успеха.

Ниже я привожу несколько разделов, в которых рассказываю о том, что мне удалось сделать за последние пару месяцев, что не удалось (чтобы вы могли избежать подводных камней), часто задаваемые вопросы и обязательные учебные ресурсы.

То, что я сделал хорошо

Последовательная практика.

Вам нужно решить около сотни качественных задач, чтобы иметь шанс решить новые задачи. Когда вы только начинаете, решение одной задачи может занять 2-3 часа вашего времени, даже если вам удалось найти собственное решение. Очень важно решать задачи последовательно, чтобы их количество увеличивалось. Если вы будете решать по одной проблеме каждый день месяца, то в итоге решите 30/31 проблему.

Решение ранее заданных проблем, специфичных для компании

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

Вести учет решенных задач.

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

Если бы мне пришлось искать решение задачи, я бы постарался кратко объяснить решение своими словами.

То, что у меня не получалось

Решение задач наугад

Первоначально я начал с фильтрации задач по темам и решения 5-10 задач из каждого раздела. В этот период я получил возможность пройти собеседование в Amazon на должность SDE-2. Я был, мягко говоря, в полной растерянности. У меня ничего не получалось, и я был уверен, что не смогу пройти онлайн-оценку.

На сайте Leetcode я наткнулся на список задач, упомянутых в статье «Взлом интервью по кодированию». Я почувствовал, что мои способности к решению проблем изменились за одну ночь. Я смог применить шаблоны, изученные в одной задаче, в другой или, по крайней мере, рассмотреть разные шаблоны для решения одной задачи.

В итоге я не смог пройти онлайн-оценку. Я не решил достаточно качественных задач. Тем не менее, это был полезный опыт. С тех пор моя подготовка в основном заключалась в решении задач из популярных списков.

Не начинать сразу

Я потратил один семестр на решение задач с таких платформ, как hackerrank, codesignal и т.д. Честно говоря, я ничего не добился. Я также верил, что смогу пройти собеседование в крупной технологической компании без решения Leetcode. В итоге я все же устроился в приличную компанию, но это не был мой первый вариант.

FAQ

У меня нет образования в области CS, поэтому я не знаком даже с базовыми структурами данных и алгоритмами. Я не знаю, что делать. Как мне подготовиться, чтобы я мог решать задачи Leetcode?

Это может быть довольно сложно, если вы начинающий. Я бы посоветовал вам не торопиться.

Прежде всего, изучите python. Вам нужно будет знать только самые базовые вещи, ничего сложного. Вам не понадобится книга, достаточно будет онлайн-учебника. Для решения задач в стиле Leetcode я бы сказал, что понимание типов данных — это одна из тем, которую легко игнорировать. Поймите интуитивно типы данных и то, как их можно комбинировать.

Затем вы должны изучить и понять структуры данных/алгоритмы/анализ сложности. Выберите что-то из списка «Обучение» и из списка «Проблемы». Изучите тему и попытайтесь решить проблему из этой темы. Здесь вы должны морально подготовиться, как под холодным душем, это будет шок. Вы не сможете решить даже «легкую» задачу.

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

Я решил 50 задач на Leetcode, но не могу придумать собственные ответы, я что-то делаю не так?

Не совсем так, 50 задач — это слишком мало для того, чтобы прочувствовать все типы задач, которые могут быть заданы на собеседовании. Чтобы хорошо решать задачи, вам нужна последовательная и целенаправленная практика. Выберите тему, скажем, массив и решайте качественные задачи.

Высококачественные проблемы — это те, которые часто задавались компаниями в прошлом/те, которые имеют хорошее соотношение «нравится — не нравится». Чтобы облегчить поиск высококачественных проблем, следуйте списку высококачественных проблем (см. ниже)

Сколько задач я должен решить, чтобы стать хорошим?

Это зависит от вашего уровня комфорта, но если вы впервые решаете подобные задачи, я бы сказал, что нужно решить около 100-150 задач (5-10 задач из популярных тем). Как только вы достигнете этой цели, решайте вопросы с метками компании.

По моему мнению, чтобы лучше подготовиться к собеседованию, вам нужно решить наиболее часто задаваемые в последнее время проблемы для компании, в которой вы проводите собеседование. Для этого вам потребуется Leetcode Premium (сокращенно LC Premium).

Если у вас нет LC Premium, вы можете порыться в разделе «Обсуждение», чтобы найти вопросы, задаваемые на собеседованиях в конкретной компании. Именно так я готовился к собеседованию, и это сработало.

Стоит ли LC Premium того?

Я не являюсь спонсором Leetcode, это мое личное мнение, что оно того стоит. Главная особенность заключается в том, что вы узнаете, как часто задавался тот или иной вопрос в компании за последние 0-6 месяцев, что, на мой взгляд, очень важно для подготовки.

Вам не нужен LC Premium, когда вы только начинаете, но стоит подумать о его приобретении, когда собеседования приблизятся, и вы исчерпаете все проблемы, которые нужно решить.

Какой лучший планшет для рисования Leetcode?

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

Блокноты могут быть дорогими. Если вы учитесь в колледже, возможно, на вашем факультете есть канцелярская комната. Если вы хотите купить блокнот, поищите бумагу с заливкой.

Какой язык программирования я должен использовать?

Если вы студент колледжа, я бы посоветовал Python. Это один из самых популярных языков. Благодаря тому, что язык лаконичен, на нем легко написать сложную логику, используя очень мало кода. Если вы опытный профессионал, я бы посоветовал попробовать решить пару задач на языке, который вы используете ежедневно. Если не получится, подумайте о переходе на Python.

Нужно ли мне знать язык программирования досконально?

Нет. Вы должны быть знакомы со структурами данных, которые доступны в выбранном вами языке. Вот список

1. Списки/динамические массивы
2. Стеки
3. Очереди
4. HashMaps/словарь
5. Наборы
6. Кучи
7. Структура данных, которая может поддерживать отсортированный порядок и делать запросы, например, проверить, существует ли значение меньше x, проверить, существует ли значение больше x. В Python вы можете использовать bisect_left и bisect_right, в Java — TreeMap/TreeSets.

Я потратил несколько часов на решение задачи и не могу прийти к решению. Что я должен сделать, чтобы стать лучше?

Раздел обсуждения проблемы — это золотая жила. В большинстве задач есть подробные объяснения проблемы. Вам следует потратить около 15 минут на то, чтобы найти подход к решению проблемы. Если вы найдете высокоуровневый подход, например, поймете, что нужно применить двоичный поиск, потратьте еще 15 минут на составление алгоритма. Если у вас получилось, запишите его в виде кода. Если нет, посмотрите на решение. Не тратьте больше получаса на решение задачи.

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

Должен ли я сосредоточиться на сложности пространства?

Нет, если нет последующего вопроса. Лично я стараюсь оптимизировать пространство, потому что экономия пространства напрямую связана с практической производительностью в реальном мире. Выделение памяти в куче требует огромных затрат, которых по возможности следует избегать.

У меня есть неделя на подготовку к собеседованию, и я не знаю, на какой теме сосредоточиться.

Если вы идете на собеседование в крупную технологическую компанию и у вас всего неделя на подготовку, я бы предложил решить задачи с графами из списка Blind75.

Обычной реакцией было бы решение вопросов по динамическому программированию (DP), но в последнее время я вижу, что графы пользуются большей популярностью. Если у вас есть некоторые продвинутые знания или со временем вы накопите опыт решения задач, вы поймете, что DP по своей сути является DFS с кэшированием.

Если у вас осталось время, сосредоточьтесь на проблемах с массивами, которые включают поиск, сортировку, модификацию массива.

До и не до

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

Вместо этого пройдитесь по коду шаг за шагом без отладчика. Если вам нужно что-то записать, это нормально. Если размер входных данных слишком велик, подумайте, как можно воспроизвести проблему на меньшем наборе данных.

Делайте достаточные перерывы

Выгорание от Leetcode — это реальность. Последовательная практика лучше, чем практика с перерывами. Даже если вы не можете посвящать Leetcode 4-5 часов каждый день, посвящайте один час каждый день. Если не получается решать задачи каждый день, ничего страшного, начните с 2-3 дней в неделю (возможно, в выходные) и освободите время в будние дни. Постарайтесь сделать решение задач Leetcode первым делом в течение дня, а не последним.

Не игнорируйте раздел обсуждения

Время работы Leetcode очень непостоянно, но если ваше решение постоянно работает медленнее, чем 20% всех решений, пора посмотреть ответы в разделе обсуждения. Скорее всего, кто-то сделал это лучше. Незначительные оптимизации/настройки также могут принести много пользы.

Ресурсы

Solve

Моя личная рекомендация, список из 150 проблем от Neetcode.
Вы также можете стремиться к списку из 75 задач на том же сайте. Я бы рекомендовал сначала решить задачи с графами, прежде чем переходить к разделу динамического программирования.

Список моделей leetcode Шона Прасада, вы можете отфильтровать по компании Sean Prasad’s Leetcode patterns

Еще один популярный список Grokking the coding interview problems

Существует онлайн-курс по решению проблем на собеседовании по кодированию

Список OG для решения проблем Cracking the coding interview 6th edition Leetcode problems

Если вам нужна дополнительная практика — Love Babbar’s 450 problems DSA list

Изучайте DSA

Для получения всех необходимых знаний по структурам данных — курс по структурам данных Уильяма Фисета — https://www.youtube.com/playlist?list=PLDV1Zeh2NRsB6SWUrDFW2RmDotAfPbeHu (я бы рекомендовал смотреть до видео номер 37).

Для большинства распространенных алгоритмов, курс «Алгоритмы» от Абдула Бари — плейлист
https://www.youtube.com/playlist?list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O (я бы рекомендовал посмотреть первые 26 видео, чтобы узнать об анализе сложности).

Для всех графовых алгоритмов, которые вам понадобятся для собеседования, плейлисты Graph playlists by William Fiset — https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDGO4—qE8yH72HFL1Km93P.

Пособие по проведению собеседования с техническими специалистами, содержащее исчерпывающий перечень тем и проблем для практики — https://www.techinterviewhandbook.org/algorithms/study-cheatsheet/