Complexity in Interviews

An Amazon L6 interview: the interviewer asks to distribute 200 batch jobs across 100 servers minimizing makespan. A junior writes a greedy algorithm in 5 minutes. A senior in 5 minutes says 'this is NP-hard, reduce from Partition' and discusses Graham's 2-approximation. The pay difference: $80k/year.

• **Google Maps** routing uses ALT (A* + landmarks + triangle inequality) - a heuristic on top of Dijkstra speeding queries up 1000x
• **Netflix** solves CDN content placement as mixed-integer programming in Gurobi - using the solver instead of hand-rolled heuristics
• **OpenAI** uses ILP solvers for GPU cluster training schedules - formulating the problem as linear constraints rather than coding the algorithm by hand

Reductions

In a Google interview, the interviewer asks to assign ad impressions to servers so that total load is minimized. The question sounds specific, but an experienced candidate instantly recognizes **bin packing** - a classic NP-hard problem. This reflex - 'reduce a known hard problem to the new one' - is the essence of **reductions**: a formal transformation from A to B such that solving B yields a solution for A.

Two types exist. **Polynomial-time reduction (A ≤_p B)** means 'B is no easier than A': if there is a polynomial algorithm for B, there is one for A. **Karp reduction** is a special case for decision problems. If 3-SAT reduces to problem X in polynomial time, X is also NP-hard. In an interview, the proof need not be formal - showing **structural analogy** is enough: 'this is set cover with renamed variables.'

**Reduction vs algorithm**: an actual interview rarely requires writing the reduction line by line. It is enough to show the problem is 'complexity-equivalent' to a known NP-hard one and propose an approximation or heuristic.

NP-hardness Proofs

In a principal-engineer interview at Amazon: 'You have 100 servers of varying power and 200 batch jobs. Minimize the completion time of the last job.' A candidate who instantly writes a greedy algorithm is junior. A candidate who says 'this is makespan scheduling, NP-hard, I will reduce from Partition' is senior. NP-hardness does not block a solution - it blocks expecting an optimal one.

The canonical NP-hardness proof pattern: (1) Pick a known NP-hard problem X. (2) Describe a polynomial-time transformation of an X instance into an instance of your problem Y. (3) Prove equivalence: X is solvable iff Y is solvable. In an interview steps 1 and 2 done informally are enough; a full proof takes 20 minutes.

**Canonical reduction toolkit** for interviews: 3-SAT, Vertex Cover, Independent Set, Clique, Hamiltonian Path, Subset Sum, Partition, TSP, Bin Packing, Graph Coloring. Familiarity with these 10 covers 90% of cases.

Algorithm Design After Hardness

TSP is NP-hard, yet Google Maps routes through 100 cities in seconds. Knapsack is NP-hard, yet every ML pipeline solves it for feature selection. Real NP-hard problems get solved - the question is at what cost. In an interview, mastery of the **toolkit** matters: 2-approximation, FPTAS, branch-and-bound, LP relaxation, heuristics (greedy, simulated annealing, beam search), ILP solvers.

**Approximation algorithms** offer a guaranteed factor of the optimum in polynomial time. **FPTAS (Fully Polynomial-Time Approximation Scheme)** is stronger: in O(poly(n, 1/ε)) it finds a (1+ε)·OPT solution. **Parameterized algorithms (FPT)** run exponentially only in a single parameter k (e.g., vertex cover size), not in n. For small k these are practical algorithms.

**What to say if pressed**: 'What approximation ratio?' Knowing the classics: Vertex Cover - 2-approx, TSP - 1.5 (metric), Set Cover - ln(n), Knapsack - FPTAS, Bin Packing - 11/9 + O(1).

Trade-offs (time/space/approximation)

A FAANG candidate suggests a hash table for O(1). The interviewer: 'And memory?' O(n) - but in a real system with a billion keys that is 100 GB of RAM. The candidate must see **trade-offs**: time vs space, exact vs approximate, throughput vs latency, fairness vs efficiency. NP-hardness is one case, but even P-class problems hinge on trade-offs.

Classic example: a **Bloom filter** sacrifices accuracy (false positives) for a 10x memory saving and O(1) checks. **Approximate counters (HyperLogLog)** count unique users in a stream with 2% error in 16 KB instead of gigabytes of HashSet. **Probabilistic data structures** form a whole class of space-vs-accuracy trade-offs.

**Interview principle**: always ask clarifying questions about bounds and SLOs. 'How many unique values? What error rate is acceptable? How much memory?' - this turns the abstract problem into a concrete one, separating senior from junior.

Key Ideas

• **Reductions** are a recognition tool: does the problem reduce to TSP/Knapsack/SAT? It is NP-hard
• **Hardness proofs** in interviews are not formal but structural analogies to a canonical problem in 2 minutes
• **Toolkit after hardness**: approximation (Christofides 1.5x for TSP), FPTAS for Knapsack, ILP solvers (Gurobi, CPLEX) for arbitrary problems
• **Probabilistic structures (Bloom, HLL)** trade accuracy for memory: 0.8% error for a 500,000x saving
• The main senior signal: asks clarifying questions about SLOs and bounds, turning the abstract problem into a concrete one

Related Topics

Back to the FAANG interview: recognizing NP-hardness and proposing an approximation is the line between junior and senior. This connects to:

• P, NP, and complexity classes — The foundation for understanding NP-hardness; without it reductions become a mechanical drill
• Approximation algorithms — Concrete techniques (LP relaxation, primal-dual, derandomization) for building approximations with guarantees

Вопросы для размышления

• In a real 45-minute interview, how much time goes to the hardness proof vs the algorithm? Where is the 'enough' line for the interviewer?
• If the problem is NP-hard but the interviewer expects an 'optimal' answer - is that a test of complexity knowledge or an expectation of brute force on small n? How to read the intent?
• Modern ML methods (GNN-based combinatorial optimization) outperform Christofides on specific data distributions. Does this change the interview approach in 5 years?

Связанные уроки

• cplx-04 — P vs NP is the foundational question for interview problem-solving
• cplx-07 — NP-complete problems appear frequently in technical interviews
• alg-22-backtracking — Backtracking is the standard tool for NP problems in interviews
• alg-01-big-o — Big O is the primary language of analysis in technical interviews