Решаем задачу из интервью Google на JavaScript: 4 разных способа

Original author: Bret Cameron
  • Translation


Когда я занимался изучением производительности алгоритмов, мне попалось вот это видео с мок-интервью Google. Оно не только дает представление, как проходят собеседования в крупных технологических корпорациях, но и позволяет понять, как решаются алгоритмические задачи, причем максимально эффективно.

Эта статья — своеобразное сопровождение к видео. В ней я даю комментарии ко всем показанным решениям плюс собственную версию решения на JavaScript. Также обсуждаются нюансы каждого алгоритма.

Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».

Skillbox рекомендует: Практический курс «Мобильный разработчик PRO».

Постановка задачи


Нам дают упорядоченный массив и определенное значение. Затем просят создать функцию, которая возвращает true или false, в зависимости от того, может ли сумма любых двух чисел из массива быть равной заданному значению.

Другими словами, есть ли в массиве два целых числа x и y, которые при сложении равны указанному значению?

Пример А

Если нам дали массив [1, 2, 4, 9] и значение 8, функция вернет false, потому что никакие два числа из массива не могут дать 8 в сумме.

Пример Б

Но если это массив [1, 2, 4, 4] и значение 8, функция должна вернуть true, потому что 4 + 4 = 8.

Решение 1. Брутфорс

Временная сложность: O(N²).
Пространственная сложность: O(1).


Наиболее очевидное значение — использование пары вложенных циклов.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

Это решение нельзя назвать эффективным, так как оно проверяет каждую возможную сумму двух элементов в массиве, а также сравнивает каждую пару индексов дважды. (Например, когда i = 1 и j = 2 — это фактически то же самое, что сравнивать с i = 2 и j = 1, но в этом решении пробуем оба варианта).

Поскольку наше решение использует пару вложенных циклов for, оно является квадратичным с временной сложностью O (N²).


Решение 2. Двоичный (бинарный) поиск

Временная сложность: O(Nlog(N)).
Пространственная сложность: O(1)
.

Поскольку массивы упорядочены, мы можем поискать решение с использованием бинарного поиска. Это наиболее эффективный алгоритм для упорядоченных массивов. Сам по себе бинарный поиск имеет время выполнения O (log (N)). Однако все равно нужно использовать цикл for, чтобы проверить каждый элемент по всем другим значениям.

Вот как может выглядеть решение. Чтобы все было понятно, мы используем отдельную функцию для контроля бинарного поиска. А также функцию removeIndex (), которая возвращает версию массива за вычетом заданного индекса.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
 
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2); 
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

Алгоритм стартует с индекса [0]. Затем он создает версию массива, исключая первый индекс, и использует бинарный поиск, чтобы проверить, можно ли добавить к массиву какое-либо из оставшихся значений для получения желаемой суммы. Это действие выполняется один раз для каждого элемента в массиве.

Сам по себе цикл for будет иметь линейную временную сложность O (N), но внутри цикла for мы выполняем двоичный поиск, что дает общую временную сложность O (Nlog (N)). Это решение лучше предыдущего, но еще есть, что улучшать.


Решение 3. Линейное время

Временная сложность: O(N).
Пространственная сложность: O(1).


Сейчас мы будем решать задачу, помня, что массив отсортирован. Решение состоит в том, чтобы взять два числа: одно в начале и одно в конце. Если результат отличается от требуемого, то меняем начальную и конечную точку.

В конце концов мы либо встретим желаемое значение и вернем true, либо начальная и конечная точки сойдутся и вернется false.

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};


Теперь все хорошо, решение вроде бы оптимальное. Но кто даст гарантию, что массив был упорядоченным?

Что тогда?


На первый взгляд, мы могли сначала просто упорядочить массив, а затем использовать решение выше. Но как это повлияет на время выполнения?

Лучший алгоритм — быстрая сортировка c временной сложностью O (Nlog (N)). Если воспользуемся им в нашем оптимальном решении, оно изменит свою производительность с O (N) на O (Nlog (N)). Можно ли найти линейное решение с неупорядоченным массивом?

Решение 4

Временная сложность: O(N).
Пространственная сложность: O(N).


