Live coding на Go

Big-O описывает, как время работы или память алгоритма растут с размером входа n, без учёта констант: O(1) не растёт, O(n) удваивается вместе с n, O(n²) растёт вчетверо. На лайв-кодинге называют и время, и дополнительную память своего решения. Слайс: s[i] стоит O(1); slices.Contains просматривает всё, O(n); append амортизированно O(1); slices.Insert и slices.Delete в середине сдвигают хвост, O(n). Map: чтение, запись и удаление в среднем стоят O(1); range стоит O(n) и идёт в случайном порядке. Отсортированный слайс: slices.BinarySearch работает за O(log n), около 20 сравнений на миллион элементов, но каждая вставка с сохранением порядка стоит O(n). Подходит для данных, которые строят один раз и часто читают. Память: считают только то, что выделено сверх входа: map seen занимает O(n), проход двумя указателями на месте O(1). Большинство ускорений меняют память на время, поэтому спрашивают и то и другое. Константы всё равно важны: на десятке элементов проход по слайсу часто быстрее map, потому что слайс лежит одним непрерывным блоком, а map хеширует каждый ключ.

Посчитайте элементы одного слайса в map, затем пройдите по второму и оставляйте каждый элемент, чей счётчик ещё больше нуля, уменьшая его: O(n + m) по времени и O(min(n, m)) дополнительной памяти вместо O(n·m) у двух вложенных циклов. Сначала спросите про дубликаты: что должны дать [1 1 2] и [1 1 1], [1 1] или [1]? Счётчики в map[T]int сохраняют кратность; для семантики множества возьмите map[T]struct{} и делайте delete ключа после первого совпадения. Считайте меньший слайс: тогда в map будет не больше min(n, m) ключей. Порядок результата: собирайте результат, проходя по слайсу, и никогда не обходом map: её порядок случаен и меняется от запуска к запуску. Оба слайса уже отсортированы: два указателя, которые сдвигают меньшее значение, дают O(n + m) вообще без map. Обобщённая сигнатура: [T comparable] принимает ровно те типы, которые допустимы как ключ map.

Нужен стек: каждую открывающую скобку кладите в него, на закрывающей снимайте верхнюю и проверяйте, что она того же вида. Строка сбалансирована, если ни одно снятие не провалилось и в конце стек пуст: O(n) по времени и O(n) памяти в худшем случае. Слайс служит стеком: append кладёт, s[len(s)-1] читает вершину, s = s[:len(s)-1] снимает её. Отдельного типа стека в Go нет, и он не нужен. Подсчёт не видит порядка: у ([)] и )( число скобок каждого вида совпадает, но они не сбалансированы. Только стек помнит, какая скобка открыта последней. Забытая проверка: на (( ни одно снятие не проваливается, поэтому её отвергает только финальное len(stack) == 0. Закрывающая скобка при пустом стеке означает сразу false. Проверьте это до чтения вершины, иначе stack[len(stack)-1] паникует с index out of range [-1]. Байты здесь безопасны: UTF-8 никогда не использует ASCII-байт внутри многобайтового символа, поэтому проход по s[i] корректно пропускает Привет и обходится без декодирования рун.

Двигайте два указателя с концов к центру, пропускайте всё, что не буква и не цифра, и сравнивайте остальное через unicode.ToLower. Индекс s[i] читает байты, а каждая кириллическая буква занимает два байта, поэтому побайтовое зеркало сравнивает первый байт одной буквы со вторым байтом другой. Два указателя: O(n) по времени и O(1) дополнительной памяти, без перевёрнутой или очищенной копии строки. Декодируйте с обоих концов: utf8.DecodeRuneInString(s[i:]) возвращает первую руну и её ширину в байтах, utf8.DecodeLastRuneInString(s[:j]) возвращает последнюю, так что оба указателя всегда попадают на границы рун. Короткий путь []rune(s) на собеседовании допустим, но стоит сказать, что он берёт O(n) дополнительной памяти, по 4 байта на символ. Фильтр и регистр: unicode.IsLetter или unicode.IsDigit решает, что учитывать, а unicode.ToLower уравнивает А и а. Граничные случаи: пустая строка и строка из одних знаков препинания считаются палиндромами. При этом руна не всегда совпадает с видимым символом: эмодзи с модификатором тона кожи состоит из двух рун.

Заведите два флага, up и down, оба true в начале: пара с a[i-1] > a[i] сбрасывает up, пара с a[i-1] < a[i] сбрасывает down, и слайс монотонен, если уцелел хотя бы один флаг. Один проход, O(n) по времени, O(1) памяти, без сортировки. Равные соседи не сбрасывают ни один флаг, поэтому [2 2 2] и [1 2 2 3] проходят. Выбор направления по первой паре даёт классический баг: в [3 3 1] первая пара равна, и направление неизвестно до первой неравной пары. Два флага снимают этот вопрос. Пустой слайс и слайс из одного элемента монотонны; цикл с i := 1 обрабатывает их без особого случая. Останавливайтесь раньше, как только сброшены оба флага: на неотсортированных данных цикл заканчивается через несколько элементов. Два прохода тоже работают: slices.IsSorted(a) для одного направления, slices.IsSortedFunc с перевёрнутым cmp.Compare для другого. Такое решение верно, но просили другое.

Пройдите список один раз с prev и cur: сохраните cur.Next, направьте cur.Next назад на prev, затем сдвиньте оба на узел вперёд. Когда cur станет nil, prev окажется новой головой. O(n) по времени и O(1) дополнительной памяти. Сначала сохраните следующий узел: если перезаписать cur.Next раньше, остаток списка потерян. Такая ошибка на лайв-кодинге встречается чаще всего. Верните новую голову: старая голова теперь хвост с Next == nil, поэтому вызывающий код пишет head = Reverse(head). Версия, которая ничего не возвращает, оставляет вызывающему список из одного узла. Пустой список и список из одного узла не требуют особого случая: цикл выполнится ноль раз или один. Рекурсивная версия короче, но тратит по кадру стека на узел, O(n) памяти. Стек горутины растёт по мере надобности, поэтому она переживает миллион узлов там, где стек потока ОС фиксированного размера (по умолчанию 8 МБ в Linux) не выдержал бы; но предел на 64-битных системах равен 1 ГБ (стек растёт удвоением, поэтому на деле он останавливается на 512 МБ), и список примерно из 16 миллионов узлов заканчивается fatal error: stack overflow, который recover не перехватывает.

Сложность равна O(n²): slices.Contains просматривает всё, что уже собрано, поэтому при почти уникальных адресах k-й адрес сравнивается с k-1 предыдущими, всего около n²/2 сравнений. Map map[string]struct{} из уже встреченных адресов отвечает на вопрос «уже был?» в среднем за O(1), и вся функция становится O(n). Скрытые циклы: slices.Contains, slices.Index, strings.Contains и slices.Insert выглядят как один шаг, но стоят O(n). Учитывайте их, когда называете сложность. Замер: 50 000 уникальных адресов обрабатываются за 1,2 с, 200 000 за 15 с (в двенадцать раз дольше при вчетверо большем входе); версия с map справляется с 200 000 примерно за 20 мс. Называйте худший случай: если все адреса одинаковые, out остаётся длиной в один элемент и цикл работает за O(n), но продакшен присылает почти уникальный вход. Память: множество стоит O(n) памяти, которую обменяли на время. Порядок сохраняется: слайс по-прежнему собирает результат; обход самой map вернул бы адреса в случайном порядке. Без map: slices.Sort плюс slices.Compact дают O(n log n), но теряют исходный порядок. Строго говоря, сложность равна O(n·L) для адресов длины L, потому что приведение к нижнему регистру и хеширование читают каждый байт.

Дайте каждому слову ключ, общий для всех его анаграмм, и добавляйте слово в groups[key]. Ключом служат либо отсортированные буквы слова, O(k log k) для слова длины k, либо массив счётчиков букв [26]int, O(k). Второй вариант работает, потому что массивы в Go сравнимы и могут быть ключами map. Счётчики как ключ: map[[26]int][]string допустима, а ключ []int нет: компилятор отвечает invalid map key type []int. Массив строится за один проход по слову, но покрывает только фиксированный алфавит, например от a до z: заглавная буква или щ дадут индекс вне диапазона и панику. Отсортированные руны как ключ: rs := []rune(w); slices.Sort(rs); key := string(rs) работает для любого алфавита, включая пила и липа, за O(k log k) на слово. Общая стоимость: O(n·k) со счётчиками, O(n·k log k) с сортировкой, плюс O(n·k) памяти на группы и ключи. Порядок результата: обход map отдаёт группы в случайном порядке. Если ожидается порядок первого появления, держите индекс от ключа к позиции, как ниже, или отсортируйте результат. Уточните вход: считаются ли Listen и Silent анаграммами и важны ли пробелы. Нормализуйте слово до построения ключа.

Держите окно без повторов и map от каждого символа к позиции, где он встречался последний раз. Если текущий символ последний раз встречался внутри окна, сдвиньте start сразу за ту позицию; ответом будет самое широкое окно. Обе границы движутся только вперёд: O(n). **Никогда не сдвигайте start назад**: start = max(start, last[r]+1). Без max в abba последняя a вернёт start на 1, окно снова будет содержать обе b, и ответ получится 3 вместо 2. Почему O(n): правая граница сдвигается один раз на символ, а левая только прыгает вперёд, поэтому каждый символ входит в окно и покидает его не больше одного раза. Руны, а не байты: s[i] даёт байт, а кириллические буквы занимают по два байта, часто с одинаковым первым, поэтому побайтовая версия возвращает 5 для четырёхбуквенного щука. for _, r := range s декодирует руны; позиции считайте в рунах, а не в байтовых смещениях. Фиксированный алфавит: для ASCII массив [128]int заменяет map, без хеширования и без аллокаций. Шаблон: правая граница растёт на каждом шаге, левая сжимается, только пока окно нарушает условие. Тот же цикл решает задачу «самая длинная серия единиц, если можно перевернуть не больше k нулей».

Отсортируйте по началу и пройдите один раз: если следующий интервал начинается раньше, чем кончается последний объединённый, растяните его конец до большего из двух; иначе начните новый интервал. После сортировки интервалы, которые могут пересекаться, оказываются соседями, поэтому хватает одного прохода: O(n log n) в целом, и эту цену задаёт сортировка. Зачем сортировать: без сортировки интервал может пересекаться с другим в дальнем конце слайса, и сравнение всех пар стоит O(n²). После сортировки по началу интервал может пересекаться только с последним объединённым. Берите больший конец: [1,10], за которым идёт [2,3], должен остаться [1,10]. Присваивание last.End = cur.End сжимает его, и такой баг встречается чаще всего. Касающиеся интервалы: объединять ли [1,3] и [3,5], решает <= или < в одной строке. Для слотов бронирования, где 3 означает время окончания, обычно да; уточните. Сортировка в Go: slices.SortFunc с cmp.Compare(a.Start, b.Start) сортирует на месте, поэтому сначала клонируйте слайс, если порядок у вызывающего должен сохраниться. Указатель в результат: last := &out[len(out)-1] безопасен, потому что берётся заново на каждой итерации, после любого append. Если же держать его через append, он может указывать в устаревший массив.

Цикл смешивает два соглашения: hi := len(ts)-1 с lo <= hi задают закрытый диапазон, которому нужно hi = mid - 1, а hi = mid относится к полуоткрытому. Как только lo == hi и ts[mid] >= t, присваивание hi = mid ничего не меняет, и цикл крутится вечно. Когда зависает: для любого t не больше последнего элемента. Для t за концом слайса функция возвращается, ведь тогда выполняется лишь lo = mid + 1, как и для пустого слайса, который вообще не входит в цикл; тест, который ищет только отсутствующие значения, остаётся зелёным. Выберите один инвариант и держитесь его: полуоткрытый [lo, hi), где всё до lo меньше t, а всё начиная с hi не меньше. Цикл идёт, пока диапазон не пуст (lo < hi), каждая ветка его сужает, и в конце lo == hi и есть ответ, len(ts), если подходящего элемента нет. Середина: lo + (hi-lo)/2 не переполняется, в отличие от (lo+hi)/2; с 64-битным int это важно только на немыслимой длине, но интервьюеры любят это услышать. В реальном коде: slices.BinarySearch(ts, t) возвращает ровно эту позицию плюс found, а sort.Search(len(ts), func(i int) bool { return ts[i] >= t }) принимает любой монотонный предикат. Оба на неотсортированном входе молча возвращают неверную позицию. Тесты, которые это ловят: пустой слайс, один элемент, t до первого, между двумя, на серии дубликатов и после последнего, запущенные с go test -timeout 10s, чтобы зависание падало быстро.

h.Push и h.Pop здесь собственные методы типа, которые только дописывают и удаляют последний элемент; порядок кучи поддерживают функции пакета heap.Push(h, x) и heap.Pop(h). Поэтому каждый Pop выбрасывает только что добавленную запись, и topK возвращает первые k слов в случайном порядке обхода map. Как устроены два слоя: heap.Interface просит написать Push и Pop как простое добавление и удаление последнего элемента. heap.Push вызывает ваш метод и затем поднимает новый элемент вверх; heap.Pop меняет корень с последним, просеивает вниз и только потом вызывает ваш. При прямом вызове просеивания нет. Почему min-куча для top k: в куче лежат только k записей, а в корне самая слабая из них, поэтому каждое новое слово стоит не больше O(log k). Итого O(n log k) по времени и O(k) памяти против O(n log n) на сортировку всех n различных слов. Куча не отсортирована: упорядочены только родитель и потомок. Извлечение всех элементов идёт от самого редкого, поэтому заполняйте результат с конца или отсортируйте k записей. Равные частоты: при одинаковых счётчиках выжившие слова всё равно зависят от порядка map. Сравнивайте слово вторым ключом в Less, если вывод должен быть детерминированным. Когда хватит сортировки: для нескольких тысяч различных слов slices.SortFunc по всем проще; кучу предложите для больших входов и потоков.

Нужна map от ключа к узлу двусвязного списка, который хранит записи от самой недавно использованной к самой давней. Get находит узел через map и переносит его в начало; Put вставляет в начало и при переполнении удаляет узел из конца вместе с его ключом в map. Каждый шаг стоит O(1). Одна map не хранит порядок, а порядок map в Go случаен намеренно, поэтому поиск самой давней записи свёлся бы к просмотру сохранённых меток времени, O(n). Слайс для порядка тоже не подходит: перенос элемента в начало сдвигает всё перед ним, O(n). **container/list** даёт стандартный двусвязный список: PushFront, MoveToFront, Back и Remove работают за O(1). Element.Value имеет тип any, поэтому значение достают через type assertion. Храните ключ в узле: вытеснение начинается с конца списка, и без ключа запись в map не удалить, так что map будет только расти. **Get пишет**: он переставляет узлы списка, поэтому конкурентному кэшу нужен sync.Mutex и вокруг Get. Если брать в Get только RLock, потому что он «просто читает», получится гонка данных на списке. В продакшене: github.com/hashicorp/golang-lru/v2 даёт обобщённую потокобезопасную реализацию той же идеи.

Пройдите все клетки; каждый раз, встретив ещё не посещённую сушу, засчитайте остров и залейте его через BFS или DFS, отметив все связанные с ней клетки суши. Каждая клетка обрабатывается константное число раз: O(rows × cols) по времени и памяти. Для подсчёта годится любой обход: DFS короче писать, а BFS заодно даёт кратчайшие расстояния, которые нужны в продолжениях вида «за сколько шагов». Глубина рекурсии: стеки горутин растут по мере надобности, поэтому рекурсивный DFS переживает сетки, на которых переполнился бы стек потока ОС фиксированного размера (по умолчанию 8 МБ в Linux). Предел всё же есть, 1 ГБ на 64-битных системах, а так как стек растёт удвоением, на деле он останавливается на 512 МБ: сетка 3000×3000 из сплошной суши уходит в рекурсию на 9 миллионов кадров и при 60 и более байтах на кадр падает с fatal error: stack overflow, который recover не перехватывает. У явной очереди или стека такого предела нет. Отмечайте при постановке в очередь, а не при извлечении: иначе одна клетка может попасть в очередь до четырёх раз, по разу от каждого соседа. Слайс как очередь: queue = queue[1:] извлекает элемент за O(1); прочитанный префикс остаётся в памяти, пока append не перенесёт очередь в новый массив, и для одной заливки это нормально. Изменение входа: перезапись посещённых 1 на 0 экономит слайс seen, но сначала спросите: сетка может ещё понадобиться вызывающему коду.

Держите текущую голову каждого входа: прочитайте по одному значению из обоих, отправьте меньшее и дочитывайте только ту сторону, откуда оно взято. Когда один вход закрывается, остаток второго проходит насквозь, а выход закрывается, когда вычерпаны оба. O(n + m) по времени, и в любой момент хранятся только два значения. **Не select**: select берёт тот канал, который готов первым, так работает fan-in, и порядок теряется. Сортированному слиянию нужны обе головы перед каждой отправкой, поэтому оно ждёт каждый вход по очереди. Закрытый канал или ноль: v, ok := <-ch отличает настоящий 0 от закрытого канала; если считать нулевое значение признаком конца, всё ломается на входе, где встречается 0. **<= сохраняет стабильность: при равных значениях первым идёт левый вход, как в сортировке слиянием. Отмена**: каждое чтение и каждая отправка ещё и ждут ctx.Done() в select, поэтому потребитель, переставший читать, или вход, который никогда не закроется, не паркуют горутину навсегда. Владение: горутина слияния единственная пишет в out, поэтому она и закрывает его через defer close(out). k каналов: держите k голов в min-куче пар (значение, источник) на container/heap: извлекайте наименьшее, отправляйте его и кладите следующее значение из того же источника. O(N log k) на N значений в сумме.

Задача сводится к топологической сортировке. Поиск в глубину, который добавляет сервис только после всех его зависимостей, сразу даёт корректный порядок запуска; если отслеживать, какие сервисы лежат на текущем пути, цикл обнаруживается в тот момент, когда поиск снова наступает на один из них, и этот путь и надо вернуть как цикл. O(V + E). Почему три состояния, а не флаг visited До сервиса в состоянии done можно дойти повторно через ромб (api и worker оба зависят от db): это нормально и не должно выглядеть как цикл. onPath означает «предок текущего сервиса». Попасть в такой сервис значит найти обратное ребро, а path от него до текущего сервиса и образует цикл: api -> auth -> config -> api. Один булев флаг не различает эти два случая: он либо объявляет ромбы циклами, либо молча пропускает настоящие циклы. Алгоритм Кана, альтернатива на BFS Посчитайте для каждого сервиса число невыполненных зависимостей, поставьте в очередь те, у кого их нет, и при выдаче каждого уменьшайте счётчики зависящих от него, добавляя в очередь те, что дошли до нуля. Он итеративный, и каждую волну очереди можно запускать параллельно. Если на выходе сервисов меньше, чем на входе, в остатке есть цикл, но какой именно, алгоритм Кана не говорит. Детали, которые проверяет интервьюер Направление рёбер: «api зависит от db» значит, что db стартует первым. Обход зависимостей с добавлением после них даёт именно этот порядок; обход обратных рёбер требует развернуть результат. Детерминированность: порядок map в Go случаен, поэтому сортируйте ключи, иначе порядок и найденный цикл меняются от запуска к запуску и ломают тесты. Глубина рекурсии равна самой длинной цепочке зависимостей, для сервисов она невелика; для графа с миллионами узлов берите алгоритм Кана. Неизвестные имена: зависимость, которой нет среди ключей, здесь считается листом; в загрузчике конфигурации такая зависимость скорее означает опечатку, достойную ошибки.

Скачивайте каждую страницу в своей горутине: множество visited под мьютексом помечает URL до того, как его запланировать, буферизованный канал ограничивает число одновременных загрузок, а sync.WaitGroup считает незаконченные страницы. Страница добавляет свои ссылки в счётчик до собственного Done, поэтому Wait возвращается, только когда работы не осталось. Завершение Worker pool знает вход заранее и закрывает канал задач, когда тот кончился. Работа краулера растёт по ходу, момента для закрытия канала нет, и сигналом служит счётчик незаконченных страниц. wg.Add(1) должен выполниться в родителе до go, пока собственный Done родителя ещё не вызван. Тогда счётчик дойдёт до нуля только после того, как последняя страница запланировала последнего потомка. Каждый URL один раз Проверяйте и отмечайте в одной критической секции. Если проверять под RLock, а отмечать позже под Lock, две горутины обе пройдут проверку и скачают одну и ту же страницу. Отмечайте при планировании, а не при загрузке: URL, на который ссылаются десять страниц, пометит первая, а остальные девять пропустят. Не больше 10 одновременно Семафор охватывает только саму загрузку и освобождается до планирования потомков. Если держать слот, синхронно спускаясь в потомков, обход встанет, как только все 10 владельцев слотов будут ждать свободного слота. Горутины, ожидающие слота, дешёвые, но их число не ограничено. Фиксированный пул из 10 воркеров, читающих очередь, с отдельным счётчиком незаконченной работы ограничивает и их. Ещё fetch принимает ctx, а ожидание слота также ждёт ctx.Done() в select, поэтому отмена быстро останавливает обход. Читать visited после wg.Wait() можно без блокировки: каждый Done происходит раньше (happens-before), чем возвращается Wait.

Держите бэкенды в слайсе и счётчик atomic.Uint64: каждый вызов берёт свой стартовый индекс через Add(1), перебирает бэкенды по кругу с этого места и возвращает первый успешный ответ. Он останавливается после полного круга или когда завершён ctx и возвращает все ошибки, объединённые через errors.Join. Счётчик общий для всех вызовов: b.next++ из конкурентных вызовов означает гонку данных, а мьютекс выстроил бы все вызовы в очередь к одной блокировке ради одного инкремента. Беззнаковый счётчик к тому же не даёт % n стать отрицательным. **Проверяйте ctx между попытками**: если вызывающий уже сдался, перебор оставшихся бэкендов только добавляет нагрузку. Оставьте ctx.Err() в объединённой ошибке, чтобы errors.Is(err, context.Canceled) продолжал работать. Повтор на соседа удваивает его нагрузку: при бэкендах a, b, c и упавшем b каждый вызов, начавшийся с b, попадает на c, и c обслуживает две трети вызовов. Health check, который выводит b из ротации, снова выравнивает нагрузку. Не каждая ошибка стоит другого бэкенда: таймаут или connection refused стоят, а 400 или ошибка валидации упадут везде и только умножат нагрузку. Классифицируйте ошибки до повтора. Идемпотентность: запрос, упавший по таймауту, мог всё же выполниться. Повторяйте только операции, которые безопасно выполнить дважды, или передавайте ключ идемпотентности. Что интервьюер спросит дальше: таймаут на каждую попытку (context.WithTimeout на попытку), чтобы один зависший бэкенд не сжёг весь бюджет, health check или circuit breaker на каждый бэкенд и backoff.