Алгоритмы на массивах и строках
Алгоритмические приёмы на последовательностях в Go — два указателя, стек, проверка скобок, слияние интервалов и компакция на месте.
11 вопросов
JuniorКодОчень частоРеализуйте FizzBuzz для 1..n
Реализуйте FizzBuzz для 1..n
Цикл i от 1 до n с бестеговым switch: проверьте i%15 == 0 → FizzBuzz первым, затем i%3 == 0 → Fizz, затем i%5 == 0 → Buzz, иначе печатайте i. Случай %15 должен быть первым, иначе i%3 совпадёт с кратными 15, и FizzBuzz не напечатается. O(n) по времени.
Типичные ошибки
- ✗Проверять
i%3илиi%5доi%15, поэтомуFizzBuzzне печатается - ✗Считать, что
switchв Go по умолчанию проваливается в следующие case - ✗Забывать, что 15 — это НОК, который надо проверять первым
Уточняющие вопросы
- →Почему
switchв Go останавливается на первом совпавшем case безfallthrough? - →Как сделать пары делитель/слово настраиваемыми вместо жёстко заданных?
MiddleКодОчень частоПроверьте, что строка скобок ()[]{} сбалансирована
Проверьте, что строка скобок ()[]{} сбалансирована
Каждую открывающую скобку кладём в стек; на закрывающей делаем pop и проверяем, что она парная — выходим сразу при несовпадении или пустом стеке. Строка валидна, только если все закрывающие совпали и стек пуст в конце. Работает за O(n) по времени и O(n) по памяти.
Открыть задачу →Типичные ошибки
- ✗Вернуть true в конце, не проверив, что стек пуст — остаются незакрытые открывающие
- ✗Сделать pop из пустого стека, когда первой идёт закрывающая, что вызывает panic по индексу
- ✗Сравнивать закрывающую с закрывающей вместо сопоставления каждой закрывающей с ожидаемой открывающей
Уточняющие вопросы
- →Как доработать это, чтобы сообщать индекс первой непарной скобки?
- →Почему ранний выход при несовпадении сохраняет худший случай на уровне O(n)?
JuniorКодЧастоУдалите все нули из слайса целых на месте, вернув усечённый слайс
Удалите все нули из слайса целых на месте, вернув усечённый слайс
Используйте индекс записи j с нуля. Сканируйте индексом чтения i; когда in[i] != 0, копируйте его в in[j] и продвигайте j. После прохода первые j элементов — это ненулевые, поэтому верните in[:j]. Это уплотняет на месте за один проход — O(n) по времени и O(1) доп. памяти — и работает для пустого и полностью нулевого случаев.
Типичные ошибки
- ✗Вырезать через
appendна каждый ноль, что даёт O(n²), а не O(n) - ✗Выделять новый слайс и называть это работой на месте
- ✗Забыть вернуть
in[:j]и вернуть весь слайс
Уточняющие вопросы
- →Как заодно обнулить хвостовые элементы, чтобы освободить ссылки?
- →Как это уплотнение двумя указателями обобщить на удаление по предикату?
JuniorКодЧастоРазверните строку так, чтобы многобайтовые символы UTF-8 остались целыми
Разверните строку так, чтобы многобайтовые символы UTF-8 остались целыми
Сначала преобразуйте строку в []rune, затем меняйте местами с двух концов двумя указателями и верните string(r). Работа по рунам сохраняет многобайтовые символы целыми — разворот сырых байтов разрезал бы руну вроде é и испортил бы её. Алгоритм O(n) по времени и O(n) по памяти.
Типичные ошибки
- ✗Разворачивать
[]byteвместо[]rune, разрезая многобайтовые символы - ✗Считать, что
rangeидёт по строке в обратном порядке - ✗Индексировать
s[i]и трактовать каждый байт как символ
Уточняющие вопросы
- →Почему разворот байтового среза строки
hélloдаёт невалидный UTF-8? - →Как развернуть по графемным кластерам (например, эмодзи с комбинирующими знаками)?
JuniorКодЧастоРеализуйте zip, попарно соединяющую два слайса целых до длины меньшего
Реализуйте zip, попарно соединяющую два слайса целых до длины меньшего
Вычислите minLen как меньшую из двух длин, предвыделите результат через make([][]int, 0, minLen), затем пройдите i от 0 до minLen, добавляя []int{s1[i], s2[i]}. Остановка на более коротком предотвращает выход за границы, а предвыделение ёмкости избегает повторного роста. Это O(minLen) по времени.
Типичные ошибки
- ✗Идти до большей длины и индексировать вне границ
- ✗Думать, что индекс слайса вне границ возвращает ноль, а не паникует
- ✗Сплющивать в один слайс вместо построения пар
Уточняющие вопросы
- →Как сделать вариативную
zip(s ...[]int)для любого числа слайсов? - →Как обобщения (generics) позволят
zipработать со слайсами любого типа элементов?
JuniorТеорияИногдаЧто такое стек и почему его порядок LIFO подходит для проверки скобок?
Что такое стек и почему его порядок LIFO подходит для проверки скобок?
Стек — это коллекция с порядком LIFO: последний добавленный элемент извлекается первым. В Go его моделируют слайсом: push — это append, pop — отсечение последнего элемента через reslice. Он подходит для проверки скобок, потому что закрыться первой должна последняя открытая скобка.
Типичные ошибки
- ✗Путать порядок LIFO с FIFO — извлекать старейший элемент вместо новейшего
- ✗Тянуться к
container/list, когда идиоматичный стек в Go — это обычный слайс - ✗Забыть проверить пустоту стека перед pop, что вызывает panic по индексу
Уточняющие вопросы
- →Как реализовать push и pop на слайсе в Go, не допуская утечки памяти?
- →Почему слайс быстрее
container/listдля стека в Go?
MiddleКодИногдаВернуть k-й с конца узел односвязного списка за один проход
Вернуть k-й с конца узел односвязного списка за один проход
Два указателя с разрывом k. Сначала продвиньте lead на k шагов вперёд; если он сошёл со списка раньше, k вне диапазона — верните nil. Затем двигайте lead и trail (старт с head) вместе, пока lead не дойдёт до последнего узла. trail теперь k-й с конца. Один проход, O(n) время, O(1) память — без предподсчёта длины и без второго обхода.
Типичные ошибки
- ✗Предподсчитывать длину и обходить дважды вместо одного прохода двумя указателями
- ✗Забывать вернуть
nil, когдаkпревышает длину списка - ✗Утверждать, что стек или рекурсия дают O(1) память, хотя это O(n)
Уточняющие вопросы
- →Как обнаружить, что
kвне диапазона, во время форы указателяlead? - →Почему инвариант разрыва в
kсохраняется, пока оба указателя идут вместе?
MiddleКодИногдаСлейте все перекрывающиеся интервалы в срезе пар [начало, конец]
Слейте все перекрывающиеся интервалы в срезе пар [начало, конец]
Отсортируйте интервалы по началу, затем пройдите один раз: держите последний интервал в результате; для каждого следующего, если его начало ≤ конца последнего, они перекрываются — расширьте конец последнего до max(lastEnd, end); иначе добавьте его новым интервалом. Результат — минимальный набор непересекающихся интервалов. O(n log n) на сортировку, O(n) на проход.
Типичные ошибки
- ✗Пропустить сортировку, считая, что один проход по несортированному всё сольёт
- ✗Сравнивать только соседние исходные, упуская транзитивную цепочку через бегущий конец
- ✗Брать пересечение вместо объединения при расширении слитого интервала
Уточняющие вопросы
- →Почему касание (
start == lastEnd) здесь считается перекрытием и когда его можно исключить? - →Как вставить один новый интервал в уже слитый отсортированный список за O(n)?
MiddleКодИногдаОпределите, является ли слайс целых монотонным, за O(n)
Определите, является ли слайс целых монотонным, за O(n)
Держите два булевых флага, isUp и isDown, оба истинны в начале. Пройдите по соседним парам один раз: оставляйте isUp истинным, пока in[i-1] <= in[i], а isDown — пока in[i-1] >= in[i]. Верните isUp || isDown. Ровный участок держит оба истинными, а смена направления гасит один. Это O(n) по времени, O(1) по памяти, один проход.
Типичные ошибки
- ✗Фиксировать направление по первой паре вместо отслеживания обоих флагов
- ✗Считать равные соседние элементы нарушением монотонности
- ✗Решать только по концам, пропуская провал в середине
Уточняющие вопросы
- →Как изменить, чтобы требовать строгую монотонность (без равных соседей)?
- →Можно ли выйти досрочно, как только оба флага станут ложными?
MiddleКодИногдаПроверьте, что строка — палиндром, игнорируя регистр и не-буквы
Проверьте, что строка — палиндром, игнорируя регистр и не-буквы
Приведите строку к нижнему регистру и преобразуйте в []rune, затем два указателя идут навстречу: пропускайте не-буквы и не-цифры через unicode.IsLetter/IsDigit, сравнивайте r[i] != r[j] → false, и сдвигайте оба. Если они пересеклись — это палиндром. O(n) по времени, O(n) по памяти на срез рун.
Типичные ошибки
- ✗Сравнивать байты через
s[i]вместо рун, неверно обрабатывая многобайтовый ввод - ✗Фильтровать только буквы, отбрасывая цифры, которые должны учитываться
- ✗Считать, что
==строк игнорирует регистр и пунктуацию
Уточняющие вопросы
- →Почему подход с байтовыми индексами ломается на строке с многобайтовыми рунами?
- →Как сделать это за O(1) доп. памяти без преобразования в
[]rune?
SeniorКодРедкоНайдите длиннейшую валидную подстроку из () за O(n)
Найдите длиннейшую валидную подстроку из () за O(n)
Кладём в стек индекс-сентинель -1, затем на каждой ( кладём её индекс, а на ) делаем pop. После pop, если стек не пуст, длина текущей валидной серии равна i - stack[top]; если стек опустел — кладём i как новую базу. Отслеживаем максимум — O(n) по времени, O(n) по памяти.
Типичные ошибки
- ✗Хранить символы вместо индексов — без позиций длину не вычислить
- ✗Забыть сентинель
-1, благодаря которомуi - stack[top]даёт верную длину - ✗Класть индекс после опустошающего pop вместо использования его как новой базовой точки отсчёта
Уточняющие вопросы
- →Как двунаправленный проход с двумя счётчиками решает это за O(1) памяти?
- →Почему индекс непарной
)должен стать новой базой стека?
