Live coding на Kotlin

Big-O описывает, как растут время работы или память с ростом размера входа n, без учёта постоянных множителей. contains у List стоит O(n), у HashSet в среднем O(1), а binarySearch по отсортированному списку работает за O(log n). Константы отбрасываются: и 2n + 10, и n дают O(n); важна только форма кривой. При n = 1 000 000 O(log n) означает около 20 шагов, O(n) миллион, O(n²) триллион. Привычная лестница: O(1), O(log n), O(n), O(n log n) у хорошей сортировки вроде sorted(), O(n²) у вложенных циклов по одним и тем же данным, O(2^n) у перебора всех подмножеств. Средний, худший и амортизированный случай: поиск в HashSet в среднем O(1), но деградирует, когда много ключей попадает в одну корзину. Добавление в конец ArrayList амортизированно O(1): редкое копирование за O(n) размазывается по множеству дешёвых добавлений. **binarySearch требует отсортированных данных**: сортировка стоит O(n log n), поэтому окупается, только если по одному списку ищут много раз. Для отсутствующего элемента функция возвращает -(insertionPoint) - 1. Память тоже считается: построить HashSet из списка стоит один раз O(n) по времени и O(n) дополнительной памяти, обычная плата за поиск за O(1). На лайвкодинге называйте сложность своего решения по времени и по памяти раньше, чем об этом спросит интервьюер.

Перебор проверяет все пары, O(n²). Версия за O(n) проходит массив один раз с HashMap из значения в индекс: для каждого элемента ищет target - x, и если это значение уже встречалось, два индекса и есть ответ. Сначала поиск, потом вставка: иначе [3] с целью 6 сложит элемент сам с собой; этот же порядок обрабатывает дубликаты вроде [3, 3], где вторая тройка находит первую. Чем платим: O(n) по времени в обмен на O(n) дополнительной памяти. Перебору хватает O(1) памяти, и это честный ответ, если ограничена именно память. Вариант с отсортированным массивом: если массив уже отсортирован, два указателя с обоих концов дают O(n) по времени и O(1) по памяти: левый сдвигается, когда сумма мала, правый, когда велика. Сортировка неотсортированного массива теряет исходные индексы, если не сортировать пары с индексами. Уточните заранее: всегда ли ответ ровно один, можно ли использовать элемент дважды и что вернуть, если пары нет (здесь null, а не пустой массив или исключение)?

Два индекса идут навстречу друг другу с обоих концов: пропускают каждый символ, для которого isLetterOrDigit() ложно, сравнивают остальные через lowercaseChar() и останавливаются на первом несовпадении. Это O(n) по времени и O(1) дополнительной памяти. Почему не однострочник: сравнение s.filter { it.isLetterOrDigit() }.lowercase() с его reversed() тоже O(n), но создаёт три новые строки и всегда сканирует весь вход. Задача просит именно версию с двумя указателями. Один ход за шаг: каждая итерация либо пропускает один символ, либо сравнивает одну пару, поэтому i < j проверяется перед каждым обращением и индексы не пересекаются. Граничные случаи: "" и ".," считаются палиндромами (сравнивать нечего); "0P" не палиндром, и этот тест ловит версию, которая выбрасывает цифры. Unicode: isLetterOrDigit() и lowercaseChar() понимают кириллицу, так что «А роза упала на лапу Азора» проходит. Они работают с отдельным UTF-16 Char: эмодзи состоит из двух суррогатных Char, ни один из них не буква, поэтому эмодзи пропускается, как знак препинания.

Стек: каждую открывающую скобку кладите в него, а на закрывающей снимайте верхнюю и проверяйте, что тип совпадает. Строка сбалансирована, если ни одно снятие не провалилось и в конце стек пуст. O(n) по времени и O(n) памяти в худшем случае. Три способа провалиться: закрывающая скобка, когда ничего не открыто (")"), не тот тип ("([)]") и скобки, оставшиеся открытыми в конце ("(("). Последнюю проверку забывают чаще всего. Почему счётчика мало: один счётчик работает для одного типа скобок, а в "([)]" количества верные, но порядок неверный. Какой стек в Kotlin: ArrayDeque с addLast и removeLastOrNull. java.util.Stack наследует Vector и синхронизирует каждый вызов, что здесь не нужно. Мапа из закрывающей скобки в открывающую держит сопоставление в одном месте, и поддержка <> сводится к ещё одной записи.

