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 - это не волшебство! У них тоже есть временная и пространственная сложность.