Фронтенд-инженерам тоже нужно изучать алгоритмы
Я хочу перейти на новую работу. Перед собеседованием я подготовил много вопросов по фронтенд-разработке, но не систематизировал знания об алгоритмах.
Я думал, что очень уверен в себе, но не ожидал, что алгоритм сильно пострадает.
Начать интервью
Да, я уверен, что дал правильный ответ, но интервьюер, похоже, не удовлетворился им и даже уставился на меня с презрительным взглядом, как будто смотрел на меня свысока.
Это вопрос на leetcode, вы можете нажать Две суммы, чтобы просмотреть детали вопроса.
Учитывая массив целых чисел и целочисленную цель, вернуть индексы двух чисел так, чтобы они складывались в цель.
Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
Пример 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Пример 2:
Input: nums = [3,2,4], target = 6 Output: [1,2]
Пример 3:
Input: nums = [3,3], target = 6 Output: [0,1]
Ограничения:
- 2 ‹= nums.length ‹= 104
- -109 ‹= числа[i] ‹= 109
- -109 ‹= цель ‹= 109
- Существует только один правильный ответ.
Мой ответ
Друг мой, когда я увидел этот вопрос, я подумал, что это так просто, что даже дал свой ответ за 2 минуты.
Для решения этой проблемы я использовал двухуровневый цикл for
.
const twoSum = (nums, target) => { const len = nums.length for (let i = 0; i < len; i ++) { for (let j = i + 1; j < len; j++) { if (nums[ i ] + nums[ j ] === target) { return [ i, j ] } } } } twoSum([3,2,4], 6) // [ 1, 2 ] twoSum([3,3], 6) // [ 0, 1 ] twoSum([2,7,11,15], 9) // [ 0, 1 ]
Боже мой, что с этим не так, разве это не правильный ответ? Он проходит все тестовые случаи.
В чем проблема?
Это действительно правильный ответ, но не очень хороший ответ, почему? Потому что его временная сложность O(n^2)
.
У нас есть способ уменьшить его временную сложность, чтобы сделать его O(n)
.
Как вы это делаете?
В процессе обхода массива мы можем добавить Map
для записи пройденных чисел и соответствующих им значений индексов. Затем каждый раз, когда проходится новое число, в Map
проверяется, появилось ли уже различие между target
и числом в последнем числе. Если это так, то ответ уже появился, и нам не нужно идти дальше.
Например:
Ввод: числа = [2,7,11,15], цель = 9
Первый обход
Когда мы обращаемся к элементу 2
, Map
является пустым объектом.
В конце визита мы превратили Map
в { 2: 0 }
Второй обход
Когда мы обращаемся к элементу 7
, потому что 9 - 7 = 2
, а Map
содержит именно элемент 2. Таким образом, индекс 2 и индекс 7 - это ответ.
Попробуем написать ответ
const twoSum = function(nums, target) { const map = {} for (let i = 0, len = nums.length; i < len; i++) { const temp = target - nums[ i ] if (typeof map[ temp ] !== 'undefined') { return [ map[ temp ], i ] } else { map[ nums[ i ] ] = i } } } twoSum([3,2,4], 6) // [ 1, 2 ] twoSum([3,3], 6) // [ 0, 1 ] twoSum([2,7,11,15], 9) // [ 0, 1 ]
Вау! Я, наконец, понял, почему интервьюера не удовлетворил мой ответ, и в этот момент я думаю, что он был намного лучше моего.
Спасибо за этот опыт интервью, хотя я всего лишь фронтенд-разработчик, возможно, у меня не так много шансов его использовать, но хорошее изучение поможет мне в будущем.
Дополнительные материалы на PlainEnglish.io.
Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .