Solves
compression
Articles
SRT
Algorithm
Exponential search
Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near.
2⌊log₂ i⌋ + 1 questions to position i
1 problem
DS
Data structure
Fenwick tree
Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index.
O(log n) per prefix sum and per update
2 problems
STR
Algorithm
The Burrows–Wheeler transform
A permutation that compresses a text and serves as an index to it: backward search, LF, and read alignment.
O(m) to count a pattern, O(m + k·s) for k positions
2 problems
STR
Algorithm
Huffman code
The optimal prefix code for character frequencies: the two rarest trees are glued together until one is left.
O(n log n)
2 problems
SYS
Data structure
Inverted index and BM25
A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts.
O(total length of the query words' lists); AND by galloping O(m·log(n/m))
2 problems
Problems
Often together
search engines 3 classic 3 interviews 3 in production 3 searching 2 binary search 2 frequencies 2 prefix sums 1 range queries 1 bit tricks 1 array 1 contests 1