Method
recursion
Articles
GRA
Algorithm
Depth-first search
Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E).
O(V + E)
2 problems
DP
Technique
Dynamic programming
Reduce a problem to subproblems, solve each once and keep the answers in a table.
states × transitions
2 problems
PAR
Technique
Backtracking
Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings.
O(bᵈ) in the worst case
2 problems
PAR
Technique
Divide and conquer
Cut, solve the parts the same way, glue; what it costs follows from the levels of the recursion tree and the master theorem.
T(n) = a·T(n/b) + f(n)
2 problems
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 Fourier transform
The discrete Fourier transform in O(N log N): spectra, convolutions, multiplying polynomials and big numbers.
O(N log N)
2 problems
ML
Algorithm
Decision tree
Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most.
O(h · F · n log n) to build; O(h) to answer
2 problems
Problems
Often together
classic 7 interviews 6 contests 4 divide and conquer 2 audio 2 traversal 1 connectivity 1 dependency order 1 stack 1 graph 1 builds and packages 1 compilers 1