Пройдите строку один раз, считая, сколько раз подряд повторяется текущий символ. Когда символ меняется, допишите его в StringBuilder, а если счётчик больше 1, то и число. За последней серией смены символа уже нет, поэтому её тоже нужно дописать: именно этот шаг и забывают. O(n) по времени. **StringBuilder, а не +=**: String неизменяема, поэтому result += ... в цикле каждый раз копирует весь результат и превращает один проход в O(n²). Последняя серия: цикл в решении идёт до s.length, на шаг дальше последнего индекса, поэтому последнюю серию записывает та же ветка. Циклу, который останавливается на последнем индексе, нужна отдельная запись после него. Счётчики больше 9: append(count) запишет 12 двумя цифрами, поэтому декодер читает цифры до следующей буквы. Спросите заранее: что делать с пустой строкой, строчными буквами или цифрами во входе ("A12" уже не раскодировать)? Версия, о которой рассказывают кандидаты после собеседований в Яндексе, ещё и требует ошибку на всём, что не входит в A–Z. Проверьте вслух: "", "A", "ABAB" (сжимать нечего) и двенадцать A подряд (получится A12).

Идите по списку с prev, cur и сохранённым next: запомните cur.next, направьте cur.next назад на prev, затем сдвиньте оба вперёд. Когда cur станет null, prev окажется новой головой. O(n) по времени, O(1) дополнительной памяти. **Сначала сохраните next**: после cur.next = prev остаток списка доступен только через сохранённую ссылку. Потерять её и есть классический баг. **Возвращайте prev, а не head**: старая голова теперь стала хвостом, у неё next == null. Рекурсивная версия разворачивает остаток списка, а затем направляет второй узел обратно на первый. Тоже O(n) по времени, но O(n) кадров стека, по одному на узел. Список из 200 000 узлов уже заканчивается StackOverflowError на стеке потока JVM по умолчанию. **tailrec не спасает**: рекурсивный вызов должен быть последней операцией, а эта версия работает и после возврата из него. Версию, которая передаёт prev параметром, можно пометить tailrec, и компилятор превратит её в тот же цикл. Граничные случаи: пустой список и один узел возвращаются без изменений; прогоните вслух один, два и три узла.

Её сложность O(T · F): для каждого из T тегов tag in followed просматривает весь список followed, а tag !in result ещё и result. Переложите оба в хеш-множества, и функция станет O(T + F). **in прячет цикл**: у List contains сравнивает элементы по одному, поэтому одна безобидная строка внутри цикла делает функцию квадратичной. Здесь 50 000 тегов против 2 000 отслеживаемых дают около 100 миллионов сравнений строк. Замер: на случайных данных такого размера исходная версия работала около 800 мс на JVM, а версия с множествами меньше 40 мс при том же результате. На главном потоке телефона 800 мс означают замёрзший экран. Исправление: один раз followed.toHashSet() за O(F), и каждый поиск в среднем O(1). result становится LinkedHashSet: add отбрасывает дубликаты за O(1) и сохраняет порядок первого появления, который обычный HashSet потерял бы. Версия цепочкой: flatMap, filter { it in wanted }, distinct(). distinct() держит собственный HashSet, поэтому она тоже линейна, если wanted является множеством, а не исходным списком. Где ещё это прячется: indexOf или contains у List внутри цикла и removeAt(0) у ArrayList в цикле: каждый такой вызов сдвигает весь массив.

