Когда я занимался изучением производительности алгоритмов, мне попалось вот это видео с мок-интервью 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 рекомендует:
- Прикладной онлайн-курс «Аналитик данных Python».
- Онлайн-курс «Профессия frontend-разработчик».
- Практический годовой курс «PHP-разработчик с 0 до PRO».
Комментарии (40)
red_perez
15.03.2019 17:59+51.
Постановка задачи
2.
Нам дают упорядоченный массив...
Но кто даст гарантию, что массив был упорядоченным?
Это очень правильно с житейской точки зрения перепроверить входные данные, но академические задачи на то и академические что исходные условия не подвергаются сомнению.grondek
16.03.2019 15:45Я в таких случаях в роли собеседуемого просто обговариваю словами, что вначале мы отсортируем массив. Потому что это простая операция и лучше больше внимания и времени уделить основной части задачи.
vitaliy2
17.03.2019 17:39Сортировка долгая, намного дольше, чем само вычисление. На крайний случай можно кинуть исключение или отсортировать, если не отсортирован (проверка за O(n)). Но в академических задачах это не требуется.
vezga
15.03.2019 18:03+4Чтобы в четвертом варианте было O(N), searchValues переменная должна быть hash map.
H_I_R_U_R_G
15.03.2019 18:28решал похожую задачу на джаве, по ТЗ массив не был отсортирован.
мой вариант был — берем хэшмапу, число в исходном массиве — это ключ в ней, значение 1 (тру, по вкусу).
потом идем по исходному массиву и смотрим, есть ли единичка в мапе под ключем [искомое — текущее]. если да — то ура, нашли пару. если нет — идем дальше. если дошли до конца и пар не нашли — значит, их нет.
итого — 2 линейных прохода по исходному массиву. доступ в хэшмапе константный.samsdemon
16.03.2019 12:45Именно так :) Ниже пример решения, если попросят в усложнение вывести индексы этих элементов
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]]; } } } };
vitaliy2
17.03.2019 17:43Доступ в хэшмапе константный, но долгий (рандомное обращение к памяти). А в quicksort добавляется логарифм, но функция эффективно работает с памятью (все проходы идут по порядку массива). Что быстрее, не знаю.
red_perez
15.03.2019 19:20С точки зрения «банальной эрудиции» можно «доработать» брутфорс.
1. Разделить исходный массив на четные и нечетные.
2. Если искомое число четное то оно может быть получено либо сложением Ч+Ч либо Н+Н, а нечетное м.б. получено сложением Ч+Н
Понятное дело все зависит от того чем наполнен исходный массив но при нормальном распределении такое упрощение имеет смысл. Если почесать репу то можно, наверное, вывести еще несколько критериев упрощения.
Все зависит от того что хотят видеть на интервью — набор готовых стандартных решений либо мыслительный процесс.daiver19
16.03.2019 00:10Лично я невысоко ценю подобные неасимптотические «креативные» отпимизации. В задаче не было речи ни о каком распределении, да и накладных расходов от такого разделения слишком много, проще уже нормальное решение написать.
funnybanana
16.03.2019 01:31Ну и в добавок в первом цикле можно проверять (если массив отсортирован)
if (arr[i] > val) break;
и не крутить лишний раз цикл если число в массиве больше чем искомое…Utopia
16.03.2019 12:40а кто сказал, что числа положительные — вдруг искомое: 8 и внутри массива есть –9 и 17?
MikailBag
16.03.2019 19:51Не стоит противопоставлять готовые знания и умение думать. Да, бинпоиск/метод двух указателей это стандартная идея. Но чтобы воткнуть их, иногда нужно сильно подумать)
skoder
15.03.2019 20:04+1А зачем вообще при брутфорсе перебирать второй цикл каждый раз с нуля, ведь все элементы до i мы уже проверили. И последнее решение с дополнительной памятью бы работало если бы использовали хеш
Skykharkov
15.03.2019 22:05-1Плюс в задаче не уточняется, что это может быть один (или не может) и тот-же индекс и тогда [1, 2, 4, 9] для результата 8 вернет true потому как 4+4=8. Как обычно "академические задачи" страдают неточностью в условиях. Типа "Для простоты примем, что число пи равно трем."
Ну и решение зависит от размеров массива, текущей располагаемой (предполагаемой) средой исполнения и т.д. Где-то тупой перебор, где-то на подмассивы бить, где-то бинарщина во все поля...
AHDPEu
16.03.2019 09:32в 3 вариант можно добавить:
— сложить первые 2 числа и если сумма больше искомого — false
— пока последнее число больше искомого — end--
Ну а дальше алгоритм как есть
gkozlenko
16.03.2019 11:20+3А в третьем варианте разве мы не получим O(N^2) и дополнительный расход памяти, так как на каждой итерации мы будем копировать исходный массив? Не лучше ли было адаптировать бинарный поиск, чтобы он пропускал элемент, для которого мы производим поиск?
WeberWebber
16.03.2019 12:48+2Выгонят ли с интервью, если предложить многопоточно запустить все алгоритмы (с подобранными приоритетами), естественно до Task.WhenAny()?
MikailBag
16.03.2019 17:14Это не решение задачи, так как вы выиграли лишь в константу (не превышающую количество ядер) раз.
dim2r
16.03.2019 12:49+1Не понимаю прикладного характера задачи, но при малых массивах (до миллиона) может оказаться, что простой перебор работает быстрее, чем время подготовки специальных структур, типа деревьев или сортировка. Логарифм на определенном диапазоне больше, чем квадрат х. Лучше сесть с таймером и сделать таблицу времени на каждый алгоритм с разными объемами данных.
MikailBag
16.03.2019 17:18Только это граница — не миллион, а от силы 1000. Попробуйте сдать лобовое решение, например, сюда: https://informatics.mccme.ru/mod/statements/view.php?id=597
dim2r
17.03.2019 08:16При решении реальных задач теория работает частично. Объективный показатель — время исполнения. Может оказаться, что массив постоянно меняется и тогда нужен будет другой подход.
MikailBag
17.03.2019 09:31Если реальная задача свелась к академической (типа поиск минимума на отрезках массива, поиск двух элементов с заданной суммой, поиск наибольшего непересекающегося подмножества ребер графа и так далее), то теория там работает хорошо)) Я ни разу еще не слышал, чтобы на 1е6 заходил квадрат. Асимпотика позволяет предсказывать, сработает ли код на входных данных того или иного размера, с довольно хорошей точностью.
И тот факт, что через неделю ТЗ может как-то поменяться, кмк не мешает здесь и сейчас написать эффективный код. Ну или не написать, но аргументированно))
Tarik02
16.03.2019 17:19В таком случае можно использовать сразу две реализации: простая для малых массивов, и сложная для больших.
mafia8
16.03.2019 13:01Берем первое число массива. Находим 2 соседних числа массива такие, что a[1]+a[j]<x a[1]+a[j+1]>x. Возможно, будет одно такое число. Следующее число массива. Используем полученные числа как начальный район поиска. И так далее.
Скорость О(N), память О(1).
acerikfy
16.03.2019 13:18Трудности перевода — «space complexity» и «time complexity» переводятся как «сложность по памяти» и «сложность по времени». Пожалуйста, при переводе статей учитывайте терминологию русского языка, становится гораздо приятнее читать.
4tlen
16.03.2019 13:47А какая тут сложность получается?
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; }MikailBag
16.03.2019 17:20Квадратичное решение — ваши отсечения (т.е. фильтрация) не дают принципиального уменьшения размера массива. Поэтому, вы делаете примерно N поисков по N-элементному массиву каждый.
OpieOP
16.03.2019 13:49Интересно, а насколько затратна в Javascript вся эта операция удаления элемента из массива и передачи нового массива в функцию во 2 решении?
kmansoft
16.03.2019 14:12Удаление — затратно, конечно. И ещё «касается» памяти всех элементов, то есть может вытеснить из кеша процессора то что нам нужно, если массивы большие (а если маленькие, то какая разница какое там O).
И это просто не учитывается, как и сложность проверки array.includes() в 4-м решении.
В общем анализ (и решения, и выводы) — так себе, и это если быть очень вежливым.
ecmaeology
16.03.2019 13:57function 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)
Naftic
16.03.2019 14:02skillbox пожалуйста обновите статью. Решение задачи 4 содержит ошибку: если у вас решением задачи будут 2 последних элемента массива, то мы также как и в 1м случае получим O(N^2)
justboris
16.03.2019 15:23Ошибка в оригинальной статье (это перевод), поэтому лучше было бы указать на ошибку там. Что я и сделал: medium.com/@boriscoder/329409e9fc5
glagola
16.03.2019 15:35Хм, вроде решил. Сложность 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) );
Попробовать можно тут.
HappyLynx
17.03.2019 19:24На самом деле, есть решение для неупорядоченного массива через черпачную сортировку, о которой, крайне незаслуженно, многие забывают, которое работает за 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++; } } } }Deosis
18.03.2019 10:06Судя по коду, у вас поразрядная (Radix) сортировка.
Так же как и сортировка подсчетом — это основные сортировки сложности O(n), не основанные на сравнениях элементов.
mosinnik
В 4 пункте ошибка, у вас вызов Array.prototype.include происходит внутри цикла, а значит там будет O(N*(N-1)) ~ O(N^2). Улучшение ничем не лучше первого варианта с полным перебором, но при этом добавили кучу доступов к памяти
Tarik02
Можно закидывать числа в какой-то контейнер типа
SetилиMap(O(logN)) но это будет тот же O(NlogN), илиHashMap(примерно O(1)).