Решение наиболее часто задаваемых вопросов Google по интерактивной доске

Более подробный взгляд на наиболее часто задаваемый вопрос по кодированию в Google

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

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

Сегодня мы рассмотрим наиболее часто задаваемый вопрос Google Whiteboarding в 2020 году с использованием метода UMPIRE, который я объяснил в предыдущем посте. Давайте начнем.

Постановка задачи

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

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

Пример:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Кредиты: https://leetcode.com/problems/two-sum/

Понимание проблемы

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

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

Еще одно свойство, на которое я обращаю внимание в данном примере, заключается в том, что каждый элемент в массиве уникален. Всегда ли это будет верно для предоставленных мне массивов? Другими словами, является ли массив [1,1,3,3] допустимым входным массивом? Мы знаем, что мы не можем повторно использовать один и тот же индекс в нашем возвращаемом типе, но вопрос не указывает, могут ли элементы повторяться. В этом случае наш интервьюер сообщит нам, что все элементы будут уникальными. Прохладный. Давайте перейдем к чертежной доске и разберемся с некоторыми подходами.

Наиболее интуитивно понятный для меня подход - взять индекс i и сравнить его со всеми остальными индексами в моем массиве, чтобы проверить, существует ли такой элемент, что arr[i] + arr[other_index]= target

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

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

Это превратится в алгоритм, работающий на O (N * N) или O (N²). Давайте подумаем, как мы можем добиться большего.

Соответствие проблеме

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

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

Хеш-таблицы - это структура данных, состоящая из пары "ключ-значение". В среднем мы можем проверить, существует ли ключ в постоянное время. В формулировке задачи мы хотим вернуть индексы, составляющие наш target, чтобы мы могли сопоставить значение с индексом, в котором мы говорим ключ.

Планирование решения

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

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

Итак, в примере, который мы создали выше, мы ожидаем, что hashTable будет содержать:

{ 
  ‘1’: 1,
  ‘2’: 0,
  ‘3’: 3,
  ‘4’: 2
}

После того, как мы инициализировали это, что еще мы хотим сделать? Все, что нам действительно нужно сделать, это просто пройтись по массиву еще раз и проверить, существует ли дополнение нашего target в нашей хеш-таблице. Другими словами, существует ли target — arr[i] в нашей хеш-таблице? Если это так, отлично, мы нашли решение; в противном случае нам нужно продолжать обходить массив и выполнять эту проверку.

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

Давайте превратим это в компилируемый код.

Реализация вашего решения

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

Рассмотрение вашего решения

На этом этапе собеседования вы хотите использовать пример, созданный на предыдущем шаге, и проследить за своим кодом построчно. Это продемонстрирует вашему интервьюеру, что вы обладаете сильными навыками отслеживания и логики. В качестве упражнения я предлагаю вам проследить мое / ваше собственное решение этой проблемы, прежде чем запускать его на своем компьютере. Некоторые компании, такие как Google и Facebook, не запускают ваш код на компьютере, поэтому этот навык на 100% жизненно важен для развития, в то время как другие компании, такие как Uber и Airbnb, также ожидают, что ваш код будет компилироваться и правильно работать с тестовыми примерами. .

Оценка вашего решения

Хотя мы уже оценили сложность нашего первоначального решения, чтобы признать, что оно было неэффективным, не помешает еще раз отметить сложность пространства и времени выполнения вашего решения после внедрения оптимального решения. Давайте определим N как длину нашего входного массива. Поскольку мы заполняем нашу хеш-таблицу N элементами во всех случаях, мы можем сказать, что сложность нашего пространства равна O (N). Мы также проходим через массив как минимум один раз, поэтому для времени выполнения мы можем обозначить, что в среднем это O (N). Проверка наличия элемента в хеш-таблице в среднем составляет O (1). На самом деле, наша среда выполнения была бы похожа на O (N + (N * 1)), но это сокращается до просто O (N).

Выводы

Способ решения проблемы чрезвычайно важен. Никогда, никогда, НИКОГДА не начинайте проблему, мгновенно кодируя то, что, по вашему мнению, является ее решением.

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