Как использовать эффективное решение распространенного вопроса на собеседовании
Некоторые вопросы на собеседовании по коду касаются не только поиска решения. Иногда предлагается простой вопрос, чтобы посмотреть, сможет ли человек решить его наиболее эффективным способом. Одним из таких вопросов является проблема повторяющихся значений.
По заданному массиву целых чисел найдите первое повторяющееся значение.
Например :
Первый массив имеет два дубликата, 2 и 3, но мы хотим найти первое повторяющееся значение. Повторяющиеся значения находятся в позициях индекса 5 и 6, поэтому возвращается значение в позиции 5, 3. Если в массиве не найдено дубликатов, возвращается null.
Глядя на эту проблему, первый инстинкт ее решения, вероятно, связан с циклами for.
Этот метод грубой силы, безусловно, работает, и найти это решение несложно. Проблема в том, что это не очень эффективно. Каждый элемент массива требует повторения дважды. Следовательно, более длинные массивы требуют больше циклов, следовательно, больше времени для вычисления результата. Было бы намного быстрее, если бы мы могли найти ответ, проходя по массиву максимум один раз без каких-либо вложенных циклов.
Есть несколько способов решить эту проблему, но есть одно решение, которое использует важную концепцию алгоритмов, которую ищут многие интервьюеры. Эта концепция информатики называется хэш-карта. Технически JavaScript не имеет собственной структуры данных хеш-карты, но нечто очень похожее может быть достигнуто с использованием объектов для сопоставления пар ключ/значение.
Имея в виду это знание, мы можем создать объект, затем выполнить итерацию по массиву и присвоить каждый индекс ключу в объекте. Значение, которое мы можем установить на true, указывает на то, что число было проверено.
Используя эту концепцию, мы можем выполнить итерацию по массиву и проверить, существует ли уже число по текущему индексу в качестве ключа в объекте. Если это так, мы вернем это число, если нет, мы добавим его в качестве ключа и перейдем к следующему индексу в массиве.
Сразу видно, что код здесь намного лаконичнее и легче читается. Результаты такие же, как и при использовании вложенных циклов for, но с преимуществом гораздо более высокой эффективности, поскольку он выполняет итерацию по массиву не более одного раза. Хеш-карты — важная концепция для изучения в информатике, а также полезная для решения множества различных алгоритмических задач.
Интервьюеры иногда включают простые вопросы, чтобы увидеть, понимает ли человек больше, чем просто метод грубой силы, и принимает во внимание более сложные концепции и временную сложность. Проблема с повторяющимися ценностями — отличный пример этого, поскольку она дает хорошую возможность показать, что вы знаете, и сообщить работодателю, что у вас есть нужные вещи. Ознакомьтесь с другими алгоритмическими задачами, которые можно решить с помощью этой методологии, и выбейте из парка следующее собеседование!
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Посетите наш Community Discord и присоединитесь к нашему Коллективу талантов.
