interviews

SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems 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 SRT Algorithm Interpolation search Estimate the place from the values at the edges: log log n probes on uniform keys and up to n on awkward ones. ≈ log₂ log₂ n on average, n in the worst case 1 problem SRT Algorithm Heapsort A heap right in the array: n log n in the worst case with no extra memory, the insurance of introsort and the Linux kernel's sort. O(n 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 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 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 Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure AVL tree A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n. O(log n) for search, insertion and deletion 2 problems GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply. neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists 2 problems GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems 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 GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 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 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 Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 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 PAR Algorithm Closest pair of points The two nearest of n points in n log n: a cut, a strip 2d wide and seven neighbours; with a grid, n on average. O(n log 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 exponentiation aⁿ in O(log n) multiplications: squares over the bits of the exponent. O(log n) multiplications 2 problems GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems SYS Algorithm Consistent hashing Spreads keys over servers so that adding a server moves only its share. O(log(N·v)) to find a server 1 problem 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 SYS Technique Retry with jitter The pause before a retry doubles and is chosen at random: clients spread out in time and do not hit the server in waves. O(1) per pause decision 2 problems ML Algorithm k-means Splits points into k groups so that points sit close to the centre of their group. O(n · k · d) per step 2 problems ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 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 TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem TEC Technique Fast input and output A million numbers in tens of milliseconds instead of a second: reading it all at once, a buffer and one write of the output. O(size of the input) 1 problem TEC Technique How to benchmark honestly Repetitions, warm-up, median and minimum, timeit and testing.Benchmark—and the usual ways to fool yourself with a measurement. enough repetitions for a series to take at least a tenth of a second 1 problem TEC Technique Complexity from measurements The growth of running time from measurements: the slope, the ratio test, exponentials, and where measurement lies. O(B) per attempt 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 Bit tricks A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion. O(1) per operation on a word 1 problem