Будьте готовы, если вы проходите собеседование в Stripe

Ужасное собеседование по программированию на доске. Мы все это ненавидим, но все должны признать это.

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

Проведя время в нескольких разных странах, я создал крепкую сеть друзей, занимающихся программным обеспечением, в Лондоне, Нью-Дели, Сан-Франциско, Чикаго, Сингапуре, Берлине и Мюнхене.

В этом случае я делюсь тем, чем поделились в моей сети - вопрос, заданный в интервью Google.

Вопрос

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

Ввод 1: [0, 1, -2, 2, 4]

Выход 1: 3

Вот пример 2:

Ввод 2: [1, 2, 3, 4]

Результат 2: 5

Вот пример 3:

Ввод 3: [2, 3, 4]

Результат 3: 1

Решение

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

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

Поскольку 1 - это наименьшее положительное целое число, оно всегда будет нижней границей нашего диапазона, и при условии, что в худшем случае, если массив содержит все положительные числа, следующее возможное положительное целое число будет равно 1 + длина входного массива. Это очевидно, если мы посмотрим на Пример 2; поскольку берутся все положительные целые числа вплоть до длины массива, наименьшее возможное целое число равно длине входного массива (5). Давайте применим это решение на практике:

В приведенном выше решении мы создали новый массив и инициализировали его, чтобы в нем был ноль, позже вы поймете, почему. Когда мы просматриваем входной массив numbers, если целое число положительно, мы добавляем его в наш служебный массив positiveIntegers по индексу целочисленного значения. Поскольку в нашем массиве уже есть 0, и поскольку мы добавляем числа в наш массив только в том случае, если они положительны и существуют в массиве numbers, может быть 2 сценария:

  1. Либо в нашем массиве positiveIntegers есть пробелы, то есть в мире JavaScript некоторые элементы в массиве наши undefined, поэтому мы найдем наименьшее возможное отсутствующее положительное целое число.
  2. Или в нашем массиве нет пробелов, и, таким образом, если мы дойдем до конца нашего массива, мы можем логически заключить, что наименьшее возможное положительное целое число, которое отсутствует, является следующим, и, таким образом, мы вернем длину нашего массива, которая может быть равна до numbers.length + 1 или numbers.length, в зависимости от того, содержит ли numbers какие-либо отрицательные целые числа или zero.

Это решение работает и имеет временную сложность O (n). Однако я хотел бы, чтобы вы подумали, что произойдет, если мы получим этот ввод:

[1, 1000000]

Наша функция будет работать правильно и даст нам результат 2, но можете ли вы представить себе размер массива, который нам придется создать во время этого решения, при выполнении нашей функции наш массив positiveIntegers будет выглядеть так:

[0, 1, undefined, undefined, undefined, undefined, ..., 1000000]

Таким образом, даже несмотря на то, что наша временная сложность будет O(n), наша пространственная сложность будет сомнительной, я не знаю, как выразить ее в большой нотации O: O(x)?

Улучшенное решение

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

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

А как насчет разных движков JavaScript?

Я знаю, что движок Google V8 JavaScript реализует Set и несколько других структур данных, таких как Map, с использованием внутренних хэш-таблиц. Эта статья подробно описывает их реализацию. Однако, поскольку в документации ECMAScript 2015 говорится:

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

Таким образом, это означает, что если вы программируете для браузеров Node.js, Google Chrome / Chromium или любого другого браузера, который использует движок Google V8, ваш код будет работать с временной сложностью O (n) как получение значений объекта Set, т.е. метод set.has(x) то, что мы использовали, будет иметь только O(1) / постоянное время. Но если вы программируете для старого браузера, вам, возможно, придется переосмыслить свое решение, и вполне возможно, что этот старый браузер даже не поддерживает Set реализацию, которая поставлялась только с ES6. Тем не менее, на собеседовании по программированию, если вы продемонстрируете понимание структуры данных HashSet, интервьюер не будет заботиться о реализациях для конкретного языка.

Однако на практике вы можете реорганизовать этот код, чтобы он работал с простым объектом JavaScript и вообще не использовал реализацию Set. Это должно быть довольно легко, особенно если вы понимаете логику того, что мы сделали в нашем окончательном решении. Или, что еще лучше, вы можете использовать более традиционный язык, такой как Java, где есть только одна реализация структур данных, таких как HashTable и HashSet.

Если я что-то упустил, оставьте комментарий ниже! И если вам нравится такой контент, следуйте за мной здесь, потому что у меня есть еще вопросы, которые я собираюсь опубликовать, чтобы помочь вам отточить свои навыки программирования на доске!

Примечание от JavaScript In Plain English:

Мы всегда заинтересованы в продвижении качественного контента. Если у вас есть статья, которую вы хотите отправить в JavaScript In Plain English, отправьте нам электронное письмо по адресу [email protected] с вашим именем пользователя Medium, и мы добавим вас в качестве автора.

Мы запустили три новых издания! Проявите любовь к нашим новым публикациям, подписавшись на них: AI на простом английском, UX на простом английском, Python на простом английском - спасибо и продолжайте учиться!