Возьмите ключ, одинаковый для всех анаграмм: отсортированные буквы слова, так что eat, tea и ate дают aet, а остальное сделает groupBy. Для n слов длины k это O(n · k log k); подсчёт букв вместо сортировки даёт O(n · k). **groupBy сохраняет порядок**: он строит LinkedHashMap, поэтому группы идут в порядке появления их первого слова, и результат легко проверить. Ключ из подсчёта: для строчных a–z сигнатурой служит IntArray(26) с количеством каждой буквы; на длинных словах это быстрее сортировки. Ловушка с массивом: сам IntArray не может быть ключом, потому что у массивов equals и hashCode сравнивают ссылки, и каждое слово получит отдельную группу. Превратите его в ключ через toList() или joinToString(","). Уточните алфавит: заглавные буквы, пробелы или кириллица ломают версию на 26 ячеек (c - 'a' выходит за границы). Отсортированный ключ работает с любыми символами; если регистр не важен, сначала вызовите lowercase(). Память: O(n · k) на ключи и группы, того же порядка, что и вход.

Держите окно [start, end] без повторов и мапу из каждого символа в индекс, где он встречался в последний раз. Сдвигайте end по одному шагу; если новый символ уже встречался внутри окна, переносите start сразу за ту раннюю копию. Ответ равен самому широкому окну за проход. **Пройдём pwwkew**: p, pw (2); вторая w встречалась на позиции 1, поэтому start прыгает на 2 и окно равно w; дальше wk, wke (3); последняя w встречалась на позиции 2, поэтому start прыгает на 3: kew (3). Ответ 3. **Проверка prev >= start**: в abba последняя a встречалась на позиции 0, уже за пределами окна [2, 3]. Без проверки start откатится назад на 1, и ответ получится 3 вместо 2. Почему O(n): end сдвигается n раз, а start движется только вперёд, поэтому каждый символ входит в окно и выходит из него не больше одного раза. Перезапуск сканирования с каждой позиции даёт O(n²). Другой вариант держит HashSet символов окна и удаляет символы слева, пока дубликат не исчезнет: тоже O(n), но до 2n шагов. Маленький алфавит: для ASCII-входа IntArray(128) с последними позициями заменяет мапу и обходится без боксинга.

Алгоритм Кадане: один проход, в котором хранится сумма лучшего отрезка, заканчивающегося на текущем индексе. Когда эта текущая сумма опустилась до нуля или ниже, начинайте новый отрезок здесь: неположительный префикс может только уменьшить то, что идёт дальше. Запоминайте начало при каждом перезапуске и границы при каждом новом рекорде. Пример: в [-2, 1, -3, 4, -1, 2, 1, -5, 4] отрезок перезапускается на 4 (индекс 3) и достигает максимума на индексе 6: сумма 6, границы 3..6. Все числа отрицательные: начинайте лучший результат с первого элемента, а не с 0, иначе [-3, -1, -2] вернёт 0 для пустого подмассива вместо -1 на индексе 1. Уточните, допустим ли пустой подмассив. Границы: сохраняйте from при перезапуске отрезка и копируйте from и i, только когда сумма побила рекорд. Если обновлять их на каждом шаге, вернутся границы последнего отрезка, а не лучшего. Почему это работает: лучший подмассив, заканчивающийся на i, равен либо одному a[i], либо лучшему подмассиву, заканчивающемуся на i - 1, плюс a[i]. Это рекуррентное соотношение и есть динамическое программирование с O(1) памяти. Переполнение: суммируйте в Long; два элемента Int.MAX_VALUE уже переполняют Int. Равные суммы: > сохраняет первый лучший отрезок, >= последний; скажите, какой вы возвращаете.

