Ошибка	Последствие
Считать `append`/`pop` через срез настоящим O(1)	Это amortized O(1); рост backing array иногда реаллоцирует
Разворачивать строку по байтам	Многобайтовые UTF-8 символы разваливаются — нужен `[]rune`
Фильтровать срез, создавая новый	Лишняя аллокация там, где хватает индекса записи на месте
Сливать интервалы без сортировки	Пропущенные пересечения — слияние требует упорядоченного входа
Думать, что `pop` со среза удерживает память	Reslice оставляет элемент в backing array — обнуляйте хвост, чтобы дать GC собрать его
Брать два указателя на неотсортированных данных	Приём навстречу предполагает порядок; иначе пара пропускается
Зипать срезы по длине большего	Выход за границы меньшего среза — паника на индексе

intermediate

Array & String Algorithms

Algorithmic techniques over sequences in Go — two pointers, a stack, bracket matching, interval merging, in-place compaction, and a slice zip with complexity analysis.

go-algorithms

Practice: 11 questions · 10 tasks →

Sections

Contents

Detailed explanation

Array & String Algorithms

An algorithm problem over a sequence rarely asks you to invent something new. Almost always a recognizable pattern sits behind it: two pointers for a two-ended walk, a stack for matching nesting, a write index for in-place filtering, a sorted pass for merging intervals. A strong candidate does not recall a solution — they recognize the pattern and immediately state the complexity.

Go adds its own specifics. A stack is modeled with a slice: push is append, pop is a reslice. Reversing a string requires going through []rune, or multi-byte UTF-8 characters fall apart. In-place filtering goes through a write index, with no new allocation. And complexity analysis must distinguish true O(1) from append's amortized O(1), which sometimes reallocates the backing array. This topic dissects array and string techniques layer by layer — each with its Go idiom and an honest estimate of time and memory. For searching, hashing, and dynamic programming, see the companion topic.

Topic Map

Two pointers — two indices moving toward each other or with a fixed gap give O(n) time and O(1) memory over a sequence.
The stack (LIFO) — last in, first out; in Go a slice with append and reslice, the basis of matching and traversal.
Bracket matching — a stack holds the expected closing brackets; a mismatch or an empty stack on a closer means the string is invalid.
Interval merging — sorting by start plus one sweep that merges overlaps gives O(n log n).
In-place compaction — a write index j and a read index i filter a slice with no new allocation in O(n) time and O(1) memory.
Slice zip — pairing two slices up to the shorter length with a preallocated result.

Common Mistakes and Traps

Mistake	Consequence
Treating slice `append`/`pop` as true O(1)	It is amortized O(1); backing-array growth sometimes reallocates
Reversing a string byte by byte	Multi-byte UTF-8 characters fall apart — you need `[]rune`
Filtering a slice by building a new one	A needless allocation where an in-place write index suffices
Merging intervals without sorting	Missed overlaps — merging needs sorted input
Thinking a slice `pop` releases memory	A reslice leaves the element in the backing array — zero the tail so the GC can collect it
Using two pointers on unsorted data	The toward-each-other technique assumes order; otherwise a pair is missed
Zipping slices over the longer length	Out of bounds on the shorter slice — an index panic

Interview Relevance

An algorithm section appears in almost every Go interview. They test not knowledge of a specific problem but the ability to recognize a pattern, implement it idiomatically in Go, and estimate its complexity.

What interviewers usually check:

Whether you recognize the two-pointer technique and when it gives O(n)/O(1).
How to model a stack with a slice and where LIFO is the natural structure (brackets, traversal).
How a stack checks bracket balance in a single pass.
How to filter or reverse in place, with no extra allocation.
Why interval merging needs sorted input and gives O(n log n).
How slice append/pop differ in complexity from true O(1).

A typical wrong answer: "A slice pop is O(1), so a stack is always O(1)." That opens a discussion of how the reslice is indeed O(1), but push via append is amortized O(1): when cap is exhausted it allocates a new backing array and copies the elements.

Why it matters

Behind half of the "easy" array and string problems sits one of the recognizable patterns — two pointers, a stack, an in-place write index. Whoever recognizes them writes O(n) where the naive solution is O(n²), never confuses amortized O(1) with true O(1), and never breaks UTF-8 by reversing a string byte by byte instead of by rune.

Ошибка	Последствие
Считать `append`/`pop` через срез настоящим O(1)	Это amortized O(1); рост backing array иногда реаллоцирует
Разворачивать строку по байтам	Многобайтовые UTF-8 символы разваливаются — нужен `[]rune`
Фильтровать срез, создавая новый	Лишняя аллокация там, где хватает индекса записи на месте
Сливать интервалы без сортировки	Пропущенные пересечения — слияние требует упорядоченного входа
Думать, что `pop` со среза удерживает память	Reslice оставляет элемент в backing array — обнуляйте хвост, чтобы дать GC собрать его
Брать два указателя на неотсортированных данных	Приём навстречу предполагает порядок; иначе пара пропускается
Зипать срезы по длине большего	Выход за границы меньшего среза — паника на индексе

intermediate

Array & String Algorithms

Algorithmic techniques over sequences in Go — two pointers, a stack, bracket matching, interval merging, in-place compaction, and a slice zip with complexity analysis.

go-algorithms

Practice: 11 questions · 10 tasks →

Sections

Contents

Detailed explanation

Array & String Algorithms

Topic Map

Two pointers — two indices moving toward each other or with a fixed gap give O(n) time and O(1) memory over a sequence.
The stack (LIFO) — last in, first out; in Go a slice with append and reslice, the basis of matching and traversal.
Bracket matching — a stack holds the expected closing brackets; a mismatch or an empty stack on a closer means the string is invalid.
Interval merging — sorting by start plus one sweep that merges overlaps gives O(n log n).
In-place compaction — a write index j and a read index i filter a slice with no new allocation in O(n) time and O(1) memory.
Slice zip — pairing two slices up to the shorter length with a preallocated result.

Common Mistakes and Traps

Mistake	Consequence
Treating slice `append`/`pop` as true O(1)	It is amortized O(1); backing-array growth sometimes reallocates
Reversing a string byte by byte	Multi-byte UTF-8 characters fall apart — you need `[]rune`
Filtering a slice by building a new one	A needless allocation where an in-place write index suffices
Merging intervals without sorting	Missed overlaps — merging needs sorted input
Thinking a slice `pop` releases memory	A reslice leaves the element in the backing array — zero the tail so the GC can collect it
Using two pointers on unsorted data	The toward-each-other technique assumes order; otherwise a pair is missed
Zipping slices over the longer length	Out of bounds on the shorter slice — an index panic

Interview Relevance

What interviewers usually check:

Whether you recognize the two-pointer technique and when it gives O(n)/O(1).
How to model a stack with a slice and where LIFO is the natural structure (brackets, traversal).
How a stack checks bracket balance in a single pass.
How to filter or reverse in place, with no extra allocation.
Why interval merging needs sorted input and gives O(n log n).
How slice append/pop differ in complexity from true O(1).

Why it matters

Алгоритмы на массивах и строках

Алгоритмы на массивах и строках

Карта темы

Частые ошибки и ловушки

Значение для собеседований

Array & String Algorithms

Array & String Algorithms

Topic Map

Common Mistakes and Traps

Interview Relevance

Алгоритмы на массивах и строках

Алгоритмы на массивах и строках

Карта темы

Частые ошибки и ловушки

Значение для собеседований

Array & String Algorithms

Array & String Algorithms

Topic Map

Common Mistakes and Traps

Interview Relevance