Как научиться решать вопросы на собеседовании по программированию с помощью Leetcode (Часть I)

Введение

Последние 8 лет работаю инженером-программистом. Я провел последние 5 лет, работая в крупных компаниях (Amazon, Google и Facebook), и я рад возможности каждый день учиться создавать программное обеспечение для крупных компаний, которое масштабируется до миллионов запросов в минуту (или даже больше) .

Как инженер-программист, я считаю, что может быть одна вещь, которую вы никогда не будете готовы сделать без надлежащей подготовки (да, даже если вы старший инженер-программист): вопрос на собеседовании по программированию.

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

• Вы находитесь в стрессовой ситуации, обычно вы не пишете/решаете задачу кодирования в подобных условиях;
• Вы должны решить задачу за ограниченное количество времени;
• У вас нет IDE (для многих это не имеет значения, правда)
• Вы не работаете над такими проблемами ежедневно (извините, особенно если вы старший инженер-программист, в итоге вы тратите меньше времени на кодирование)
• Как обычно напоминает рекрутер, вы должны сосредоточиться на определенной стратегии: говорить вслух, объяснять свой мыслительный процесс, задавать вопросы, не переходить сразу к кодированию, показать, что вы можете справляться с двусмысленностью(Мне нравится этот…)

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

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

Цель

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

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

Вопросы на собеседовании обычно возникают из-за реальных проблем, но у вас есть большое преимущество: в большинстве случаев они упрощены и преобразованы в простую область, которую можно понять за несколько минут.

Стратегия

Ключевым моментом вашей подготовки является то, что в конце вы должны уметь:

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

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

Помните: редко когда вопрос настолько сложный, что его нельзя решить за 20–25 минут; поэтому, если ваш алгоритм кажется очень сложным и длинным, я бы очень рекомендовал сделать шаг назад, попросить подсказки (это не плохой знак) и начать заново.

Массивы, карты и наборы

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

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

Прежде всего: спросите себя, поможет ли упорядочение массива, заданного во входных данных, найти решение. Если это так, возможно, вы нашли [sub]-оптимальное решение (я поставил sub-, потому что в некоторых случаях ваше решение для заказа будет не лучше, чем O( nlogn) но на самом деле может быть что-то лучше).

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

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

Используйте массив, когда ваш входной домен равен [0.. n-1], чтобы само значение можно было использовать для указания на другие места самого массива. (например, массив содержит 5 элементов типа 0 4 1 3 2 — вы можете использовать значения внутри массива для перехода из одной позиции в другую). В этом случае вы также можете отметить его значения, чтобы проверить, выполняются ли определенные условия. (например, если все входные значения [0.. n-1] несортированного массива положительны, то каждый раз, когда вы встречаете число i, вы можете инвертировать его соответствующую позицию в массиве, чтобы вы знаете, что вы видели число i ранее).

Используйте массив, если задача требует, чтобы вы исследовали все входные данные один раз — O(n) — и вы можете просто проверить, всегда ли должно выполняться условие.

Используйте набор, когда вам нужно что-то проиндексировать и проверить, присутствует ли что-то (например, найти дубликаты).

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

Используйте карту, если вам нужно проиндексировать элементы, например, если вы хотите узнать, какую позицию занимает каждый элемент.

Списки

Переворачивание списка

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

Это становится немного сложнее, когда вы хотите перевернуть часть списка, но в этом случае вы просто применяете широко распространенную стратегию:

• Придумайте упрощенную задачу (весь список) и попытайтесь ее решить;
• Примените ограничения;
• Решите алгоритм как решение подзадач вместе.

Вот упражнение, где вы можете попрактиковаться в этом подходе.

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

Позвольте мне дать вам несколько идей для связанного упражнения:

1. Подумайте, как использовать две вложенные рекурсивные функции;
2. Найдите k элементов, чтобы развернуть их и развернуть (примечание: отсоедините последний узел от следующего, чтобы у вас фактически был список из k узлов, которые вы можете полностью развернуть) и рекурсивно вызовите функцию для присоедините следующий узел следующего перевернутого списка
3. Вам нужно сохранить важные узлы в переменных, отсоединить «последний» узел от следующего и сохранить его следующий в другой переменной, потому что этот следующий фактически будет следующим узлом из что функция будет вызываться рекурсивно (да, очень сложно сказать это словами :))
4. Попробуйте набросать код в виде макросов…
5. Вы можете перевернуть весь список (в данном случае из k элементов), используя рекурсию

...и если вам интересно, как перевернуть связанный список без рекурсии, вот фрагмент кода:

Найдите среднюю точку списка

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

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

Матрицы

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

Когда ваш ввод представляет собой матрицу, в зависимости от вопроса вы можете рассмотреть следующее:

• если в вопросе рассматривается локальность, можете ли вы начать применять свою стратегию к первым двум строкам, получить результат, а затем итеративно применять его к каждой следующей строке?
• Можете ли вы представить матрицу как гистограмму?
• Вам нужно пройти матрицу по диагонали? Если да, то вот фрагмент, который позволит вам сделать это (примечание: обход по диагонали немного сложен, он требует использования одного единственного индекса со смещением — но имейте в виду границы, если матрица не возведена в квадрат)

• вы можете рекурсивно перемещаться по матрице. Вы определяете рекурсивную функцию, которая принимает на вход (среди прочих) i и j и сначала увеличивает i, пока не будет достигнут конец строки а затем сбрасывает его при увеличении j.
• для задач, подобных судоку, вы можете рассчитать индекс на основе квадранта матрицы с помощью такой формулы, как (i/3)*3+(j/3)
• Поворот матрицы:вы можете использовать стратегию очистки луковицы. Для каждого «слоя» матрицы вы выбираете всего четыре элемента (по одному с каждой стороны) и меняете их местами. Это должно быть как-то интуитивно понятно, вам просто нужно обратить внимание на условия остановки.

Стеки и очереди

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

Аналогично проталкиванию, процесс извлечения из стека происходит до тех пор, пока не будет выполнено определенное другое условие.

Здесь упоминаются два примера успешного использования стеков.

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

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

Индексы

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

Вы можете использовать более одного индекса, если существует принцип локальности, который ведет к решению проблемы.

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

• Жадный подход: вы расширяете, насколько можете, а затем сжимаете
• Фиксированный размер: вы интуитивно перемещаете начальный и конечный индексы одновременно.

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

• Вам нужно найти цикл
• Вам нужно найти повторяющееся число (есть несколько способов решить эту проблему, медленный/быстрый индекс не самый интуитивный)
• Вам нужно найти средний элемент в списке за O(n) (один индекс перемещается на 1, другой перемещается на 2)

Вы также можете использовать левый/правый индекс: наиболее распространенное применение — реализация быстрой сортировки. Эти индексы начинаются в противоположных направлениях и движутся друг против друга.

Чтобы найти пару элементов, diff которых равен определенному значению k в отсортированном массиве, вы также используете два указателя. В этом случае идея состоит в том, что вы сохраняете i фиксированным и продолжаете увеличивать j до тех пор, пока либо diffравноk, либо больше. Если он больше, нет смысла продолжать увеличивать j; вы можете только увеличить i и оставить j там, где оно есть (вы не сбрасываете j, потому что вы уже точно знать, что diff ‹ k — помните, что массив отсортирован).

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

Скользящие окна/последовательности

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

Используйте раздвижные окна, когда:

• Вам нужно найти последовательный шаблон в массиве или строке
• У вас есть фиксированное количество вещей, которые вы можете взять (например, не более k видов фруктов из списка деревьев), поэтому вы должны максимизировать их.

Для более сложных вопросов вам может понадобиться использовать карту для отслеживания положения/частоты элементов, содержащихся в окне.

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

Некоторые из наиболее распространенных примеров:

• найти самую длинную подстроку, содержащую не более k различных символов
• найти минимальную подстроку окна

Чтобы найти непрерывную максимальную сумму в массиве с отрицательными числами, хитрость заключается в том, что вы можете использовать два указателя и сохранить переменные runningSum и max. Вы обновляете указатель i до последнего индекса j в тот момент, когда обнаруживаете, что runningSum становится отрицательным (нет смысла сохранять эту сумму, так как это ухудшит ее для будущих сумм). Во всех остальных случаях вы просто увеличиваете j.

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

Поиск последовательностей в массиве

Если последовательность связана с соседними числами, то обычно проблема может быть решена линейно с более чем одним указателем (или, в худшем случае, легко с O (n²))

Когда подпоследовательность состоит из чисел в разных позициях, вам нужно прыгать с одного места на другое, и это обычно будет O (n³)). Так что в этом случае может помочь массив карт. Вы можете построить карту для каждого элемента массива: карта содержит информацию о текущем элементе с его предыдущим. Таким образом, эта карта может быть использована последующими элементами. Это напоминает о динамическом программировании.

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

проблема максимума скользящего окна может быть решена за линейное время с некоторыми наблюдениями (используя ArrayDeque — O(1) для опроса с хвоста и начала):

• Вы всегда должны оставлять в очереди только те элементы, которые находятся в диапазоне окна
• Вы обязательно всегда удаляете элементы из хвоста, которые меньше вставляемого нового, потому что они наверняка не понадобятся для ответа.
• Вы вставляете элемент в очередь, если он меньше элемента в хвосте (потому что на самом деле вы не знаете… он может стать следующим большим в следующем окне)