Отсортируйте по началу, затем пройдите один раз: если следующий интервал начинается раньше, чем кончается последний объединённый, продлите конец последнего до большего из двух концов; иначе начните новый блок. Сортировка стоит O(n log n) и доминирует, проход занимает O(n). Зачем сортировать: когда интервалы упорядочены по началу, всё, что пересекается с текущим блоком, идёт сразу за ним, и достаточно одного сравнения с последним объединённым интервалом. Без сортировки каждый интервал приходится сверять со всеми остальными, O(n²). **maxOf для конца**: [1,10], за которым идёт [2,3], должен остаться [1,10]; если взять конец следующего интервала, блок сожмётся до [1,3]. Касающиеся интервалы: спросите, сливаются ли [1,3] и [3,5]. Замкнутые отрезки делят точку 3 (<=); бронирования как полуоткрытые промежутки времени, 1–3 и 3–5, не пересекаются (<). Что даёт Kotlin: IntRange задаёт замкнутый интервал с first и last. Для времени понятнее data class Slot(val start: Long, val end: Long) с явно исключённым концом. Не трогайте вход: sortedBy возвращает новый список, а sortBy у MutableList вызывающего кода тайком переупорядочит его. Продолжения задачи: вставка одного интервала в уже объединённый список делается за O(n) без пересортировки; «может ли один человек попасть на все эти встречи» решается той же сортировкой и проверкой соседей.

lo = mid не сужает диапазон: как только hi == lo + 1, mid совпадает с lo, и если a[mid] < target, цикл бесконечно присваивает lo то же значение. mid, который меньше цели, не может быть ответом, поэтому исправление выглядит как lo = mid + 1. **Трассировка [1, 2, 2, 2, 5] с целью 2**: hi опускается до 2, затем до 1; при lo = 0 и hi = 1 получается mid = 0 и a[0] = 1 < 2, так что lo остаётся 0. Зависает любой вход, который доходит до этого состояния, включая [1, 3] с целью 3. Инвариант: при полуоткрытом диапазоне [lo, hi) первое совпадение всегда внутри него. lo = mid + 1 отбрасывает слишком маленький mid, hi = mid оставляет кандидата, поэтому каждая итерация сужает диапазон и цикл завершается. **hi = a.size: заодно покрывает «вставить в конец» и убирает отдельную проверку на пустой массив. Почему не стандартная библиотека**: binarySearch возвращает какой-то из совпадающих индексов, не обязательно первый, поэтому задача и просит такой поиск нижней границы. Переполнение: (lo + hi) / 2 переполняется, когда lo + hi превышает Int.MAX_VALUE; (lo + hi) ushr 1 или lo + (hi - lo) / 2 не переполняются. С массивами на телефоне это редкость, но интервьюеры спрашивают. Проверьте: пустой массив, один элемент, цель меньше первого и больше последнего элемента и массив из одинаковых элементов.

Сначала посчитайте частоты мапой (groupingBy { it }.eachCount()), затем выберите k лучших: min-heap размера k даёт O(n + m log k) для m различных значений, а bucket sort по частоте даёт O(n), потому что ни одна частота не превышает n. Min-heap, а не max-heap: держите не больше k записей и выкидывайте наименьшую частоту, когда куча вырастает больше k; оставшиеся и есть ответ. Max-heap из всех m записей тоже работает, но стоит O(m log m) на заполнение и O(m) памяти. **Детали PriorityQueue**: это бинарная куча из java.util. add и poll стоят O(log k), но итерация по ней не идёт в порядке приоритета, поэтому для отсортированного результата вычерпывайте её через poll(). Bucket sort: массив из n + 1 списков с индексом по частоте, который читается от старшего индекса вниз, пока не набрано k значений. O(n) по времени и памяти, без сравнений. Как выбирать: куча, когда k мало, а данных много или они приходят потоком, ведь кроме частот она держит только k записей; корзины, когда всё в памяти и нужна линейная оценка. Третий ответ, quickselect по различным значениям, даёт O(m) в среднем и O(m²) в худшем случае. Равные частоты: скажите, как вы их разрешаете. Корзины возвращают значения с равной частотой в порядке первого появления, потому что groupingBy его сохраняет; куча не даёт фиксированного порядка, если компаратор не добавляет второй ключ.

Обойдите все клетки; каждая непосещённая клетка суши начинает новый остров, который вы заливаете обходом в ширину (BFS) или в глубину (DFS), помечая всю его сушу посещённой. В обоих случаях это O(rows · cols). Рекурсивному DFS нужен кадр стека на каждую клетку острова, поэтому большой остров переполняет стек. Переполнение реально: сетка 1000 × 1000 из одной суши означает остров в миллион клеток, и рекурсивный DFS бросает StackOverflowError на обычном потоке, чей стек вмещает лишь несколько десятков тысяч небольших кадров. BFS с ArrayDeque или DFS с собственным стеком держит эту работу в куче. Помечайте при постановке в очередь: если ставить seen при добавлении клетки, а не при извлечении, одну и ту же клетку не добавят в очередь несколько соседей. Массив посещений или изменение входа: замена 1 на 0 на месте экономит память, но портит сетку вызывающего кода; BooleanArray на строку стоит байт на клетку и оставляет вход нетронутым. Четыре или восемь соседей: спросите, соединяют ли острова диагонали; это одно изменение в списке steps. Union-find даёт другой ответ, и он лучше для продолжения задачи, где клетки суши добавляются по одной и после каждой спрашивают число островов.

Он печатает B, D, A, C, E. launch только планирует корутину, и единственный поток runBlocking запускает её, когда родитель приостанавливается; coroutineScope выполняет свой блок сразу, а затем приостанавливается до завершения дочерней корутины, поэтому E ждёт C. **B раньше A**: родительская корутина держит поток, пока не приостановится; launch ставит A в очередь event loop у runBlocking и возвращается. **D раньше A**: вход в coroutineScope не является приостановкой. Его тело выполняется сразу, ставит в очередь внутренний launch и печатает D. **Затем A и C**: в конце блока coroutineScope приостанавливается, чтобы дождаться дочерней корутины, поток освобождается, и очередь выполняет A, затем запускает внутреннюю корутину, которая через 100 мс печатает C. **E последней**: coroutineScope возвращается, только когда завершились все его дочерние корутины. Это и есть структурированная конкурентность (structured concurrency). Варианты, которые спрашивают: launch(start = CoroutineStart.UNDISPATCHED) печатает A первой (A B D C E); yield() после println("B") даёт B A D C E; замена coroutineScope на launch даёт B E A D C, потому что больше никто ничего не ждёт. Только на одном потоке: на многопоточном диспетчере вроде Dispatchers.Default A может выполниться параллельно с B, и порядок перестаёт быть фиксированным.

Запустите по одному async на URL внутри coroutineScope, оберните каждый запрос в withPermit { } у Semaphore(4) и закончите awaitAll(). Сотня корутин стоит дёшево; запросы ограничивает именно семафор, а awaitAll сохраняет порядок входа. Порядок бесплатно: Deferred создаются в порядке входа, и awaitAll возвращает их значения в том же порядке, как бы ни завершались загрузки. **Ловушка limitedParallelism(4)**: он ограничивает потоки, на которых выполняются корутины, а не открытые запросы. Suspend-вызов (Retrofit suspend, Ktor) освобождает поток на время ожидания, поэтому все 100 вызовов стартуют сразу: с фейковым suspend-загрузчиком пик составил 100, а не 4. Дальше вызовы Retrofit встают в очередь диспетчера OkHttp по 5 на хост, и этот лимит выбирали не вы. limitedParallelism ограничивает только блокирующие вызовы. **chunked(4) даёт медленный ответ: каждая пачка ждёт свою самую медленную загрузку, поэтому большую часть времени запросов идёт меньше четырёх. Ошибки**: внутри coroutineScope первое исключение отменяет остальные загрузки и пробрасывается дальше. Если одна битая картинка не должна топить всю пачку, ловите ошибку внутри async и возвращайте null или Result. Альтернатива на Flow: flatMapMerge(concurrency = 4) тоже ограничивает параллелизм, но выдаёт результаты в порядке завершения, так что для восстановления порядка придётся тащить индекс. Воркеры: четыре корутины, которые забирают URL из Channel, работают не хуже и лучше подходят, когда URL приходят бесконечным потоком.

