Хабрахабр

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

Оно не только дает представление, как проходят собеседования в крупных технологических корпорациях, но и позволяет понять, как решаются алгоритмические задачи, причем максимально эффективно. Когда я занимался изучением производительности алгоритмов, мне попалось вот это видео с мок-интервью 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) => ; }; }; return false;
};

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

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

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

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

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

Чтобы все было понятно, мы используем отдельную функцию для контроля бинарного поиска. Вот как может выглядеть решение. А также функцию 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;
};

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

Что тогда?

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

Если воспользуемся им в нашем оптимальном решении, оно изменит свою производительность с O (N) на O (Nlog (N)). Лучший алгоритм — быстрая сортировка c временной сложностью 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 рекомендует:

Теги
Показать больше

Похожие статьи

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть