Built on
array
Articles
SRT
Algorithm
Binary search
Finds the “no → yes” boundary in ordered data in log₂ n checks.
O(log n)
2 problems
SRT
Algorithm
Counting sort and radix sort
Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n.
O(n + k) and O(d·(n + b))
2 problems
DS
Data structure
Dynamic array
An array that grows by itself: access by index in O(1), appending to the end in O(1) amortised.
O(1) amortised per append
2 problems
DS
Data structure
Binary heap
The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on.
O(log n)
2 problems
DS
Data structure
Disjoint set union
Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks.
O(α(n))
2 problems
NUM
Algorithm
Big integers
Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing.
addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n)
2 problems
TEC
Technique
Cache-friendly data
The same algorithm, a different order of memory accesses: tiling, padded rows and laying data out by field.
the same big O
1 problem
TEC
Technique
Amortized analysis
A bound on a whole sequence of operations, not on each one: by a sum, by coins and by a potential, and where it does not help.
a bound on a sequence
2 problems
TEC
Technique
Choosing a data structure
First the list of operations, then the structure: the cost of each operation in Python and Go on one map.
depends on the choice
1 problem
TEC
Technique
Coordinate compression
Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks.
O(n log n) to compress
2 problems
Problems
Often together
classic 7 in production 7 interviews 6 amortized 3 measurement 3 binary search 2 version control 2 sorting 2 cache-friendly 2 heap 2 tree 2 science and physics 2