Это топологическая сортировка ориентированного графа. DFS, который добавляет модуль в порядок только после всех его зависимостей, даёт корректный порядок сборки; встреча с модулем, который ещё лежит на текущем пути, означает обратное ребро, и путь от этого модуля и есть цикл. O(V + E). DFS Три состояния: не посещён, на текущем пути, готов. HashSet для готовых и LinkedHashSet для пути дают проверки за O(1) и хранят путь по порядку, так что цикл можно напечатать прямо из него. Post-order и есть порядок сборки: модуль добавляется только после всех своих зависимостей, поэтому :core:model идёт раньше :core:network, а тот раньше фич и :app. Сообщение о цикле: на обратном ребре цикл образует путь от повторившегося модуля и дальше плюс сам этот модуль: :feature:feed -> :core:network -> :core:auth -> :feature:feed. Gradle отказывается собирать такой граф с ошибкой о циклической зависимости. Листовые модули: модуль, который встречается только как зависимость, например :core:ui, всё равно посещается и попадает в порядок. Вместо этого алгоритм Кана Посчитайте для каждого модуля число ещё не собранных зависимостей, поставьте в очередь все модули без них, затем по одному доставайте, добавляйте в порядок и уменьшайте счётчики зависящих от них. Модули, оставшиеся после опустошения очереди, лежат в цикле или за ним. Он итеративный, так что ограничения глубины стека нет, и он показывает параллелизм: модули, которые одновременно стоят в очереди, можно собирать одновременно, на этой идее построен --parallel в Gradle. Его слабое место: оставшиеся модули доказывают, что цикл есть, но не называют путь; найти его можно DFS по ним. Граничные случаи Модуль, зависящий от самого себя, образует цикл длины один; пустая мапа даёт пустой порядок. Глубина рекурсии равна самой длинной цепочке зависимостей: для 40 модулей это нормально, для графа на миллион узлов нет, и там надёжнее версия Кана. Корректных порядков несколько; если результат должен воспроизводиться, обходите модули в фиксированном порядке.

Запустите оба запроса внутри channelFlow, отправляйте через send каждый успех и глотайте каждую сетевую ошибку, а первое значение берите через firstOrNull(), который отменяет flow и проигравший запрос. Оберните это в withTimeoutOrNull(2_000) и читайте кэш, если результат null. Почему именно так Первый успешный, а не первый завершившийся: зеркало, которое упало за 50 мс, не должно победить. Перехват IOException внутри его launch отбрасывает этот результат, а второй запрос продолжает работу. Отмена происходит сама: firstOrNull() прекращает сбор после одного элемента, и это отменяет скоуп channelFlow и все ещё работающие дочерние корутины. Вызов Retrofit или Ktor, отменённый так, отменяет и свой HTTP-запрос. Оба зеркала упали: каждая дочерняя корутина завершается без отправки, канал закрывается, и firstOrNull() возвращает null, так что кэш отвечает сразу, а не через 2 секунды. Таймаут: withTimeoutOrNull отменяет блок и возвращает null. withTimeout бросил бы TimeoutCancellationException, а это CancellationException, который широкий catch легко проглатывает. Ответы, которые выглядят верными **select { a.onAwait { it }; b.onAwait { it } }** возвращает первый завершившийся Deferred, и ошибка тоже считается: быстрый сбой пробрасывается из select, а внутри coroutineScope ещё и отменяет соседа. Даже если каждый async при ошибке возвращает null, select выберет этот null; пришлось бы крутить цикл, пока не придёт значение или не закончатся все запросы. **awaitAll() ждёт оба ответа, и преимущество быстрого зеркала пропадает. Ловите узко**: catch (e: Exception) в дочерней корутине ловит и CancellationException, который останавливает проигравшего. Здесь это безвредно, но в цикле ретраев отменённый запрос продолжит жить. Тестирование С runTest и фейковыми API на delay виртуальное время мгновенно прогоняет все четыре случая: быстрый основной сервер, основной падает первым, оба падают, оба медленнее 2 секунд.