Упражнения с последовательностями могут иметь множество вариаций. Самая длинная последовательная последовательность предлагает найти самую длинную последовательную последовательность чисел (5,6,7,8,9,…) в неупорядоченном массиве. Это означает, что либо вы заказываете (что делает это тривиальным), либо вы действительно используете некоторую логику, чтобы понять это:

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

Сопоставление с образцом

Скользящие окна, последовательности, подстроки всегда имеют что-то общее: они также связаны с сопоставлением шаблонов.

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

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

Идея сопоставления с образцом состоит в том, чтобы выполнить итерацию по строке S, чтобы заполнить карту букв того же размера, что и карта P, с той же частотой. Когда вы сталкиваетесь с картой, удовлетворяющей критериям, вы просто обновляете результат с помощью кратчайшей длины указателей l(left) и r(right), которые вы используете для навигации в S.

Общее правило сопоставления с образцом: когда важна частота, проверки размера карты или набора недостаточно. Таким образом, чтобы выполнить условие совпадения, вам также необходимо проверить частоту: по этим причинам увеличивайте на 1 переменную, которая проверяет, находится ли значение в обеих картах, только когда частота совпадает.

Например: у вас есть pMap, представляющий шаблон («A»:1, «B»: 2, «C»: 1), а затем вы создаете sMap для строки s для навигации. Как только вы нашли символ B в s, вы не увеличиваете переменную foundCharacters напрямую, а ждете, пока когда частота также не совпадет.

Некоторые ключевые моменты о сопоставлении шаблонов:

• Попробуйте использовать массив, где каждая позиция указывает букву, а ее значение - частоту
• Попробуйте создать уникальный номер для каждой уникальной строки, чтобы вы могли использовать скользящее окно и выполнять поиск по строке за линейное время (например, сопоставление строк ДНК — см. Алгоритм Рабина-Карпа ниже).
• Попробуйте использовать два указателя: расширяйтесь, пока вы идете к цели, сжимайтесь, когда любое из условий снова нарушается.
• Иногда вам нужно создать класс эквивалентности, который представлен значением. Например, класс эквивалентности сдвинутых строк (например, «abc» == «bcd» == «xyz») представлен строкой, сдвинутой с использованием смещения, вычисленного из str.chatAt (0) — 'а'. Таким образом, все эти строки будут одинаковыми, если они принадлежат к одному и тому же классу эквивалентности.

Алгоритм Рабина-Карпа

Это очень известный алгоритм, используемый, например, для поиска ear в предложении «Доу меня слышит» — в этом случае вам нужно найти точную строку (вы знаете символы и длину). поэтому вы можете предварительно вычислить хэш-функцию для каждой подстроки длиной 3 (в данном случае), а затем вычислить следующую, вычитая значение удаляемого символа и добавляя новое значение.

Например, если текущая подстрока hea → 'h' * 128² + 'e' * 128 + 'a', чтобы перейти к ear, вы просто делаете это → ( хэш(hea) — 'h'* 128²) * 128 + 'r'

Эту задачу также можно обозначить как «Найди иголку в стоге сена».

Интервалы

Сортировка интервалов обычно помогает решать проблемы с интервалами. Сведение интервала в один массив также обычно помогает:

• Либо вы создаете массив, индексы/размер которого относятся к диапазонам интервалов
• Или вы создаете массив, который содержит Integer[] — первое значение — это начало/конец диапазона, второе значение — это само значение, связанное с этим диапазоном (поставьте его отрицательным, если он заканчивается диапазоном).

Проблема Конференц-залов II — нечто среднее между концепцией интервала и распределением. На самом деле, хорошей стратегией является либо сортировка, а затем сведение массива, чтобы затем вы подсчитывали максимальное количество комнат, которые вы должны выделить (путем +1 или -1, перемещаясь по сглаженному массиву), либо вы сортируете его снова, а затем используете min-PQ (Priority Queue), который содержит использованные/созданные до сих пор комнаты и помещает в качестве peek() комнату, которая будет освобождена первой. Таким образом, вы знаете, что если есть комната, которую вы можете использовать, это будет комната в peek(), в противном случае никакая комната не может быть использована, и вы создаете новую.

Найдите пересечения между интервалами

Если вам нужно найти минимальное количество комнат для уроков в разное время или минимальное количество стрел для стрельбы воздушными шарами, которые находятся в 2D-пространстве, вы можете использовать жадный подход, сортируя интервалы на основе конечное значение. При жадном подходе вы принимаете лучшее локальное решение, которое (поскольку интервалы отсортированы) приводит к лучшему общему результату.

Вывод

Это конец первой части моей серии статей «Давайте поделимся моими заметками с другими». Я планирую написать еще 3 части после этого (я сделал более 30 страниц заметок).

Надеюсь, это может быть полезно и вдохновляюще для тех, кто в настоящее время готовится к собеседованию по программированию :)