Found in
security
Articles
DS
Data structure
Hash table
Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell.
O(1) on average
2 problems
DS
Data structure
Bloom filter
Says “surely not” or “maybe yes” about set membership, at about 10 bits per item.
O(k)
2 problems
STR
Algorithm
The Aho–Corasick algorithm
Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function.
O(n + Σ|wᵢ| + z)
1 problem
STR
Data structure
BK-tree
All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping.
O(N · depth) to build
1 problem
NUM
Algorithm
Euclid's algorithm
The greatest common divisor of two numbers in O(log n) divisions with remainder.
O(log min(a, b))
2 problems
NUM
Algorithm
Fast exponentiation
aⁿ in O(log n) multiplications: squares over the bits of the exponent.
O(log n) multiplications
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
Problems
Often together
classic 5 interviews 4 in production 4 hashing 2 array 2 membership 2 databases 2 string matching 2 contests 2 number theory 2 divide and conquer 2 hash table 1