15.03.2019 14:29
fokus-lop 40 17600 Источник


Когда я занимался изучением производительности алгоритмов, мне попалось вот это видео с мок-интервью 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 рекомендует:

Комментарии (40)


  1. mosinnik
    15.03.2019 17:38
    #19890794
    +5

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


    1. Tarik02
      16.03.2019 11:37
      #19893548

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


  1. red_perez
    15.03.2019 17:59
    #19890902
    +5

    1.

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

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


    1. grondek
      16.03.2019 15:45
      #19894678

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


      1. vitaliy2
        17.03.2019 17:39
        #19899146

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


  1. vezga
    15.03.2019 18:03
    #19890922
    +4

    Чтобы в четвертом варианте было O(N), searchValues переменная должна быть hash map.


  1. H_I_R_U_R_G
    15.03.2019 18:28
    #19891034

    решал похожую задачу на джаве, по ТЗ массив не был отсортирован.
    мой вариант был — берем хэшмапу, число в исходном массиве — это ключ в ней, значение 1 (тру, по вкусу).
    потом идем по исходному массиву и смотрим, есть ли единичка в мапе под ключем [искомое — текущее]. если да — то ура, нашли пару. если нет — идем дальше. если дошли до конца и пар не нашли — значит, их нет.
    итого — 2 линейных прохода по исходному массиву. доступ в хэшмапе константный.


    1. samsdemon
      16.03.2019 12:45
      #19893868

      Именно так :) Ниже пример решения, если попросят в усложнение вывести индексы этих элементов

      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]];
            }
        }
    }
};


    1. vitaliy2
      17.03.2019 17:43
      #19899170

      Доступ в хэшмапе константный, но долгий (рандомное обращение к памяти). А в quicksort добавляется логарифм, но функция эффективно работает с памятью (все проходы идут по порядку массива). Что быстрее, не знаю.


  1. red_perez
    15.03.2019 19:20
    #19891274

    С точки зрения «банальной эрудиции» можно «доработать» брутфорс.
    1. Разделить исходный массив на четные и нечетные.
    2. Если искомое число четное то оно может быть получено либо сложением Ч+Ч либо Н+Н, а нечетное м.б. получено сложением Ч+Н
    Понятное дело все зависит от того чем наполнен исходный массив но при нормальном распределении такое упрощение имеет смысл. Если почесать репу то можно, наверное, вывести еще несколько критериев упрощения.
    Все зависит от того что хотят видеть на интервью — набор готовых стандартных решений либо мыслительный процесс.


    1. daiver19
      16.03.2019 00:10
      #19892538

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


    1. funnybanana
      16.03.2019 01:31
      #19892732

      Ну и в добавок в первом цикле можно проверять (если массив отсортирован)

      if (arr[i] > val) break;

      и не крутить лишний раз цикл если число в массиве больше чем искомое…


      1. Utopia
        16.03.2019 12:40
        #19893850

        а кто сказал, что числа положительные — вдруг искомое: 8 и внутри массива есть –9 и 17?


        1. MaximSuvorov
          16.03.2019 18:05
          #19895342

          Условие задачи, массив отсортирован.


    1. MikailBag
      16.03.2019 19:51
      #19895766

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


  1. skoder
    15.03.2019 20:04
    #19891510
    +1

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


  1. Skykharkov
    15.03.2019 22:05
    #19892070
    -1

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


  1. AHDPEu
    16.03.2019 09:32
    #19893222

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


  1. gkozlenko
    16.03.2019 11:20
    #19893504
    +3

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


  1. WeberWebber
    16.03.2019 12:48
    #19893874
    +2

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


    1. MikailBag
      16.03.2019 17:14
      #19895132

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


  1. dim2r
    16.03.2019 12:49
    #19893880
    +1

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


    1. MikailBag
      16.03.2019 17:18
      #19895150

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


      1. dim2r
        17.03.2019 08:16
        #19897278

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


        1. MikailBag
          17.03.2019 09:31
          #19897410

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


    1. Tarik02
      16.03.2019 17:19
      #19895156

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


  1. mafia8
    16.03.2019 13:01
    #19893948

    Берем первое число массива. Находим 2 соседних числа массива такие, что a[1]+a[j]<x a[1]+a[j+1]>x. Возможно, будет одно такое число. Следующее число массива. Используем полученные числа как начальный район поиска. И так далее.
    Скорость О(N), память О(1).


    1. mafia8
      16.03.2019 14:04
      #19894206

      Перебирать до тех пор, пока 2*a[i]<x.


  1. acerikfy
    16.03.2019 13:18
    #19894000

    Трудности перевода — «space complexity» и «time complexity» переводятся как «сложность по памяти» и «сложность по времени». Пожалуйста, при переводе статей учитывайте терминологию русского языка, становится гораздо приятнее читать.


  1. 4tlen
    16.03.2019 13:47
    #19894124

    А какая тут сложность получается?

    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;
}


    1. MikailBag
      16.03.2019 17:20
      #19895162

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


    1. Tarik02
      16.03.2019 17:21
      #19895164

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


  1. OpieOP
    16.03.2019 13:49
    #19894134

    Интересно, а насколько затратна в Javascript вся эта операция удаления элемента из массива и передачи нового массива в функцию во 2 решении?


    1. kmansoft
      16.03.2019 14:12
      #19894232

      Удаление — затратно, конечно. И ещё «касается» памяти всех элементов, то есть может вытеснить из кеша процессора то что нам нужно, если массивы большие (а если маленькие, то какая разница какое там O).

      И это просто не учитывается, как и сложность проверки array.includes() в 4-м решении.

      В общем анализ (и решения, и выводы) — так себе, и это если быть очень вежливым.


  1. ecmaeology
    16.03.2019 13:57
    #19894168

    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. Naftic
    16.03.2019 14:02
    #19894194

    skillbox пожалуйста обновите статью. Решение задачи 4 содержит ошибку: если у вас решением задачи будут 2 последних элемента массива, то мы также как и в 1м случае получим O(N^2)


    1. justboris
      16.03.2019 15:23
      #19894566

      Ошибка в оригинальной статье (это перевод), поэтому лучше было бы указать на ошибку там. Что я и сделал: medium.com/@boriscoder/329409e9fc5


  1. glagola
    16.03.2019 15:35
    #19894618

    Хм, вроде решил. Сложность 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)
);


    Попробовать можно тут.


  1. HappyLynx
    17.03.2019 19:24
    #19899478

    На самом деле, есть решение для неупорядоченного массива через черпачную сортировку, о которой, крайне незаслуженно, многие забывают, которое работает за 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++;
      }
    }
    
  }
  
}


    1. Deosis
      18.03.2019 10:06
      #19901590

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