TIS в моем первом техническом интервью. Вот что я узнал.

Сегодня я провел свое первое техническое интервью с Spaced и
едва мог вспомнить, как console.log()пускать в одиночку найти оптимальное решение.

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

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

Сегодня я провел свое первое техническое телефонное собеседование во время написания кода в реальном времени, но я
надеюсь, что мой момент «Сегодня я разошелся» (TIS) превратится в «Сегодня я узнал» (TIL) после прохождения моего собеседования. Тут ничего не происходит…

Эта проблема

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

Например, для массива [5, 2, 1, 4, 0, 2] функция должна вернуть 3.

Все просто, правда? Пусть начнется интервал.

Где я ошибся

Хм, с чего мне начать? Как только интервьюер закончил объяснение вопроса, началась внутренняя паника. Я не мог думать.

Внутренний монолог: ДУМАЙ, Марин, ДУМАЙ. Почему вы даже не пытаетесь думать о проблеме? Ага! Google всегда знает. Йо, Google, скажи мне, что делать ... Ой, подожди, я должен говорить. Все советы в Интернете говорят, что я должен говорить через свой мыслительный процесс. Ах, ладно, ладно. Я не могу читать и говорить одновременно. Хорошо, до свидания, Google.

Внешний монолог: «Мммм, ах, ну ... посмотрим. Хм. Ага, хм. "

После нескольких минут подшивания и болтовни, а также минуты или двух
молчания я пришел к следующему решению (на JavaScript):

Помните, как я сказал, что даже не могу вспомнить, как console.log()? Что ж, после первой попытки я был сбит с толку, когда Coderpad запустил мою функцию и на экране ничего не появилось. Интервьюер должен был напомнить мне, что он действительно компилируется правильно, мне просто нужно было console.log() , если я хотел увидеть результат в консоли. Дох. Кий лицом к ладони.

Вот и обновил: console.log(count). И вернул правильный ответ! Уахоо! … Могу я пойти домой?

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

ДУМАЙ, Марин. ДУМАЙТЕ. Ну, мое решение - всего лишь один цикл, верно? Loop === Constant был нацарапан на моей распечатке. Поэтому я сказал: «Постоянно, O (n) время», не особо задумываясь об этом.

НЕПРАВИЛЬНО. Да, я написал одну while петлю. Однако мне не удалось распознать функцию JavaScript includes() как нечто иное, чем волшебство. Когда интервьюер подтолкнул меня к этому вопросу, я понял, что includes() также каждый раз перебирает массив. Так что на самом деле его временная сложность O (n²). Сигнал лицом к ладони второй раунд.

На какое-то короткое мгновение колеса начали вращаться. О каких структурах данных я читал? Связанный список? Не кажется полезным. Куча? Неа. Хеш-таблица? Ага!

К решению

Попытка номер два:

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

Из-за ограниченного оставшегося времени интервьюер спросил меня, как я могу решить эту проблему, используя только массивы. Дин! Я сказал: «Вы можете отсортировать массив, а затем перебирать его, пока не найдется пропущенное число». Вот что я имел в виду:

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

Вздох. Больше практики! Больше интервью! Будьте на связи.

TL;DR

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

Примечание для себя:

  • Обсудите решение, прежде чем писать его. Это может помочь вам быстрее найти более эффективное решение (например, интервьюер может быть чем-то большим, чем просто звуковая доска, иногда он дает подсказки)
  • Да, важно обговорить свой ответ, но не в ущерб окончательному решению. Если нужно, подумайте.
  • Внутренние функции JavaScript - это не волшебство! У них тоже есть временная и пространственная сложность.