Алгоритмы с нуля
Массивы и строки: движок запросов по логу
Знать приём — не то же самое, что потянуться к нему под давлением. Построй маленький движок запросов над числовым логом, реализуй каждый приём юнита руками и дай бенчмаркам доказать, что выбранный приём реально бьёт версию-перебор — с той сложностью, что ты предсказал.
Преврати приёмы юнита в один рабочий модуль: операции с учётом непрерывности, two pointers, sliding window, prefix sum и перестройку in-place — каждый реализован с нуля, протестирован против эталона-перебора и забенчмаркан, чтобы эмпирически подтвердить поведение Big-O.
Построй маленький движок запросов над числовым логом фиксированной длины (например, поминутные счётчики запросов), который отвечает на четыре вида вопросов, каждый — правильным приёмом юнита 02, и докажи тестами и таймингом, что каждый бьёт свой эталон-перебор на предсказанной сложности.
- Таблица тайминга до/после: перебор vs приём для каждого из четырёх видов запросов, измеренные на одном n (и минимум двух значениях n) — реальное время по часам, не оценки.
- Удвоение n примерно удваивает время приёма (O(n) операций) и примерно учетверяет время перебора (O(n²) операций), эмпирически подтверждая предсказанную сложность.
- Результат каждого приёма утверждён равным своему эталону-перебору для всех случайных сидов и перечисленных крайних случаев — тесты проходят.
- Абзац по каждой операции: какой приём, его сложность по времени и памяти и предусловие, на котором он держится (отсортированный вход для two-sum; статический массив для prefix sum; положительные целые для сжимающегося окна; разрушающая запись для in-place).
- Добавь строковый аспект: считай строку лога строкой, проверь палиндромный id через two pointers с концов и собери большой экспорт через push в массив + join — затем забенчмарь против наивного +=, чтобы воспроизвести ловушку конкатенации O(n²).
- Добавь наибольшую подстроку без повторяющихся символов (вариативное окно над набором символов) и подтверди O(n) проверкой принадлежности через хеш-множество.
- Добавь 2D prefix sum над фиксированной сеткой сэмплов и отвечай на запросы суммы прямоугольника за O(1), расширяя одномерную идею.
- Добавь путь обновления: когда один сэмпл меняется, измерь цену O(n)-перестройки prefix и обсуди, когда дерево Фенвика/отрезков было бы правильной следующей структурой вместо обычного prefix-массива.
Это цикл, который ты запускаешь, когда запрос медленный: определи модель стоимости (непрерывность), выбери приём, чьё предусловие данные удовлетворяют, реализуй его против эталона-перебора и подтверди сложность таймингом — а не утверждением. Prefix sum для повторных запросов по диапазону на статичных данных, sliding window для свойств непрерывного подмассива, two pointers для поиска пары на отсортированном, in-place для перестройки при ограниченной памяти. Построив каждый раз на игрушечном логе, ты сделаешь выбор правильного в проде автоматическим.