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
appendand 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
jand a read indexifilter 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/popdiffer 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.