Ошибка	Последствие
Решать вложенным циклом то, что решает хеш-таблица	O(n²) вместо O(n) — частая причина TLE на собеседовании
Считать «O(1)» у `map` гарантированным	Это средняя сложность; коллизии и рост таблицы дают худший случай хуже O(1)
Путать множество `map[T]bool` и `map[T]struct{}`	`struct{}{}` не занимает памяти под значение — идиоматичнее для set
Брать `slice`, `map` или функцию ключом множества	Несравнимые типы — код не скомпилируется; нужен сравнимый ключ
Считать наивную рекурсию Фибоначчи приемлемой	Без мемоизации это O(2ⁿ) — одна подзадача пересчитывается в обеих ветках
Хранить в LRU только `map` без списка	Нет O(1)-вытеснения самого старого элемента
Строить LRU на односвязном списке	Вырвать узел за O(1) нельзя — нужен `prev`, иначе поиск соседа за O(n)
Брать полный перебор там, где есть структура	Экспоненциальная цена вместо полиномиальной
Запускать перебор без ограничения	Формально «работает», но не завершится при жизни на большом пространстве

intermediate

Searching, Hashing & DP

Search and optimization techniques in Go — a hash map and a set instead of a quadratic, an LRU cache, dynamic programming, and brute-force search with honest complexity analysis.

go-algorithms-search

Practice: 8 questions · 7 tasks →

Sections

Contents

Detailed explanation

Searching, Hashing & DP

When the naive solution is "too slow," the speed-up almost never comes for free — you pay for it with memory or precomputation. A hash map removes the nested loop by replacing the repeated scan with keyed access in average O(1), but takes O(n) memory for the keys. Dynamic programming collapses an exponential tree of recomputations into a linear pass, but stores a cache of subproblems. An LRU cache keeps three operations constant only by combining a map and a doubly linked list at once. And brute force is an admission that there is nothing to prune: it honestly pays an exponential and therefore must be bounded.

A strong candidate does not just name the technique — they name the cost. Go adds its own details: a set is a map[T]struct{} with a zero-size value, a map key must be a comparable type, and the hash map's "O(1)" is an average complexity, not a guarantee. This topic dissects search and optimization techniques layer by layer — each with its own time-versus-memory trade.

Topic Map

Hash-map lookup — a map gives keyed access in average O(1) and collapses an O(n²) nested loop into a single O(n) pass at the cost of O(n) memory.
Set and deduplication — map[T]struct{} as a set for membership tests and removing duplicates in O(1); the key must be comparable.
LRU cache — a map plus a doubly linked list give O(1) get, put, and eviction of the least-recently-used element.
Dynamic programming — overlapping subproblems and optimal substructure; memoization and a table remove recomputation, 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 `map`'s "O(1)" as guaranteed	It is an average complexity; collisions and table growth give a worst case worse than O(1)
Confusing `map[T]bool` and `map[T]struct{}` as a set	`struct{}{}` uses no memory for the value — idiomatic for a set
Using a `slice`, `map`, or func as a set key	Non-comparable types — the code will not compile; the key must be comparable
Treating naive recursive Fibonacci as acceptable	Without memoization it is O(2ⁿ) — one subproblem is recomputed in both branches
Storing only a `map` in an LRU, no list	No O(1) eviction of the oldest element
Building an LRU on a singly linked list	A node cannot be unlinked in O(1) — you need `prev`, or finding the neighbor is O(n)
Reaching for brute force where structure exists	Exponential cost instead of polynomial
Running brute force with no bound	It formally "works" but will not finish in a lifetime on a large space

Interview Relevance

The search-and-optimization section tests not algorithm memorization but the understanding of the trade: what you spend to win time, and how reliable that win is.

What interviewers usually check:

When a hash map or set collapses a quadratic into a linear pass, and what it costs in memory.
Why map's "O(1)" is an average complexity, not a guarantee.
Which type qualifies as a map key and why a slice does not.
How an LRU cache's get/put achieve O(1) and why it needs a doubly linked list specifically.
What overlapping subproblems are and how memoization or a table removes recomputation.
When brute force is justified and why it is always bounded.

A typical wrong answer: "A map access is O(1), so the solution is always O(1)." That opens a discussion of how the hash map's O(1) is an amortized average complexity: with collisions and table growth a single operation can cost more, and the win over the double loop itself is paid for with O(n) extra memory.

Why it matters

Half of the "medium" problems on a Go interview are a resource trade under the hood. A hash map turns O(n²) into O(n) at the cost of O(n) memory, dynamic programming collapses an exponential into a line at the cost of a cache, and brute force honestly pays an exponential when there is nothing to prune. Whoever sees the trade chooses the structure deliberately and never confuses "average O(1)" with guaranteed O(1).

Ошибка	Последствие
Решать вложенным циклом то, что решает хеш-таблица	O(n²) вместо O(n) — частая причина TLE на собеседовании
Считать «O(1)» у `map` гарантированным	Это средняя сложность; коллизии и рост таблицы дают худший случай хуже O(1)
Путать множество `map[T]bool` и `map[T]struct{}`	`struct{}{}` не занимает памяти под значение — идиоматичнее для set
Брать `slice`, `map` или функцию ключом множества	Несравнимые типы — код не скомпилируется; нужен сравнимый ключ
Считать наивную рекурсию Фибоначчи приемлемой	Без мемоизации это O(2ⁿ) — одна подзадача пересчитывается в обеих ветках
Хранить в LRU только `map` без списка	Нет O(1)-вытеснения самого старого элемента
Строить LRU на односвязном списке	Вырвать узел за O(1) нельзя — нужен `prev`, иначе поиск соседа за O(n)
Брать полный перебор там, где есть структура	Экспоненциальная цена вместо полиномиальной
Запускать перебор без ограничения	Формально «работает», но не завершится при жизни на большом пространстве

intermediate

Searching, Hashing & DP

Search and optimization techniques in Go — a hash map and a set instead of a quadratic, an LRU cache, dynamic programming, and brute-force search with honest complexity analysis.

go-algorithms-search

Practice: 8 questions · 7 tasks →

Sections

Contents

Detailed explanation

Searching, Hashing & DP

Topic Map

Hash-map lookup — a map gives keyed access in average O(1) and collapses an O(n²) nested loop into a single O(n) pass at the cost of O(n) memory.
Set and deduplication — map[T]struct{} as a set for membership tests and removing duplicates in O(1); the key must be comparable.
LRU cache — a map plus a doubly linked list give O(1) get, put, and eviction of the least-recently-used element.
Dynamic programming — overlapping subproblems and optimal substructure; memoization and a table remove recomputation, 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 `map`'s "O(1)" as guaranteed	It is an average complexity; collisions and table growth give a worst case worse than O(1)
Confusing `map[T]bool` and `map[T]struct{}` as a set	`struct{}{}` uses no memory for the value — idiomatic for a set
Using a `slice`, `map`, or func as a set key	Non-comparable types — the code will not compile; the key must be comparable
Treating naive recursive Fibonacci as acceptable	Without memoization it is O(2ⁿ) — one subproblem is recomputed in both branches
Storing only a `map` in an LRU, no list	No O(1) eviction of the oldest element
Building an LRU on a singly linked list	A node cannot be unlinked in O(1) — you need `prev`, or finding the neighbor is O(n)
Reaching for brute force where structure exists	Exponential cost instead of polynomial
Running brute force with no bound	It formally "works" but will not finish in a lifetime on a large space

Interview Relevance

The search-and-optimization section tests not algorithm memorization but the understanding of the trade: what you spend to win time, and how reliable that win is.

What interviewers usually check:

When a hash map or set collapses a quadratic into a linear pass, and what it costs in memory.
Why map's "O(1)" is an average complexity, not a guarantee.
Which type qualifies as a map key and why a slice does not.
How an LRU cache's get/put achieve O(1) and why it needs a doubly linked list specifically.
What overlapping subproblems are and how memoization or a table removes recomputation.
When brute force is justified and why it is always bounded.

Why it matters

Поиск, хеширование и ДП

Поиск, хеширование и ДП

Карта темы

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

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

Searching, Hashing & DP

Searching, Hashing & DP

Topic Map

Common Mistakes and Traps

Interview Relevance

Поиск, хеширование и ДП

Поиск, хеширование и ДП

Карта темы

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

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

Searching, Hashing & DP

Searching, Hashing & DP

Topic Map

Common Mistakes and Traps

Interview Relevance