Ошибка	Последствие
Решать вложенным циклом то, что решает хеш-таблица	O(n²) вместо O(n) — частая причина TLE на собеседовании
Считать `append`/`pop` через срез настоящим O(1)	Это amortized O(1); рост backing array иногда реаллоцирует
Разворачивать строку по байтам	Многобайтовые UTF-8 символы разваливаются — нужен `[]rune`
Фильтровать срез, создавая новый	Лишняя аллокация там, где хватает индекса записи на месте
Путать множество `map[T]bool` и `map[T]struct{}`	`struct{}{}` не занимает памяти под значение — идиоматичнее для set
Сливать интервалы без сортировки	Пропущенные пересечения — слияние требует упорядоченного входа
Брать полный перебор там, где есть структура	Экспоненциальная цена вместо полиномиальной
Хранить в LRU только map без списка	Нет O(1)-вытеснения самого старого элемента

intermediate

Algorithms in Go

Classic algorithmic techniques in Go — two pointers, a stack, a hash map as a set, interval merging, in-place compaction, an LRU cache, and dynamic programming with complexity analysis.

go-algorithms

Practice: 19 questions · 17 tasks →

Sections

Contents

Detailed explanation

Algorithms in Go — the Pattern Matters More Than Memorization

An interview algorithm problem 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 hash map for O(1) lookup instead of a nested loop, a write index for in-place filtering. 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. A set is a map[T]struct{} with a zero-size value. Reversing a string requires going through []rune, or multi-byte UTF-8 characters fall apart. And complexity analysis must distinguish true O(1) from append's amortized O(1), which sometimes reallocates the backing array. This topic dissects algorithmic techniques layer by layer — each with its Go idiom and an honest estimate of time and memory.

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.
Hash-map lookup — a map gives O(1) keyed access and collapses an O(n²) nested loop into a single O(n) pass.
Set and deduplication — map[T]struct{} as a set for membership tests and removing duplicates in O(1).
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.
LRU cache — a hash map plus a doubly linked list give O(1) get, put, and eviction.
Dynamic programming — overlapping subproblems and optimal substructure; a sliding window cuts memory to O(1).
Brute-force search — exhaustive enumeration of the candidate space when there is no structure to prune; the cost is exponential and must be bounded.

Common Mistakes and Traps

Mistake	Consequence
Solving with a nested loop what a hash map solves	O(n²) instead of O(n) — a frequent cause of TLE in interviews
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
Confusing `map[T]bool` and `map[T]struct{}` as a set	`struct{}{}` uses no memory for the value — idiomatic for a set
Merging intervals without sorting	Missed overlaps — merging needs sorted input
Reaching for brute force where structure exists	Exponential cost instead of polynomial
Storing only a map in an LRU, no list	No O(1) eviction of the oldest element

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).
When a hash map or set collapses a quadratic into a linear pass.
How to filter or reverse in place, with no extra allocation.
How an LRU cache's get/put achieve O(1) and why it needs a doubly linked list.
What overlapping subproblems are and how a sliding window removes needless memory.

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

The algorithm section of almost any Go interview tests not memorization but the ability to pick a technique for the task and honestly estimate its complexity. Behind half of the "easy" problems sits one of the recognizable patterns — two pointers, a stack, a hash set, an in-place write index. Whoever recognizes them writes O(n) where the naive solution is O(n²) and never confuses amortized O(1) with true O(1).

Ошибка	Последствие
Решать вложенным циклом то, что решает хеш-таблица	O(n²) вместо O(n) — частая причина TLE на собеседовании
Считать `append`/`pop` через срез настоящим O(1)	Это amortized O(1); рост backing array иногда реаллоцирует
Разворачивать строку по байтам	Многобайтовые UTF-8 символы разваливаются — нужен `[]rune`
Фильтровать срез, создавая новый	Лишняя аллокация там, где хватает индекса записи на месте
Путать множество `map[T]bool` и `map[T]struct{}`	`struct{}{}` не занимает памяти под значение — идиоматичнее для set
Сливать интервалы без сортировки	Пропущенные пересечения — слияние требует упорядоченного входа
Брать полный перебор там, где есть структура	Экспоненциальная цена вместо полиномиальной
Хранить в LRU только map без списка	Нет O(1)-вытеснения самого старого элемента

intermediate

Algorithms in Go

Classic algorithmic techniques in Go — two pointers, a stack, a hash map as a set, interval merging, in-place compaction, an LRU cache, and dynamic programming with complexity analysis.

go-algorithms

Practice: 19 questions · 17 tasks →

Sections

Contents

Detailed explanation

Algorithms in Go — the Pattern Matters More Than Memorization

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.
Hash-map lookup — a map gives O(1) keyed access and collapses an O(n²) nested loop into a single O(n) pass.
Set and deduplication — map[T]struct{} as a set for membership tests and removing duplicates in O(1).
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.
LRU cache — a hash map plus a doubly linked list give O(1) get, put, and eviction.
Dynamic programming — overlapping subproblems and optimal substructure; a sliding window cuts memory to O(1).
Brute-force search — exhaustive enumeration of the candidate space when there is no structure to prune; the cost is exponential and must be bounded.

Common Mistakes and Traps

Mistake	Consequence
Solving with a nested loop what a hash map solves	O(n²) instead of O(n) — a frequent cause of TLE in interviews
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
Confusing `map[T]bool` and `map[T]struct{}` as a set	`struct{}{}` uses no memory for the value — idiomatic for a set
Merging intervals without sorting	Missed overlaps — merging needs sorted input
Reaching for brute force where structure exists	Exponential cost instead of polynomial
Storing only a map in an LRU, no list	No O(1) eviction of the oldest element

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).
When a hash map or set collapses a quadratic into a linear pass.
How to filter or reverse in place, with no extra allocation.
How an LRU cache's get/put achieve O(1) and why it needs a doubly linked list.
What overlapping subproblems are and how a sliding window removes needless memory.

Why it matters

Алгоритмы на Go

Алгоритмы на Go — паттерн важнее зубрёжки

Карта темы

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

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

Algorithms in Go

Algorithms in Go — the Pattern Matters More Than Memorization

Topic Map

Common Mistakes and Traps

Interview Relevance

Алгоритмы на Go

Алгоритмы на Go — паттерн важнее зубрёжки

Карта темы

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

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

Algorithms in Go

Algorithms in Go — the Pattern Matters More Than Memorization

Topic Map

Common Mistakes and Traps

Interview Relevance