Фронтенд-инженерам тоже нужно изучать алгоритмы

Я хочу перейти на новую работу. Перед собеседованием я подготовил много вопросов по фронтенд-разработке, но не систематизировал знания об алгоритмах.

Я думал, что очень уверен в себе, но не ожидал, что алгоритм сильно пострадает.

Начать интервью

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

Это вопрос на 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]

Ограничения:

  1. 2 ‹= nums.length ‹= 104
  2. -109 ‹= числа[i] ‹= 109
  3. -109 ‹= цель ‹= 109
  4. Существует только один правильный ответ.

Мой ответ

Друг мой, когда я увидел этот вопрос, я подумал, что это так просто, что даже дал свой ответ за 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 .