*когда не проходит один из тестов на литкоде 😅

Типы задач на livecoding. Часть 1.

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

Два указателя — одна из самых популярных тем из алго-секции на фронт-собеседованиях, и пока не теряет обороты.

Какие задачи в целом часто дают на фронт-собеседованиях?
- Алгоритмические (два указателя, скользящее окно, хэш-таблица, стек)
- Особенности языка (асинхронность, контекст, замыкания, метод промиса или массива)
- Основы фреймворка (рефакторинг, асинхронность, особенности)

В этой серии, мы посмотрим решения самых частых алгоритмических задач, потому что задачи на JS мы многократно решали на стримах, и наверняка вы и так их помните) 👇

Заметка: без знания алгоритмической сложности тема может быть непонятной.

Что в может указывать на то, что задача решается указателями?

— Отсортированный массив
— Два массива
— Палиндром

Задача 1. Вариация на TwoSum.

Наверняка все, кто заходил на литкод ее знают.

Дан массив чисел и target, нужно найти в массиве два числа, которые в сумме дают target.

Например: [1, 3, 5, 7, 9, 13]

Решение 1.

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

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

function twoSumSorted(arr, target) {
let left = 0;
let right = arr.length - 1;

while (left < right) {
const sum = arr[left] + arr[right];

if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}

return null;
}

Задача 2. Обьединить два отсортированных массива в один.

Частое решение в JS — собрать массивы через spread оператор, и далее отсортировать через sort(). И оно неверное 😅

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

Решение 2.

У задачи есть два варианта. Базовый и более интересный.

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

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

Если начать с первых элементов, можно затереть первый элемент, и получится не тот результат, который мы ожидаем)

Поэтому фишка этого варианта — делать все тоже самое, но начинать с последних элементов массива. Ну и само собой, записывать элементы тоже в конец. 🌚

function mergeSortedArraysInPlace(arr1, m, arr2, n) {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;

while (i >= 0 && j >= 0) {
if (arr1[i] >= arr2[j]) {
arr1[k] = arr1[i];
i--;
} else {
arr1[k] = arr2[j];
j--;
}
k--;
}

// если в arr2 остался остаток
while (j >= 0) {
arr1[k] = arr2[j];
j--;
k--;
}
}

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

Если было интересно и такой формат разборов полезен — ставьте 👍, и мы сделаем следующие посты на оставшиеся частые темы с фронт-собеседований: скользящее окно, хэш-таблица.

@codepunks_bro