Вопрос о вложенных массивах может поначалу показаться сложным. Но если как следует разобраться, всё станет легко и понятно. К тому же, знание особенностей вложенных массивов даёт возможность здорово оптимизировать код. После этой статьи вы сможете порадовать своих интервьюеров некоторыми идеями по этой теме, о которых они, может, и не догадывались!
В чём заключается задача о вложенных массивах?
Давайте разбираться.
На входе мы имеем целочисленный массив arr длинной n. Целые числа в массиве представляют собой перемешанные индексы. Составление исходного массива для задачи выглядит следующим образом:
function scrambleArray(arr) {
const tmpArray = Array.from(arr);
const scrambledArray = new Array(arr.length).fill(1);
let index = 0;
while (tmpArray.length) {
const randomIndex = Math.floor(Math.random() * (tmpArray.length - 1));
scrambledArray[index++] = tmpArray.splice(randomIndex, 1)[0];
}
return scrambledArray;
}
Для каждого элемента перемешанного массива необходимо посчитать последовательность по следующей логике:
s[k] = [arr[k], arr[arr[k]], arr[arr[arr[k]], ...]Последовательность для каждого числа записывается ровно до тех пор, пока очередное число не совпадёт с уже обработанным элементом (повторяющееся число мы не включаем в массив). В конце нужно вернуть самую длинную последовательность в s.
Пример вложенного массива
Возьмём следующий массив: [6, 5, 7, 8, 0, 4, 3, 2, 1, 9].
Из этого массива создаются следующие последовательности:
[3, 8, 1, 5, 4, 0, 6], [4, 0, 6, 3, 8, 1, 5], [2, 7], [1, 5, 4, 0, 6, 3, 8], [6, 3, 8, 1, 5, 4, 0], [0, 6, 3, 8, 1, 5, 4], [8, 1, 5, 4, 0, 6, 3], [7, 2], [5, 4, 0, 6, 3, 8, 1], [9]
Здесь можно легко увидеть, что наибольшая длина последовательности – 7 цифр.
Если вы никогда ранее не брались за подобные задачи, то советую вам попробовать прямо сейчас, потому что дальше будут спойлеры! Найти аналогичную задачу можно на leetcode.
Но если вас больше интересует самая «сочная» часть, продолжайте читать!
Как решить задачу со вложенными массивами на собеседовании?
Решая такую задачу, вы, вероятно, будете действовать по следующей схеме:
- Создадите брутфорс-решение
- Оптимизируете его
Давайте и пойдём по этому пути.
Брутфорс-решение
Алгоритм довольно прост:
function getNestedArraysMaxLength(inputArray) {
let maxLength = -Infinity;
inputArray.forEach(value => {
const seriesLength = findSeriesLength(inputArray, value);
maxLength = Math.max(seriesLength, maxLength);
});
return maxLength;
}
Мы делаем в точности то, о чём нас просят. Для каждого элемента inputArray мы узнаём seriesLength и сохраняем наибольшую найденную длину. В результате мы возвращаем максимальную длину, что от нас и требовалось.
Теперь нам нужно реализовать функцию findSeriesLength:
function findSeriesLength(arr, nextValue) {
const series = {[nextValue]: true};
while (true) {
nextValue = arr[nextValue];
if (series[nextValue]) {
return Object.keys(series).length;
}
series[nextValue] = true;
}
}
Это более сложная часть алгоритма. Функция принимает на вход массив и следующее значение (первое значение в последовательности). Последовательность в любом случае имеет первый элемент, поэтому мы установим его для каждого вложенного массива. Затем мы заполняем последовательность, пока снова не дойдем до того же числа. Как только мы это сделаем, сможем вернуть длину вложенного массива.
Сложность нашего непродуманного, но рабочего брутфорс-решения составляет O(n2). В наихудшем случае мы бы прошлись по всем числам в исходном массиве, а потом, в ходе составления последовательностей, для каждого числа проходили бы по всем числам снова. Но обычно на собеседовании можно предложить решение получше.
Оптимизация по времени
Глядя на пример выше, мы можем выделить следующую закономерность:
Рисунок 1 иллюстрирует циклическую природу наших последовательностей. В данном случае последовательности – это просто периодически повторяющиеся наборы чисел. Это можно использовать для оптимизации алгоритма. Добавим массив memory, чтобы сохранить количество значений, которые мы уже обработали.
function getNestedArraysMaxLength(inputArray) {
let maxLength = -Infinity;
const memory = [];
inputArray.forEach(value => {
memory[value] = findSeriesLength(inputArray, value, memory);
maxLength = Math.max(maxLength, memory[value]);
});
return maxLength;
}
function findSeriesLength(arr, nextValue, memory) {
const series = {[nextValue]: true};
while (true) {
nextValue = arr[nextValue];
if (memory[nextValue]) {
return memory[nextValue];
}
if (series[nextValue]) {
return Object.keys(series).length;
}
series[nextValue] = true;
}
}
Перечислим все изменения:
- В 3 строке объявляется массив memory.
- В 6 строке счетчик заносится в массив memory, а не в переменную. Теперь мы используем это значение в строке 7 вместо переменной
seriesLength. - Функция
findSeriesLengthтеперь использует массив memory, который она получает в качестве входных данных, чтобы проверить, есть ли у нас уже счетчик для определенного значения (строки 18–20).
Давайте посмотрим на сложность (“O” большое) этого решения. Мы по-прежнему просматриваем n значений в inputArray. Но каждую последовательность, показанную на рисунке 1, мы будем проходить только один раз.
Наша сложность теперь O(n) (линейная), потому что единственное место, где мы перебираем n элементов, – это основной цикл forEach. Наша пространственная сложность теперь O(n), потому что мы используем вспомогательный массив memory.
Сравнение
Изучим разницу между оптимизированным и исходным алгоритмами. Используем для этих целей сайт jsben.ch. Начнём наши замеры с n = 10 (да, этого немного, но пусть будет так).
Рисунок 2 демонстрирует успешную оптимизацию (результат сравнительного анализа здесь). Но… мы же ожидали куда большего, правда? Ведь мы заметно уменьшили сложность алгоритма!
Возможна ли дополнительная оптимизация?
Есть несколько способов оптимизировать наш алгоритм.
Будет полезно пояснить для начинающих, что происходит, когда мы используем счётчик вместо series в функции findSeriesLength. Изменим функцию следующим образом:
function findSeriesLength(arr, nextValue) {
const startingNumber = nextValue;
let count = 1;
while (true) {
nextValue = arr[nextValue];
if (startingNumber === nextValue) {
return count;
}
count++;
}
}
В этом коде, вместо создания последовательностей, что от нас и не требуется по заданию (нам нужно лишь вернуть длину), мы сохраняем первое число в переменной startingNumber и создаём счётчик.
Сравнительный анализ для этой функции представлен на рисунке 3 (и здесь).
Что бы та же оптимизация сделала со сложностью алгоритма? Результаты на рисунке 4 вас удивят.
Что же здесь происходит? Может ли топорный алгоритм O(n2) выполняться быстрее, чем O(n)?
Сбор мусора (Garbage Collection) – основной фактор, определяющий производительность кода на JavaScript.
Если функция создаёт и уничтожает множество объектов/массивов, это дорого нам обойдётся: JS будет производить выделение памяти для них и сбор мусора. А это требует времени. При масштабировании вашего кода это будет занимать даже еще больше времени.
Вдобавок, как вы можете видеть, алгоритм O(n) не даёт нам ожидаемого преимущества, хотя теоретически он должен быть быстрее O(n2). Всё это из-за очень маленького n. Если увеличить его до 1000, картина будет совершенно иной. На рисунке 5 показаны результаты для n=1000.
Так что тут мы узнаём 2 вещи:
- Уменьшение сложности алгоритма полезно только при больших n.
- Сбор мусора может стать основной слабостью вашего кода на JavaScript.
Оптимизация временной и пространственной сложности
Мы также можем улучшить временную сложность, не увеличивая пространственную и полностью избегая проблемы со сборкой мусора.
Вместо создания нового массива memory мы можем просто установить маркер в нашем массиве:
function getNestedArraysMaxLength(inputArray) {
let maxLength = -Infinity;
inputArray.forEach((value, index) => {
const seriesLength = findSeriesLength(inputArray, index);
maxLength = Math.max(maxLength, seriesLength);
});
return maxLength;
}
function findSeriesLength(arr, nextIndex) {
let count = 0;
while (true) {
let nextValue = arr[nextIndex];
if (nextValue === null) {
return count;
}
arr[nextIndex] = null;
nextIndex = nextValue;
count++;
}
}
Заметьте, что мы убрали все упоминания memory. Хитрость в том, что мы присваиваем null (или какое-нибудь другое известное значение) всем обработанным переменным. И теперь каждый раз, когда мы встречаем null, мы знаем, что уже проверяли данный цикл, и нет смысла идти дальше.
Результаты на рисунке 6 выглядят довольно убедительно. Использование алгоритма со сложностью O(n) и затем оптимизация расхода памяти до O(1) также увеличивают производительность. И мы уже знаем причину этому: выделение памяти и сбор мусора.
Отказываясь от массива memory, мы уменьшаем количество выделяемой памяти и, как следствие, количество циклов сборки мусора.
Чтобы подтвердить нашу гипотезу, мы можем легко избежать сборки мусора в решении с расходом памяти O(n). Меняем строчку:
const memory = [];
на
const memory = new Array(inputArray.length).fill(1);
Таким образом мы зарезервируем память перед выполнением функции, и, как следствие, сократим количество циклов сборки мусора и выделения памяти. Результат – на рисунке 7.
Можно ли сделать что-нибудь ещё?
Конечно! Но это уже будет микро-оптимизациями, которые будут зависеть от вашего браузера или движка JS. Например, если мы заменим цикл forEach на for, то получим следующий результат:
Заключение
Вложенные массивы – относительно простая задача на собеседовании. У нее довольно простое брутфорс-решение, которое легко оптимизировать. Вы можете либо сохранять результаты предыдущих вычислений, либо использовать некий флаг на самих данных.
Мы также обнаружили, что наши манипуляции с данными сильно влияют на скорость конечного решения. Выделение памяти и сбор мусора могут сильно навредить производительности. И, наконец, мы выяснили, что некоторые оптимизации (вроде трюка с forEach) дадут совсем небольшой выигрыш в производительности.
В нашей задаче – обнаружении наибольших последовательностей – мы производили различные оптимизации: либо сохраняли счётчик, либо использовали заранее зарезервированный массив memory.
Я надеюсь, что теперь, если вам зададут данный вопрос на собеседовании, вы сможете удивить своего интервьюера глубоким пониманием проблемы и подробными объяснениями про выделение памяти, сбор мусора и О-нотацию.
Перевод статьи “Deep dive into an interview question: Array Nesting”.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]