Да, линейное решение существует, для этого нужно создать новый массив, содержащий список совпадений, которые мы ищем. Компромисс здесь в более активном использовании памяти: это единственное решение в статье с пространственной сложностью, превышающей O (1).

Если первое значение данного массива равно 1, а искомое значение равно 8, мы можем добавить значение 7 в массив «значений поиска».

Затем, обрабатывая каждый элемент массива, можем проверить массив «значений поиска» и посмотреть, равно ли одно из них нашему значению. Если да, возвращаем true.

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

Основа решения — цикл for, который, как мы видели выше, имеет линейную временную сложность O (N).

Вторая итерационная часть нашей функции — Array.prototype.include (), метод JavaScript, который будет возвращать true или false в зависимости от того, содержит ли массив заданное значение.

Чтобы выяснить временную сложность Array.prototype.includes (), мы можем рассмотреть polyfill, предоставляемый MDN (и написанный на JavaScript), или воспользоваться методом в исходном коде движка JavaScript, такого как Google V8 (C ++).

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
 
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
 
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
 
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
 
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
 
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
 
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
 
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
 
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
 
      // 8. Return false
      return false;
    }
  });
}

Здесь итерационная часть Array.prototype.include () является циклом while на шаге 7, который (почти) пересекает всю длину данного массива. Это означает, что его временная сложность также линейна. Ну а поскольку она всегда находится на один шаг позади нашего основного массива, то временная сложность равна O (N + (N — 1)). Воспользовавшись Big O Notation, упрощаем ее до O (N) — потому что именно N имеет наибольшее влияние при увеличении входного размера.

Что касается пространственной сложности, необходим дополнительный массив, длина которого отражает исходный массив (минус один, да, но это можно игнорировать), что приводит к пространственной сложности O (N). Ну а увеличенное использование памяти обеспечивает максимальную эффективность алгоритма.


Надеюсь, статья окажется для вас полезной в качестве приложения к видеоинтервью. Она показывает, что простая задача может быть решена несколькими разными способами с различным количеством используемых ресурсов (время, память).

Skillbox рекомендует:

Skillbox
0.00
Онлайн-университет профессий будущего
Share post

Comments 44

    +13
    В 4 пункте ошибка, у вас вызов Array.prototype.include происходит внутри цикла, а значит там будет O(N*(N-1)) ~ O(N^2). Улучшение ничем не лучше первого варианта с полным перебором, но при этом добавили кучу доступов к памяти
      +1

      Можно закидывать числа в какой-то контейнер типа Set или Map (O(logN)) но это будет тот же O(NlogN), или HashMap (примерно O(1)).

      +13
      1.
      Постановка задачи
      Нам дают упорядоченный массив...
      2.
      Но кто даст гарантию, что массив был упорядоченным?

      Это очень правильно с житейской точки зрения перепроверить входные данные, но академические задачи на то и академические что исходные условия не подвергаются сомнению.
        0
        Я в таких случаях в роли собеседуемого просто обговариваю словами, что вначале мы отсортируем массив. Потому что это простая операция и лучше больше внимания и времени уделить основной части задачи.
          0
          Сортировка долгая, намного дольше, чем само вычисление. На крайний случай можно кинуть исключение или отсортировать, если не отсортирован (проверка за O(n)). Но в академических задачах это не требуется.
        +5
        Чтобы в четвертом варианте было O(N), searchValues переменная должна быть hash map.
          0
          решал похожую задачу на джаве, по ТЗ массив не был отсортирован.
          мой вариант был — берем хэшмапу, число в исходном массиве — это ключ в ней, значение 1 (тру, по вкусу).
          потом идем по исходному массиву и смотрим, есть ли единичка в мапе под ключем [искомое — текущее]. если да — то ура, нашли пару. если нет — идем дальше. если дошли до конца и пар не нашли — значит, их нет.
          итого — 2 линейных прохода по исходному массиву. доступ в хэшмапе константный.
            0
            Именно так :) Ниже пример решения, если попросят в усложнение вывести индексы этих элементов

            var twoSum = function(nums, target) {
                const hash = [];
                for (let i = 0; i < nums.length; i++) {
                    if (hash[nums[i]] !== undefined) {
                        hash[nums[i]].push(i);
                    } else {
                        hash[nums[i]] = [i];
                    }
                    const hashBucket = hash[target - nums[i]];
                    if (hashBucket !== undefined) {
                        if (i !== hashBucket[0]) {
                            return [i, hashBucket[0]]
                        } else if (hashBucket[1] !== undefined) {
                            return [i, hashBucket[1]];
                        }
                    }
                }
            };
            
              0
              Доступ в хэшмапе константный, но долгий (рандомное обращение к памяти). А в quicksort добавляется логарифм, но функция эффективно работает с памятью (все проходы идут по порядку массива). Что быстрее, не знаю.
              0
              С точки зрения «банальной эрудиции» можно «доработать» брутфорс.
              1. Разделить исходный массив на четные и нечетные.
              2. Если искомое число четное то оно может быть получено либо сложением Ч+Ч либо Н+Н, а нечетное м.б. получено сложением Ч+Н
              Понятное дело все зависит от того чем наполнен исходный массив но при нормальном распределении такое упрощение имеет смысл. Если почесать репу то можно, наверное, вывести еще несколько критериев упрощения.
              Все зависит от того что хотят видеть на интервью — набор готовых стандартных решений либо мыслительный процесс.
                0
                Лично я невысоко ценю подобные неасимптотические «креативные» отпимизации. В задаче не было речи ни о каком распределении, да и накладных расходов от такого разделения слишком много, проще уже нормальное решение написать.
                  0
                  Ну и в добавок в первом цикле можно проверять (если массив отсортирован)
                  if (arr[i] > val) break;

                  и не крутить лишний раз цикл если число в массиве больше чем искомое…
                    0
                    а кто сказал, что числа положительные — вдруг искомое: 8 и внутри массива есть –9 и 17?
                      +2
                      Условие задачи, массив отсортирован.
                    0

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

                    +3
                    А зачем вообще при брутфорсе перебирать второй цикл каждый раз с нуля, ведь все элементы до i мы уже проверили. И последнее решение с дополнительной памятью бы работало если бы использовали хеш
                      –3

                      Плюс в задаче не уточняется, что это может быть один (или не может) и тот-же индекс и тогда [1, 2, 4, 9] для результата 8 вернет true потому как 4+4=8. Как обычно "академические задачи" страдают неточностью в условиях. Типа "Для простоты примем, что число пи равно трем."
                      Ну и решение зависит от размеров массива, текущей располагаемой (предполагаемой) средой исполнения и т.д. Где-то тупой перебор, где-то на подмассивы бить, где-то бинарщина во все поля...

                        0
                        в 3 вариант можно добавить:
                        — сложить первые 2 числа и если сумма больше искомого — false
                        — пока последнее число больше искомого — end--
                        Ну а дальше алгоритм как есть
                          +5

                          А в третьем варианте разве мы не получим O(N^2) и дополнительный расход памяти, так как на каждой итерации мы будем копировать исходный массив? Не лучше ли было адаптировать бинарный поиск, чтобы он пропускал элемент, для которого мы производим поиск?

                            +2
                            Выгонят ли с интервью, если предложить многопоточно запустить все алгоритмы (с подобранными приоритетами), естественно до Task.WhenAny()?
                              +1

                              Это не решение задачи, так как вы выиграли лишь в константу (не превышающую количество ядер) раз.

                              +1
                              Не понимаю прикладного характера задачи, но при малых массивах (до миллиона) может оказаться, что простой перебор работает быстрее, чем время подготовки специальных структур, типа деревьев или сортировка. Логарифм на определенном диапазоне больше, чем квадрат х. Лучше сесть с таймером и сделать таблицу времени на каждый алгоритм с разными объемами данных.
                                0

                                Только это граница — не миллион, а от силы 1000. Попробуйте сдать лобовое решение, например, сюда: https://informatics.mccme.ru/mod/statements/view.php?id=597

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

                                    Если реальная задача свелась к академической (типа поиск минимума на отрезках массива, поиск двух элементов с заданной суммой, поиск наибольшего непересекающегося подмножества ребер графа и так далее), то теория там работает хорошо)) Я ни разу еще не слышал, чтобы на 1е6 заходил квадрат. Асимпотика позволяет предсказывать, сработает ли код на входных данных того или иного размера, с довольно хорошей точностью.
                                    И тот факт, что через неделю ТЗ может как-то поменяться, кмк не мешает здесь и сейчас написать эффективный код. Ну или не написать, но аргументированно))

                                  0

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

                                  0
                                  Берем первое число массива. Находим 2 соседних числа массива такие, что a[1]+a[j]<x a[1]+a[j+1]>x. Возможно, будет одно такое число. Следующее число массива. Используем полученные числа как начальный район поиска. И так далее.
                                  Скорость О(N), память О(1).
                                    0
                                    Перебирать до тех пор, пока 2*a[i]<x.
                                    0
                                    Трудности перевода — «space complexity» и «time complexity» переводятся как «сложность по памяти» и «сложность по времени». Пожалуйста, при переводе статей учитывайте терминологию русского языка, становится гораздо приятнее читать.
                                      0
                                      А какая тут сложность получается?
                                      var arr = [-22,-9,-4,2,5,7,8,9,11,12,16,17,21,22,25,26,29];
                                      
                                      for(let i=30; i > 0; i--) {
                                        console.log(`${i} = ${search(arr, i)}`);  
                                      }
                                      
                                      function search(arr, num) {
                                      
                                        var filterRange = arr[0] < 0 ? num - arr[0] : num;
                                        var new_arr = arr.filter(i=>{ return i <= filterRange })
                                      
                                        for(var i = new_arr.length; i >= 0; i--) {
                                          var para = Number(num) - Number(new_arr[i]);
                                          if (new_arr.includes(para)) {
                                            return [ new_arr[i], para ];
                                            break;
                                          }
                                        }
                                        return false;
                                      }
                                      
                                      
                                        0

                                        Квадратичное решение — ваши отсечения (т.е. фильтрация) не дают принципиального уменьшения размера массива. Поэтому, вы делаете примерно N поисков по N-элементному массиву каждый.

                                          0

                                          У функции search — O(N^2) в худшем случае.

                                          0
                                          Интересно, а насколько затратна в Javascript вся эта операция удаления элемента из массива и передачи нового массива в функцию во 2 решении?
                                          • UFO just landed and posted this here
                                            0
                                            function findPairOfAddendsBySum (array, requiredSum)
                                            {
                                              let lower = 0
                                              let upper = array.length - 1
                                            
                                              while (lower < upper)
                                              {
                                                const currentSum = array[lower] + array[upper]
                                                const middle = Math.floor(lower + (upper - lower) / 2)
                                            
                                                if (currentSum < requiredSum)
                                                {
                                                  if (array[middle] + array[upper] < requiredSum)
                                                    lower = middle;
                                                  ++lower
                                                }
                                                else if (currentSum > requiredSum)
                                                {
                                                  if (array[lower] + array[middle] > requiredSum)
                                                    upper = middle;
                                                  --upper
                                                }
                                                else
                                                {
                                                  return [array[lower], array[upper]]
                                                }
                                              }
                                            
                                              return []
                                            }

                                            В лучшем случае алгоритм аналогичен двоичному поиску O(log n), в худшем — O(n)
                                              +1
                                              skillbox пожалуйста обновите статью. Решение задачи 4 содержит ошибку: если у вас решением задачи будут 2 последних элемента массива, то мы также как и в 1м случае получим O(N^2)
                                                +1
                                                Ошибка в оригинальной статье (это перевод), поэтому лучше было бы указать на ошибку там. Что я и сделал: medium.com/@boriscoder/329409e9fc5
                                                  0
                                                  Автор оригинала обновил статью, теперь там используется Set.
                                                0
                                                Хм, вроде решил. Сложность O(n) в худшем случае, память O(1).
                                                function solve(target, arr) {
                                                    let i = 0;
                                                    let j = arr.length - 1;
                                                
                                                    while (i < j) {
                                                        const sum = a[i] + a[j];
                                                
                                                        if (sum < target) {
                                                            ++i;
                                                        } else if (target < sum) {
                                                            --j;
                                                        } else {
                                                            return true;
                                                        }
                                                    }
                                                
                                                    return false;
                                                }
                                                
                                                
                                                const target = 8;
                                                
                                                let a = [];
                                                // a = [1, 2, 3];
                                                a = [1, 2, 2, 4, 4];
                                                
                                                console.log(
                                                    solve(target, a)
                                                );
                                                


                                                Попробовать можно тут.
                                                  0
                                                  На самом деле, есть решение для неупорядоченного массива через черпачную сортировку, о которой, крайне незаслуженно, многие забывают, которое работает за O(n) и требует O(n) памяти и читает память практически линейно на больших массивах, пишет не совсем линейно, но в крайне ограниченное число адресов (в примере ниже — 256), т.е. почти все записи попадают в кэш.
                                                  Единственное ограничение, которое он накладывает — значения массива должны быть ограничены сверху некоторой константой. При этом алгоритм по сложности очень толерантен к данной константе.
                                                  Вот пример для массива с long значениями
                                                  // assumption: 0 <= array values < 2^63 (8 bytes signed)
                                                  // complexity: O(n)
                                                  // memory: O(n)
                                                      
                                                  function solve(arr, target) {
                                                  
                                                      // magic is here
                                                      bucketSort(arr);
                                                  
                                                      // classic O(n) solution for sorted array
                                                      var i = 0;
                                                      var j = arr.length - 1;
                                                      var sum;
                                                      while (i < j) {
                                                          const sum = arr[i] + arr[j];
                                                          if (sum < target) {
                                                              i++;
                                                          } else if (target < sum) {
                                                              j--;
                                                          } else {
                                                              return true;
                                                          }
                                                      }
                                                      return false;
                                                      
                                                  }
                                                      
                                                  // bucket sort has complexity O(n) and memory consumption O(n) for array of values less than constant
                                                  function bucketSort(arr) {
                                                    var buckets, i, j, byteShift, bucketId, pos;
                                                    
                                                    // create empty buckets
                                                    buckets = []; // will consume no more than O(n) memory
                                                    for (i = 0; i < 256; i++) {
                                                      buckets[i] = [];
                                                    }
                                                    
                                                    // sort
                                                    for (byteShift = 0; byteShift < 8; byteShift++) {
                                                      
                                                      // init buckets
                                                      for (i = 0; i < 256; i++) {
                                                        buckets[i].length = 0; // lets reuse memory
                                                      }
                                                      
                                                      // split array to buckets
                                                      for (i = 0; i < arr.length; i++) {
                                                        bucketId = (arr[i] >>> (byteShift * 8)) & 255;
                                                        buckets[bucketId].push(arr[i]);
                                                      }
                                                      
                                                      // merge buckets to array
                                                      pos = 0;
                                                      for (i = 0; i < 256; i++) {
                                                        for (j = 0; j < buckets[i].length; j++) {
                                                          arr[pos] = buckets[i][j];
                                                          pos++;
                                                        }
                                                      }
                                                      
                                                    }
                                                    
                                                  }

                                                    0

                                                    Судя по коду, у вас поразрядная (Radix) сортировка.
                                                    Так же как и сортировка подсчетом — это основные сортировки сложности O(n), не основанные на сравнениях элементов.

                                                    0
                                                    В реальности эти алгоритмы должны работать не с числами и индексами. Стоимость каждой операции нужно выяснять. Без этого, не надо морочить голову переусложнённым кодом. Брутфорс, немного оптимизированный, самый годный вариант.
                                                      0
                                                      А почему так нельзя? Тесты вроде проходит
                                                      const findSum = (arr, summ) => {
                                                        for (let i = 0; i < arr.length; i++) {
                                                          let c = arr.indexOf(summ - arr[i]);
                                                          if (c > -1 && c != i) return true;
                                                        }
                                                        return false;
                                                      }
                                                        0
                                                        Потому что Array.indexOf работает за O(n), в итоге весь ваш алгоритм работает за O(n^2), вы просто переложили половину работы по перебору влоб на плечи реализации метода indexOf.

                                                      Only users with full accounts can post comments. Log in, please.