как найти наименьшее число, которого нет в массиве

1656524413 kak najti naimenshee chislo kotorogo net v massive

Марин Абернетти

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

1*uGGUGY-TAtzH7-XYMdzzvQ
ID 48395285 © Ojogabonitoo | Dreamstime.com

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

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

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

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

Проблема

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

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

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

Где я ошибся

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

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

Внешний монолог: «Гммм, а, ну… посмотрим. Хммм Да, хм.

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

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

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

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

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

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

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

На пути к решению

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

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

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

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

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

TL; DR

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *