Подготовка к этапу собеседования Алгоритмы

977. Squares of a Sorted Array

Суть задачи в том ,чтобы возвести все числа входного массива в квадрат и вернуть их в отсортированном порядке. Задачу нужно решить за O(n) по времени.

Мне пришла интересная идея ,как ее решить. Классическое решение строится на базе 2 указателей ,но я решил иначе:

Возводя числа в квадрат я решил сохранять их в хешмапе ,где ключи - это сами числа ,а значения - кол-во раз ,сколько это число встречалось ,тк по условию могут быть дубликаты. Далее я делаю обход по хешмапе ,причем в JavaScript ключи итерируются по порядку возрастания их символьных кодов. Тк ключи представляют собой строки ,например ключ 10 - это совокупность 2 символов с кодами 49 и 48 соответственно для символов '1' и '0'. Таким образом перебирая ключи у объекта { 0: null, 1: null } я могу быть уверен ,что движок обойдет их по возрастанию ,и сначала будет 0 ,потом 1. Тоже верно для любых положительных чисел ,как мне кажется.

Получается 2 цикла ,где первый - O(n) ,а второй O(k) ,где k может быть меньше n при наличии дубликатов. Наличие 2 рядом стоящих циклов не влияет на класс сложности ,поэтому итоговую временную сложность можно оценить как O(n). По памяти будет тоже O(n) несмотря на то ,что я сохраняю 2 структуры. Берем снова одну с наибольшей оценкой ,а это O(n).

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

Эталонное решение подразумевает наличие 2 указателей. Я не сильно в нем разобрался ,сходу мне оно кажется даже странным и не очень понятным. Разберу его чуть позже.

Довольно интересный коммент словил на хабре. Оказывается метод ,которым я решал задачу называется методом частичных сумм. Примечательно ,что в теории яндекса ничего про это не было( Как бы я не старался ,не зная этого метода ,я бы не смог решить задачу за O(n) без гуглежки. Сам принцип мне подсказал чптгпт ,но я не знал ,что в его основе лежит какой-то распространенный метод ,который имеет целую область применения.

С одной стороны словил немного чувства позора) С другой ,получил весьма полезный фидбек. В будущем имеет смысл спрашивать у ИИ не только подсказку о решении ,но и принцип или метод ,из которого это решение получилось. Это будет очень полезно ,чтобы в будущем мочь применить его для других задач одной области ,решаемых этим методом.

По приколу выложил статью про решение задачки на Хабре https://habr.com/ru/articles/872650/
Словил кучу замечаний ,но обоснованных. Конечно ,писать заметки здесь и писать статьи на таких площадках как хабр - разные вещи. Здесь я многим пренебрегаю ,допускаю какие-то погрешности в решении или неточности в формулировках. А там это имеет значение. Но и время на написание качественной статьи как правило уходит много. Короче вот такой первый опыт на хабре)

В следующей задаче мне требовалось от полученной строки вычислить максимальную длину подстроки с уникальными символами.

Здесь наблюдается некоторое сходство в мышлении над задачей ,которую я описывал в teletype. Суть в том ,что я на каждой итерации обхода проверяю ,не было ли текущего символа в хешмапе. И если он есть ,я двигаю указатель left на значение из хешмапы по этому символу. В хешмапе ключи - это символы ,а значения - индексы ,на которых в последний раз встречался этот символ.

Далее максимальное значение подстроки вычисляется как максимум от последнего вычисленного максимума и текущей разницы между i (индексом текущей итерации) и указателем left.

Суть в том ,что каждый раз ,встречая символ ,который уже был ранее ,я как бы перестаю учитывать все то ,что было левее него ,включая его самого. Таким образом посредством указателей left и i формируется окно или отрезок ,который гарантировано содержит уникальные символы.

Но мое решение проходило не все тесты. Как оказалось недостаточно просто проверить наличие символа в хешмапе ,чтобы обновить указатель left. Нужно еще проверить ,чтобы он всегда двигался вправо! Ведь может быть ситуация ,когда символ стоял левее текущего указателя left ,и тогда логика нарушится. Этот момент я упустил ,а так мышление было в правильном направлении.

На задачу ушел 1 час ,и по правилам ,которые я себе придумал (уделять на честное решение не более часа) ,я прервал акт насилия над своим мозгом и полез в chatgpt спрашивать ,где у меня ошибка. В общем с одной стороны радует ,что изначально я сообразил общий алгоритм ,но не радует ,что упустил детали ,до которых не додумался даже после анализа упавших тестов. А когда получаешь подсказку ,вроде таким простым это кажется..

Вообще говоря ,тема хешей очень странно подана на яндексе. В теории по большому счету описывались алгоритмы построения хеш-функций. И только одна задача разбиралась в теории - 3-sum. Как мне кажется ,этого недостаточно ,чтобы подготовить к решению подобных задач. Я думаю ,что в теории должно разбираться больше задач из этой классификации ,а затем даваться примеры +- похожие на эти ,но требующие доработок или поданные под другими условиями ,где нужно разглядеть уже показанные в теории паттерны решений. А так как будто получается ,что кидают в воду ,чтобы научить плавать ,но бултыхайся сам как говорится. С одной стороны это побуждает разобраться в вопросе самому ,что хороший поинт для сеньора. С другой - зачем тогда курс. В общем пока с подсказками потихоньку решаются задачи.

Решал сейчас задачу вычисления полиномиального хеша для строки. В приложенной картинке приводится формула для расчета такого хеша. Где s - конкретный символ строки ,a - основание по которому считается хеш ,а m - модуль для вычисления хеша. И вроде все выглядит просто - вычислил числовой код символа через charCodeAt и поехал умножать и складывать по формуле в цикле ,а в конце берем по модулю.

Но вот проблема. При больших строках и основании {a} получаются числа ,выходящие за диапазон точных целых чисел 2^53 - 1. А результате чего получается ситуация ,что берем число Infinity по модулю {m} ,что даст NaN.

Оказалось есть другая формула ,которая помогает избежать переполнения путем вычисления модуля на каждой итерации:

hash = (hash * a + s) % m.

И это работает! Числа не переполняются ,тк вычисление по модулю происходит на каждой итерации и значение не превосходит m. Может быть в теории где-то была эта формула ,и я про нее забыл. Но без подсказки решить не смог бы.. Вот не знаю даже ,что делать с этими формулами ,стоит ли их запоминать или нет.. Надеюсь ,на собесе не будут попадаться подобные задачи.

Была еще мысль использовать BigInt ,но это бы сильно замедлило алгоритм. Причем я помню ,была какая-то задача тоже с переполнением ,где я переписал Number на BigInt и алгоритм проваливал тест по TimeLimit.

Решил в общем описывать решения задачек ,которые мне показались особо интересными на платформе Teletype ,тк там есть поддержка code blocks с подсветкой синтаксиса. И вот моя первая публичная статья https://teletype.in/@webnikler/z-fysc1M7Et
Я разобрал решение задачки ,которую сам не смог решить ,но с чатгпт получилось хотя бы понять смысл корректного решения.

В это воскресенье пройдет вебинар по хешам. Наставник сказал ,что лекция очень важная ,тк по его личному опыту собесов про хешмапы спрашивают в 80% случаев. Из чего следует вывод ,что тема важная. Дается она мне пока с трудом ,но прикол в том ,что воскресенье - это по сути дедлайн спринта ,и нужно сдать финалку по хешам до этого дня.
Я думаю ,немного схитрить и сильно не упарываться в вещи ,которые пока тяжелы для понимания ,но собрать вопросы ,чтобы задать их на лекции и прояснить для себя.

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

Еще я думаю ,что возможно лучше прочитать все теорию целиком ,а только потом приступать к задачам. Сейчас я останавливаюсь на главах ,где предлагают решить практические задачки ,и они сильно тормозят дальнейший прогресс. Прочтение теории занимает гораздо меньше времени ,чем решение задач. Ее можно прочитать сразу.

Добавлю эти новведения в свой менеджерский план.

Прошел вебинар по сортировкам.

Рассмотрели сортировку выбором и пузырьком. В целом они довольно похожи ,но в то время как пузырьковая требует постоянных перестановок ,сортировка выбором сначала найдет наибольший или наименьший элемент и только потом при необходимости переставит его. Однако все равно оба алгоритмы не очень оптимальные ,и работают за O(n^2).

Иногда требуется найти в массиве k наибольших или наименьших элементов. Таким образом можно произвести частичную сортировку ,и стоимость алгоритмов выше снижается до O(n * k) или O(n) ,тк k будет считаться константой.

Вспомнили сортировку подсчетом. Я задал вопрос про то ,когда она актуальна ,и получил следующий ответ: когда диапазон элементов в целом не превышает пары тысяч элементов. Зачастую ограничивают применение до меньших диапазонов - например до сотен элементов. Главное ,чтобы она не отжирала слишком много памяти ,и не было слишком больших разрывов между элементами по значению.

Рассмотрели блочную сортировку (bucket sort) ,которая предполагает разделение данных на блоки ,например на интервалы. Каждый блок можно быстро отсортировать отдельно. Но слишком много накладных расходов ,тк под каждый блок выделяется доп память. В целом может подойти ,если требуется сортировка в определенном диапазоне. Может быть применена в задаче нахождения топ k элементов.

Поразрядная сортировка (radix sort) предполагает группировку по разрядам поочередно - от меньшего к бОльшему. Суть в том ,что на каждой итерации мы расставляем числа по индексам от 0 до 9. Сначала мы это делаем для разряда единиц ,потом для десятков ,затем сотен и т.д. На каждой такой итерации мы достаем числа в той последовательности ,в какой они добавлялись по индексам. И получается частичная сортировка по разряду числа. В конце на самом большом разряде окажется ,что все числа отсортированы.

В целом такая сортировка может работать за O(n * k) ,где k - максимальный разряд числа в массиве. Если он небольшой ,то алгоритм будет достаточно эффективным. Но работает он только с положительными числами (если не наворачивать костыли). Может подойти для задачи про суффиксный массив ,поэтому для алфовитных символов тоже может подойти.

Из сортировок общего назначения вспомнили про сортировку слиянием и быструю сортировку. Слиянием всегда выполняется за O(n log n) независимо от условий ,в то время как в быстрой все зависит от выбора опорного элемента и того ,отсортирован ли уже массив. Однако сортировка слиянием требует доп память O(n) ,в то время как быстрая может не требовать памяти при реализации in-place. Кстати такую реализацию быстрой сортировки я писал для одной из задач на курсе. Как оказалось на практике именно этот вариант и берут из-за преимущества по расходу памяти O(1).

Однако остается минус в виде того - что реализация подразумевает рекурсию. А это память под кадры стека и ограничение глубины.

Рассмотрели пример модификации Quick sort с 2 опорными элементами ,которая работает эффективнее.

Далее рассмотрели еще некоторые способы решения задач вида N smallest-biggest. Это алгоритм быстрого выбора (Quick Select) ,который в целом напоминает быструю сортировку ,а также решение через структуру данных - кучу ,где на вершине хранится всегда наименьший элемент ,а потом убирается. В случае с кучей ,где все операции можно сделать за O(log k) ,где k - размер кучи ,сложность алгоритма поиска может достигать O(n) ,где k обычно превращается в константу.

Рассмотрели некоторые особенности сортировки данных на диске ,когда оперативная память ограничена ,а файл достаточно большой.

В целом вебинар очень полезный.