Рассмотрение вопроса Two-Sum на интервью по JavaScript

Spread the love

Вступление

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

Two-Sum вопрос

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

Вам предлагается создать функцию, которая принимает два параметра. Первый параметр, nums, представляет собой массив чисел. Второй параметр, total – это одно число. Выходные данные функции должны быть двухэлементным массивом, который представляет собой пару чисел в nums, которые при суммирование равны total.

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (arr, total) => {
  // Solution here
};

Как правило, обычно приводиться пару примеров допустимых комбинаций ввода/вывода:

input: nums = [1, 2, 3], total = 4
output: [1, 3]

input: nums = [3, 9, 12, 20], total = 21
output: [9, 12]

Краткое примечание про написание кода во время интервью

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

  • Может ли nums быть чем-то другим, кроме массива чисел?
  • Может ли total быть чем-то другим, кроме числа?
  • Всегда будет два числа в nums, которые в сумме будут равны total? Если нет, то каким должен быть вывод, когда нет решения?

Для этого поста в блоге мы будем предполагать, что nums всегда будет массивом чисел, total всегда будет числом, и всегда будет решение проблемы (т. е. два числа в nums всегда будут складываться в total ).

Решение прямым перебором (Brute Force)

Нашим первым инстинктом, скорее всего, будет грубая сила. Для этого мы можем использовать следующую процедуру:

  • начать с первого элемента nums и перебрать каждый из оставшихся элементов массива, проверяя, суммируются ли они до total
  • далее если ответ не найден перейти ко второму элементу nums и перебрать каждый из оставшихся элементов, проверяя, составляют ли они в сумме total
  • повторять, пока не будет найдена соответствующая сумма!

В коде мы реализуем это как вложенный цикл:

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (nums, total) => {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === total) {
        return [nums[i], nums[j]];
      }
    }
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

Потрясающие! Есть несколько потенциально сложных аспектов этого решения; давайте быстро разберем их.

Почему внешний цикл останавливается на i < nums.length – 1?

Внешний цикл не должен учитывать последний элемент массива nums, только второй-последний элемент массива. Так как вложенный цикл всегда будет учитывать последний элемент.

Почему вложенный цикл начинается с j = i + 1?

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

Проблема подхода с перебором

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

Так в чем проблема? Вложенные циклы имеют алгебраическую сложность O(n2).

Понимание сложности O(n2)

По существу, сложность O(n2) означает, что время выполнения алгоритма пропорционально квадрату числа входных данных. Это становится очевидным, когда мы еще раз рассмотрим метод перебора: если мы добавляем элемент в nums, наше решение должно пройти через дополнительный элемент в каждом из вложенных циклов, а затем должно пройти дополнительное время через весь двойной цикл.

Давайте проведем эксперимент. Мы создадим массив из 100 000 элементов, причем решающими номерами будут последние два элемента.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

Теперь реализуем наше решение для двух сумм методом перебора, но на этот раз мы будем следить за тем, сколько итераций потребуется, а также приблизительно сколько времени это займет.

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      iterations++;
      if (nums[i] + nums[j] === total) {
        console.log(
          `Iterations: ${iterations}`,
          `Time: ${new Date() - startTime}ms`
        );
        return [nums[i], nums[j]];
      }
    }
  }
};

twoSum(bigArr, total);
// Iterations: 4999950000 Time: 20032ms

Решение для перебора прошло почти 5 миллиардов итераций, и на моем компьютере это заняло 20 секунд. Ужас! Посмотрим, сможем ли мы сделать лучше.

Сила объектов (и, что более важно, хеш-таблицы)

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

Вот пример кода!

const twoSum = (nums, total) => {
  // Keep track of previous array values
  const previousValues = {};

  for (let i = 0; i < nums.length; i++) {
    // What previous value needs to exist for
    // us to have found our solution?
    const complement = total - nums[i];

    if (previousValues[complement]) {
      return [complement, nums[i]];
    }

    // This current array item now becomes
    // a previous value
    previousValues[nums[i]] = true;
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

Возможно, вы спросите: у нас есть только один цикл, конечно, но наш второй цикл заменен этим поиском previousValues[complement]. Это действительно намного эффективнее, чем второй цикл?

Ответ – да, потому что поиск по объекту – имеет сложность O(1). Это связано с использованием JavaScript хеш-таблиц в объектах! Отличный учебник по хеш-таблицам описан в этом прекрасном посте.

Поскольку поиск объекта равен O(1), а первый цикл равен O(n), сложность нашей функции теперь равна O(n). Давайте попробуем наш новый алгоритм на том же большом массиве, который мы использовали ранее.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();

  const previousValues = {};
  for (let i = 0; i < nums.length; i++) {
    iterations++;
    const complement = total - nums[i];
    if (previousValues[complement]) {
      console.log(
        `Iterations: ${iterations}`,
        `Time: ${new Date() - startTime}ms`
      );
      return [complement, nums[i]];
    }
    previousValues[nums[i]] = true;
  }
};

twoSum(bigArr, total);
// Iterations: 100000 Time: 4ms

Теперь все работает гораздо быстрее.

Ничто не бесплатно

Хотя мы уменьшили нашу сложность алгоритма, мы увеличили нашу пространственную сложность, поскольку нам теперь нужно создавать новый объект previousValues в памяти. Для очень больших объектов (например, порядка миллиона элементов) речь будет идти о 10 МБ памяти и более. Но этот выбор за вами!

Оригинальная статья Nick Sciall: Exploring the Two-Sum Interview Question in JavaScript


Spread the love

Рассмотрение вопроса Two-Sum на интервью по JavaScript: 2 комментария

  • 02.09.2019 в 18:14
    Permalink

    Вместо хэш таблицы const previousValues = {}, можно использовать простое множество Set.

    Ответ
  • 12.09.2019 в 16:48
    Permalink

    > поиск по объекту – имеет сложность O(1)
    строго говоря не верно, читаем про колизии

    Ответ

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

Ваш e-mail не будет опубликован.