Спорим, вы не сможете решить эту задачу с собеседования в Google
Разбираем решение задачи, которую блоггер TechLead давал на собеседовании на должность разработчика ПО в Google.
Разбиваем сложную задачу на простые шаги
Мне захотелось посмотреть видео о разработке программного обеспечения, и я начал запоем смотреть TechLead на YouTube. Следующие несколько дней я потратил на то, чтобы найти разные варианты решения задачи, который он давал кандидатам, когда проводил собеседование в Google.
Меня заинтересовало это видео
Как проходит собеседование в Google (на должность разработчика ПО), автор: TechLead
В своем видео TechLead упоминает задачу, которую он больше сотни раз задавал кандидатам, что проходили собеседование в Google. Мне захотелось придумать решение с помощью RxJS. В этой статье мы рассмотрим традиционные методы.
Настоящая цель этой задачи – узнать кандидата. Правильные ли вопросы он задает перед написанием кода? Впишется ли его решение в инфраструктуру проекта? Насколько он будет полезен команде, когда придет работать в Google? TechLead утверждает, что от кандидата не требуется правильный ответ: важнее выяснить, как он думает, и насколько хорошо понимает поставленную задачу.
Он привел два решения: одно рекурсивное (ограниченное размером стека), другое – итеративное (ограниченное объемом памяти). Мы рассмотрим и то, и другое!
Задача от TechLead
Вот условия задания: нужно взять эту сетку блоков, найти самый большой участок из смежных блоков одного цвета и вычислить, из скольких блоков он состоит.
Когда я услышал это условие и увидел картинку, я подумал: «Черт, придется делать моделирование 2D-изображения, это же почти невозможно выполнить на собеседовании».
Однако после того, как TechLead объяснил подробнее, я понял, что всё не так. Нужно не проанализировать изображение, а обработать уже имеющиеся данные. Теперь я понимаю, что моделировать 2D-изображение совсем не обязательно.
Моделирование данных
Прежде чем писать код, нужно определить модель данных – это крайне важный этап. С такими сложными задачами сначала выясните, с какими условиями придется работать.
В нашем случае TechLead задал такие условия:
- У нас есть цветные квадраты – для удобства назовем их блоками.
- В наборе данных есть 10 000 блоков.
- Блоки организованы в столбцы и строки (2D).
- Количество столбцов и строк может быть неравным.
- Блоки смежны между собой и окрашены в несколько цветов.
Также мы можем получить дополнительную информацию на основе данных, приведенных выше:
- Блоки не перекрывают друг друга.
- Блок не может быть смежным по отношению к самому себе.
- Параметры смежности не могут быть одинаковы у разных блоков.
- Блоки, которые находятся на сторонах и углах, будут иметь на один и два параметра смежности меньше, чем все остальные.
Чего мы не знаем:
- Соотношение количества строк к количеству столбцов.
- Количество возможных цветов.
- Каковы шансы, что во всей сетке присутствует всего один цвет.
- Как распределены цвета.
Чем профессиональнее разработчик, тем больше вопросов у него возникает. Однако здесь дело не в опыте. Да, он помогает, но даже опытного разработчика нельзя назвать профессионалом, если он не может определить, какие условия в задаче неизвестны. Умение задавать вопросы важно во всех компаниях, не только в Google.
Большинство людей, скорее всего, определит другие неизвестные. Пока я не начал думать над алгоритмом решения, я тоже не знал, что именно неизвестно: чтобы разобраться в этом, нужно время и много обсуждений с представителями бизнеса.
Глядя на это изображение, кажется, что распределение случайное. В условиях задачи в Google даны всего 3 цвета и не упоминается, что цветов может быть больше или меньше. Также предположим, что все блоки могут быть одного цвета.
Чтобы облегчить работу над алгоритмом, допустим, что мы работаем с сеткой 100×100. Так, нам не придется иметь дело с нетипичными случаями, в которых сетка состоит из 1 строки и 10 000 столбцов.
Обычно я ставлю перед собой все эти вопросы в течение первых нескольких часов после изучения данных. Задание с собеседования в Google показывает, как вы работаете над поставленными задачами: сначала пробуете писать код случайного решения или сперва пытаетесь разобраться в проблеме?
Да, в своей модели данных вы допустите несколько ошибок. Я так думаю, потому что сам попал в такую ситуацию, пока писал статью. Тем не менее, если у вас есть план действий, вы легче справитесь с этой проблемой. В итоге мне пришлось переписывать довольно небольшую часть кода.
Создание модели данных
Нам нужно точно знать, в каком формате нам поступают данные, и как мы будем их обрабатывать.
Поскольку у нас нет системы для обработки данных, нам нужно самим придумать визуализацию.
Основные параметры данных в нашем случае:
- цвет;
- ID;
- X;
- Y.
Зачем нужен ID? Чтобы не обрабатывать данные об одном и том же блоке по несколько раз. Если каждому блоку присвоить ID, с его помощью мы сможем отмечать уже обработанные блоки и предотвратим бесконечные циклы.
Кроме того, в подобных случаях данным, как правило, присваивается какой-либо ID, хэш или другой параметр. Это уникальный идентификатор, с помощью которого мы сможем отметить каждый конкретный блок. Чтобы найти самый большой участок одного цвета, нужно знать, из каких блоков он состоит.
Поскольку в нашем случает данные находятся в сетке, я предполагаю, что мы можем присвоить им значения по оси X и Y. Используя только эти параметры, я смог сгенерировать HTML, чтобы убедиться, что результат похож на задачу в Google.
Как и в задаче от TechLead, я использовал абсолютное позиционирование:
Это работает и с бо́льшим объемом данных:
Это код, которые генерирует сетку блоков:
const generateNodes = ({
numberOfColumns,
numberOfRows,
}) => (
Array(
numberOfColumns
* numberOfRows
)
.fill()
.map((
item,
index,
) => ({
colorId: (
Math
.floor(
Math.random() * 3
)
),
id: index,
x: index % numberOfColumns,
y: Math.floor(index / numberOfColumns),
}))
)
Берем столбцы и строки, создаем одномерный массив, в котором указываем количество элементов, а затем генерируем блоки на основе этих данных.
Вместо color я использую colorId. Во-первых, потому что так проще рандомизировать. Во-вторых, так нам не придется отдельно находить значение параметра color.
На собеседовании в Google задают задачу с тремя цветами, но никто не говорит, что это обязательное условие. Тем не менее, я тоже ограничусь тремя цветами. Просто уточним, что даже если в схеме будут сотни цветов, в итоге переписывать алгоритмы не придется.
Более простой пример: сетка блоков 2×2:
[
{ colorId: 2, id: 0, x: 0, y: 0 },
{ colorId: 1, id: 1, x: 1, y: 0 },
{ colorId: 0, id: 2, x: 0, y: 1 },
{ colorId: 1, id: 3, x: 1, y: 1 },
]
Обработка данных
Независимо от того, какой метод мы собираемся использовать, сначала нужно узнать параметры смежности для каждого блока. Сами по себе значения X и Y не решают эту задачу.
Таким образом, зная параметры блока X и Y, нужно найти блоки со смежными значениями X и Y. Это довольно просто: мы находим все блоки со значениями +1 и –1 по оси X и Y.
Для этого я написал вспомогательную функцию:
С точки зрения математики, генерация блоков и определение ID каждого блока – это один и тот же процесс. Но я исхожу из того, что в нашей сетке блоки расположены в случайном порядке.
Я сделал ещё один проход по всем блокам, чтобы найти параметры смежности:
const addAdjacencies = (
nodes,
) => (
nodes
.map(({
colorId,
id,
x,
y,
}) => ({
color: colors[colorId],
eastId: (
getNodeAtLocation({
nodes,
x: x + 1,
y,
})
),
id,
northId: (
getNodeAtLocation({
nodes,
x,
y: y - 1,
})
),
southId: (
getNodeAtLocation({
nodes,
x,
y: y + 1,
})
),
westId: (
getNodeAtLocation({
nodes,
x: x - 1,
y,
})
),
}))
.map(({
color,
id,
eastId,
northId,
southId,
westId,
}) => ({
adjacentIds: (
[
eastId,
northId,
southId,
westId,
]
.filter((
adjacentId,
) => (
adjacentId !== undefined
))
),
color,
id,
}))
)
В коде препроцессора я постарался избежать ненужных оптимизаций. Это не повлияет на финальную производительность и поможет упростить алгоритмы.
Я пошел еще дальше и заменил colorId на color. Это совершенно не обязательно для работы алгоритмов, но я хотел показать все нагляднее.
Для каждого набора смежных значений X и Y вызываем getNodeAtLocation и находим northId, eastId, southId и westId. Больше значения X и Y нам не понадобятся.
После того, как мы нашли количественные ID, конвертируем их в один adjacentIds-массив, что включает в себя только ID, у которых есть значение. Таким образом, нам не нужно дополнительно проверять угловые и боковые блоки, у которых некоторые идентификаторы будут со значением 0. Это позволит нам зациклить массив вместо того, чтобы вручную отмечать каждый количественный ID в алгоритмах.
Вот еще один пример сетки 2×2 с заново сгенерированными блоками, обработанными с помощью addAdjacencies:
[
{ adjacentIds: [ 1, 2 ], color: 'red', id: 0 },
{ adjacentIds: [ 3, 0 ], color: 'grey', id: 1 },
{ adjacentIds: [ 3, 0 ], color: 'blue', id: 2 },
{ adjacentIds: [ 1, 2 ], color: 'blue', id: 3 },
]
Оптимизация предварительной обработки
Для этой статьи я решил значительно упростить алгоритмы, поэтому добавил еще один этап оптимизации. Он состоит в удалении смежных ID, не соответствующих по цвету с текущим блоком.
Переписал функцию addAdjacencies:
const addAdjacencies = (
nodes,
) => (
nodes
.map(({
colorId,
id,
x,
y,
}) => ({
adjacentIds: (
nodes
.filter(({
x: adjacentX,
y: adjacentY,
}) => (
adjacentX === x + 1
&& adjacentY === y
|| (
adjacentX === x - 1
&& adjacentY === y
)
|| (
adjacentX === x
&& adjacentY === y + 1
)
|| (
adjacentX === x
&& adjacentY === y - 1
)
))
.filter(({
colorId: adjacentColorId,
}) => (
adjacentColorId
=== colorId
))
.map(({
id,
}) => (
id
))
),
color: colors[colorId],
id,
}))
.filter(({
adjacentIds,
}) => (
adjacentIds
.length > 0
))
)
Уменьшил addAdjacencies, добавил больше функциональности.
После отсеивания блоков, которые не совпадают по цвету, мы можем быть на 100% уверены, что все ID в adjacentIds – смежные блоки.
Затем я отсеял все смежные, но не совпадающие по цвету блоки. Это еще больше упростило алгоритм, и мы теперь работаем только с нужными блоками.
Неправильный способ – рекурсия
Для решения этой задачи в Google не рекомендуют применять рекурсию: она вызовет переполнение стека.
Однако есть два способа справиться с этой проблемой: итерирование и хвостовая рекурсия. Мы остановимся на итерировании, потому что хвостовая рекурсия больше не поддерживается в JavaScript.
Мы все еще можем эмулировать хвостовую рекурсию в JavaScript. Однако нам нужен простой способ, поэтому мы используем обычную рекурсивную функцию.
Прежде чем запустить код, нужно разобраться в алгоритме. В случае с рекурсией есть смысл применить «поиск в глубину». Не переживайте, если не знаете этот термин. Я узнал его от коллеги, которому показывал свои решения.
Алгоритм
Начнем с какого-нибудь блока и пойдем по алгоритму до конечной точки, затем вернемся и выберем следующий путь ветвления, пока не просканируем весь участок этого цвета.
Еще нужно отслеживать, какие блоки мы уже рассмотрели и из скольких состоял самый большой участок одного цвета.
Я разделил функцию на две части. В одной части хранится информация о самом большом участке и уже обработанных ID. Одновременно с этим каждый блок зацикливается хотя бы по одному разу. Другая часть алгоритма начинается с корневого блока без сканирования и выполняет поиск в глубину.
Вот как выглядят эти две функции:
const getContiguousIds = ({
contiguousIds = [],
node,
nodes,
}) => (
node
.adjacentIds
.reduce(
(
contiguousIds,
adjacentId,
) => (
contiguousIds
.includes(adjacentId)
? contiguousIds
: (
getContiguousIds({
contiguousIds,
node: (
nodes
.find(({
id,
}) => (
id
=== adjacentId
))
),
nodes,
})
)
),
(
contiguousIds
.concat(
node
.id
)
),
)
)
const getLargestContiguousNodes = (
nodes,
) => (
nodes
.reduce(
(
prevState,
node,
) => {
if (
prevState
.scannedIds
.includes(node.id)
) {
return prevState
}
const contiguousIds = (
getContiguousIds({
node,
nodes,
})
)
const {
largestContiguousIds,
scannedIds,
} = prevState
return {
largestContiguousIds: (
contiguousIds.length
> largestContiguousIds.length
? contiguousIds
: largestContiguousIds
),
scannedIds: (
scannedIds
.concat(contiguousIds)
),
}
},
{
largestContiguousIds: [],
scannedIds: [],
},
)
.largestContiguousIds
)
Это же безумие! Я сомневался, стоит ли показывать такой код – это черновая версия. Судя по этому черновику, меня бы не взяли в Google.
Давайте шаг за шагом его упростим.
Рекурсивная функция
getContiguousIds – это наша рекурсивная функция, она вызывается один раз для каждого блока. После каждого цикла список смежных блоков обновляется.
В этой функции есть всего одно условие: этот блок уже есть в списке? Если нет, снова вызываем getContiguousIds: так у нас появится обновленный список смежных блоков, который возвращается к редуктору и используется в следующем adjacentId.
Вы можете спросить: как добавляются значения к contiguousIds? Это происходит, когда мы используем concat, объединяя текущий блок в contiguousIds. Каждый раз, когда происходит рекурсия, нужно убедиться, что текущий блок добавляется в список contiguousIds, прежде чем зацикливать adjacentIds.
Постоянное добавление текущего блока гарантирует, что мы не столкнемся с бесконечной рекурсией.
Цикл
Вторая половина этой функции также проходит через каждый блок по одному разу.
У нас есть редуктор рекурсивной функции. Он проверяет, просканирован ли код. Если да, то цикл продолжается до тех пор, пока не найдется не просканированный блок, или пока мы не дойдем до конца цикла.
Если блок не был просканирован, вызовите getContiguousIds и подождите. Это происходит синхронно, но может занять некоторое время.
Как только мы получим список contiguousIDs, сравните его со списком largestContiguousIDs.Если он больше, сохраните это значение.
Чтобы отмечать просканированные данные, добавим contiguousIDs в список scannedIds.
Получилось довольно наглядно и понятно.
Выполнение
Даже обрабатывая 10 000 блоков трех случайных цветов, алгоритм не сталкивается с переполнением стека. Если бы блоки были одного цвета, возможно, переполнение стека могло произойти: рекурсивной функции пришлось бы проходить 10 000 рекурсий.
Последовательная итерация
Стек вызова функции меньше, чем память, поэтому следующий шаг – сделать все за один цикл.
Мы будем отслеживать список, состоящий из списков блоков и пополнять его до конца цикла.
В этом методе важно, чтобы всевозможные списки блоков хранились в памяти до конца цикла. В примере с рекурсией в памяти сохранялся только самый длинный список.
const getLargestContiguousNodes = (
nodes,
) => (
nodes
.reduce(
(
contiguousIdsList,
{
adjacentIds,
id,
},
) => {
const linkedContiguousIds = (
contiguousIdsList
.reduce(
(
linkedContiguousIds,
contiguousIds,
) => (
contiguousIds
.has(id)
? (
linkedContiguousIds
.add(contiguousIds)
)
: linkedContiguousIds
),
new Set(),
)
)
return (
linkedContiguousIds
.size > 0
? (
contiguousIdsList
.filter((
contiguousIds,
) => (
!(
linkedContiguousIds
.has(contiguousIds)
)
))
.concat(
Array
.from(linkedContiguousIds)
.reduce(
(
linkedContiguousIds,
contiguousIds,
) => (
new Set([
...linkedContiguousIds,
...contiguousIds,
])
),
new Set(adjacentIds),
)
)
)
: (
contiguousIdsList
.concat(
new Set([
...adjacentIds,
id,
])
)
)
)
},
[new Set()],
)
.reduce((
largestContiguousIds = [],
contiguousIds,
) => (
contiguousIds.size
> largestContiguousIds.size
? contiguousIds
: largestContiguousIds
))
)
Еще один безумный код. Давайте в нем разберемся. Цикл проходит каждый блок по одному разу. Теперь с помощью contiguousIdsList мы должны проверить, находится ли наш ID в списке, состоящем из списков блоков.
Если какого-то блока еще нет ни в одном списке contiguousIds, мы добавим его и его adjacentIds. Таким образом, во время циклов какие-то еще блоки будет связаны с этим.
Если блок уже есть в одном из списков, возможно, он есть в нескольких из них. Свяжем все это вместе и удалим несвязанные блоки из contiguousIdsList.
Когда будет готов список, состоящий из списков блоков, мы проверяем, какой из них самый большой. Готово! ;)
Выполнение
В отличие от алгоритма с рекурсией, этот алгоритм справляется с сеткой из 10 000 блоков одного цвета.
Тем не менее, алгоритм медленный; он гораздо медленнее, чем я ожидал. Когда я думал о производительности, я не учел зацикливание списков, и это явно повлияло на скорость алгоритма.
Итерация случайным образом
Я решил взять методологию алгоритма с рекурсией и применить ее итеративно.
Я потратил целую ночь, пытаясь вспомнить, как динамически менять индекс в цикле, и пришел к while(true). Прошло так много времени с тех пор, как я писал традиционные циклы, что я практически все забыл.
Теперь у меня есть оружие, иду в атаку! Я потратил слишком много времени, пытаясь ускорить работу алгоритмов выше, поэтому решил использовать старый добрый метод мутации данных.
Цель этого алгоритма состояла в том, чтобы обработать каждый блок ровно один раз и сохранить информацию только о самом большом участке одного цвета:
const getLargestContiguousNodes = (
nodes,
) => {
let contiguousIds = []
let largestContiguousIds = []
let queuedIds = []
let remainingNodesIndex = 0
let remainingNodes = (
nodes
.slice()
)
while (remainingNodesIndex < remainingNodes.length) {
const [node] = (
remainingNodes
.splice(
remainingNodesIndex,
1,
)
)
const {
adjacentIds,
id,
} = node
contiguousIds
.push(id)
if (
adjacentIds
.length > 0
) {
queuedIds
.push(...adjacentIds)
}
if (
queuedIds
.length > 0
) {
do {
const queuedId = (
queuedIds
.shift()
)
remainingNodesIndex = (
remainingNodes
.findIndex(({
id,
}) => (
id === queuedId
))
)
}
while (
queuedIds.length > 0
&& remainingNodesIndex === -1
)
}
if (
queuedIds.length === 0
&& remainingNodesIndex === -1
) {
if (
contiguousIds.length
> largestContiguousIds.length
) {
largestContiguousIds = contiguousIds
}
contiguousIds = []
remainingNodesIndex = 0
if (
remainingNodes
.length === 0
) {
break
}
}
}
return largestContiguousIds
}
module.exports = getLargestContiguousNodesIterative2
Большинство кандидатов в Google написали бы точно такой же код: несмотря на это, код получился не очень читабельный. Я сам не могу сходу объяснить, что здесь происходит. Чтобы объяснить, сначала нужно посмотреть весь код целиком.
Вместо добавления новых ID в список уже отсканированных, мы выделяем значения из массива remainingNodes.
Все просто! Никому не рекомендую этот метод: сам я пришел к нему, потому что хотел попробовать какой-нибудь другой подход.
Разбиение
Я разбил алгоритм на три раздела, разделенные блоками if.
Давайте начнем со второго раздела. Проверяем queuedIds. Если есть queuedIds, мы делаем еще один цикл по элементам в очереди, чтобы увидеть, есть ли они в remainingNodes.
В третьем разделе все зависит от результатов второго. Если больше нет queuedIds, а remainingNodesIndex равен −1, то мы закончили с этим списком блоков, и нужно начать с нового корневого блока. Новый корневой блок всегда имеет индекс 0, потому что мы сращиваем remainingNodes.
Вернувшись в начало цикла, я мог бы использовать while(true), но мне захотелось найти вариант на всякий случай. Это удобно при отладке, потому что бесконечные циклы могут стать довольно сложной проблемой.
После этого мы сращиваем блок, добавляем его в contiguousIds и добавляем adjacentIds в очередь.
Выполнение
Этот алгоритм оказался почти таким же быстрым, как алгоритм с рекурсией, и быстрее, чем все остальные, справился с сеткой из блоков одного цвета.
Оптимизация данных
Группировка блоков одного цвета
Поскольку нам нужны только блоки одного цвета, мы можем сгруппировать одинаково окрашенные блоки в алгоритме с последовательной итерацией.
Разделение его на три массива уменьшает используемый объем памяти и количество циклов в списке списков. Тем не менее, это не решает ситуацию с сеткой, где все блоки одинакового цвета, поэтому так не получится исправить алгоритм с рекурсией.
Это также означает, что можно выполнить многопоточную операцию, сократив время выполнения почти на треть.
При последовательном выполнении нужно сначала запустить самый большой из трех разделов. Если самый большой раздел больше двух других вместе взятых, ничего проверять не нужно.
Максимально возможный размер
Вместо того, чтобы через определенные интервалы проверять, нашли ли мы самый большой список, можно проверять это каждую итерацию.
Если самый большой участок больше или равен половине доступных блоков (больше 5 000), очевидно, что он и есть самый большой.
Используя алгоритм с произвольной итерацией, можно найти самый большой размер списка и посмотреть, сколько блоков осталось. Если их осталось меньше, чем блоков в самом большом списке, то мы нашли самый большой участок.
Используйте рекурсию
Да, у нее есть свои ограничения, но ее все равно можем использовать. Все, что нам нужно сделать, это проверить количество оставшихся блоков. Если число ниже предела стека, можно переключиться на более быстрый алгоритм с рекурсией. Рискованно, но это уменьшит время выполнения, поскольку мы продвинулись дальше в цикле.
Используйте цикл for
Так как мы знаем максимальное количество элементов, смена функции reduce на традиционный цикл for принесет небольшую пользу.
Почему-то методы Array.prototype намного медленнее циклов for.
Используйте хвостовую рекурсию
Я не рассматривал этот метод, потому что алгоритму с хвостовой рекурсией понадобилась бы отдельная статья.
Это большая тема, которую пришлось бы долго объяснить. Хвостовую рекурсию можно применить в алгоритме с рекурсивной функцией, однако вряд ли так будет быстрее, чем в случае с циклом while.
RxJS: обслуживание против производительности
Есть способ переработать все эти алгоритмы так, чтобы они стали понятнее и легче с точки зрения обслуживания. В качестве основного решения я использовал RxJS в стиле Redux-Observable, но без Redux.
Я решил сначала написать код стандартными способами, а затем передавать данные с помощью RxJS, чтобы увидеть, как далеко это зайдет.
Я сделал 3 версии в RxJS и позволил себе несколько допущений, чтобы ускорить время выполнения. Все три версии выдают результат медленнее, даже при увеличении количества строк и столбцов.
Всю неделю я придумывал возможные решения и прочесывал каждый сантиметр кода. Я даже лежал на полу, закрыв глаза, и думал, думал, думал. Идеи становились все лучше и лучше, но я все равно не укладывался в ограничения скорости JavaScript.
Я мог бы внести целый список оптимизаций, но тогда код получился бы нечитабельным, а мне этого не хотелось (но я все-таки внес одну оптимизацию).
Наконец-то я получил приемлемое решение – самое быстрое: работает за половину отведенного времени. В целом, это лучшая оптимизация кода.
Единственный раз, когда у меня получилась последовательная итерация наблюдаемых данных с большим объемом памяти, это в случае, где все блоки одного цвета. Это был единственный раз. Технически такое решение лучше, чем рекурсивное, потому что в том случае переполняется стек.
Посмотреть код можно на GitHub.
Финальная статистика
В общем, самый большой участок одного цвета составлял в среднем где-то от 30 до 80 блоков.
Сколько времени занимает каждый алгоритм:
## Random Colors Time | Method --- | --- 229.481ms | Recursive 272.303ms | Iterative Random 323.011ms | Iterative Sequential 391.582ms | Redux-Observable Concurrent 686.198ms | Redux-Observable Random 807.839ms | Redux-Observable Sequential ## One Color Time | Method --- | --- 1061.028ms | Iterative Random 1462.143ms | Redux-Observable Random 1840.668ms | Redux-Observable Sequential 2541.227ms | Iterative Sequential
Сколько раз я ни проводил тесты, время выполнения алгоритмов в сравнении друг с другом не менялось.
Метод Redux-Observable Concurrent неэффективен в случае, если все блоки в сетке одного цвета. Я пробовал кучу способов ускорить его, но ничего не вышло.
Разработка игр
За все время работы я дважды сталкивался с подобным кодом. В гораздо меньших масштабах такое было в Lua и во время работы над моей инди-игрой Pulsen.
В первой ситуации я работал над картой мира. У нее был предопределенный список блоков, и я обрабатывал этот список в режиме реального времени. Так появилась возможность нажимать [ВЛЕВО], [ВПРАВО], [ВВЕРХ] и [ВНИЗ] и перемещаться по карте мира, даже если угол карты был немного смещен.
Я также писал генератор блоков для неизвестного списка элементов со значениями X и Y. Звучит знакомо? Еще мне пришлось центрировать эту сетку на экране. Это было гораздо проще сделать в HTML, чем на игровом движке. Хотя центрировать кучу абсолютно позиционированных элементов div тоже нелегко.
В обоих этих случаях время выполнения в реальном времени не имело большого значения, потому что довольно много предварительной обработки происходило при загрузке игры.
Хочу подчеркнуть, что задача TechLead может вам встретиться в работе. Это возможно, но обычно для приложений JavaScript скорость – не ключевой фактор.
Судя по другим видео, в Google TechLead работал с Java. Я предполагаю, что на собеседованиях, которые он проводил, была важна скорость исполнения. Вероятно, у них была куча рабочих задач, обрабатывающих огромные объемы данных, поэтому необходима скорость.
Но тогда это могла быть работа для специалистов по HTML и CSS, и он просто троллил собеседника: кто знает?
Заключение
Судя по финальной статистике, самый нечитаемый код работал быстрее всех и соответствовал всем требованиям. А теперь попытайтесь обслужить этот кошмар!
Я потратил довольно много времени на разработку не-RxJS версий. Скорее всего, это потому, что более быстрые версии требовали комплексного мышления. Redux-Observable позволяет думать небольшими порциями.
Это была действительно интересная и непростая задача. Сначала она показалась мне очень сложной, даже для собеседования в Google, но когда я разбил ее на отдельные шаги, все получилось :)