Algorithms

Part I — Foundations · Interview reference

Senior algorithm competence is less about memorizing 200 LeetCode patterns and more about: stating complexity correctly, choosing the right approach under constraints, proving correctness intuition, and knowing when an approximate / systems solution beats a clever O(n log n) whiteboard win.

Complexity — what you must say precisely

Always state: time and extra space; offline vs online; comparison model vs hashing.

Master method / recursion trees: be able to derive T(n) = 2T(n/2) + O(n) → O(n log n).

Technique catalog (interview toolkit)

Two pointers / sliding window

• Sorted arrays, pair sums, substring with constraints
• Maintain invariant; prove each pointer moves ≤ n times → O(n)

Java: Usually two indices over char[] / int[] / String / ArrayList. Sliding window often pairs with HashMap / int[] frequency counts. Prefer charAt / array access over repeated substring (allocates).

Binary search

• On sorted arrays and on monotonic answer space (“search the answer”)
• Template pitfalls: mid overflow (lo + (hi-lo)/2), inclusive vs exclusive bounds, duplicates

Java: Arrays.binarySearch / Collections.binarySearch require a sorted range. Negative return encodes insertion point (-(ip) - 1). Comparator overload for objects. Hash lookup is not binary search — that is HashMap bin/tree walk.

Sorting

Know when O(n log n) is required (comparison lower bound Ω(n log n)) vs linear special cases.

Java:

Interview trap: sorting Integer[] vs int[] is a different algorithm family (Timsort vs dual-pivot).

Production case study (high volume)

Context: Banking ledger / settlement batch and an online ads reporting API both sort tens of millions of rows daily (batch) and multi-million keyed windows online. Why seniors care: Wrong sort stability breaks ledger “equal amount” tie-breaking; boxing to Integer[] flips algorithm and allocates heavily; parallel sort helps throughput but can hurt p99 if it saturates shared ForkJoinPool.commonPool(). Failure / symptom: Non-deterministic order in reconciliation diffs; GC spikes when sorting boxed IDs; latency cliffs when parallelStream().sorted() steals CPU from request threads. Resolution: Keep primitives (long[]) on hot paths; reserve Timsort when stability matters; dedicated FJP for heavy sorts; push huge sorts to Spark/DB ORDER BY + keyset pagination. Seen at / similar to: Stripe/Square settlement-style batches; Meta/Google ads reporting; LinkedIn/Hadoop-era external sort patterns.

Divide and conquer

• Merge, quickselect (expected O(n) selection), closest pair
• Parallelism angle: fork-join friendly vs sequential dependency

Java: No JDK quickselect. Top-K / selection → PriorityQueue of size K, or full sort. Parallel D&C → ForkJoinPool + RecursiveTask / RecursiveAction (work-stealing). Streams parallel() also uses ForkJoinPool.commonPool() — hidden shared pool cost.

Greedy

• Requires proof: exchange argument or stay-ahead
• Classic: interval scheduling, Huffman, Dijkstra (non-negative weights)

Trap: greedy “feels right” but fails — interviewers ask for counterexample.

Java: Often just hand-written logic + PriorityQueue / sorting. No special “greedy framework” in the JDK.

Dynamic programming

• Define state, transition, base, order
• 1D/2D, knapsack variants, LCS/LIS, path counts, interval DP
• Space optimization (rolling arrays); reconstruct solution via parent pointers
• Vs recursion + memo: same asymptotics; stack limits

Java: Bottom-up with int[] / int[][] (primitive arrays beat boxed). Top-down: recursion + HashMap memo or array memo — watch StackOverflowError on deep recursion; prefer iterative or increase stack only as a last resort. Bitmask DP: int/long masks — see bit operators.

Graphs

Must distinguish: Dijkstra fails with negative edges; need Bellman-Ford / Johnson.

Java: No JDK BFS/Dijkstra. Build adjacency with Map + List. BFS: ArrayDeque. Dijkstra: PriorityQueue of (dist, node) (no decrease-key — allow duplicate entries + skip stale). Union-Find: hand-rolled parent/rank arrays (int[]). Topo: Kahn’s algorithm with indegree array + queue.

Production case study (high volume)

Context: Ride-hailing / food-delivery ETA and route graph (city-scale road network, millions of GPS pings/day) plus a social “people you may know” graph job. Why seniors care: Dijkstra on the wrong weight (or negative adjustments) silently wrong ETAs; loading full graph per request blows memory; celebrity nodes create hot partitions in BFS fan-out; recursion DFS on deep graphs → stack overflow in prod, not in unit tests. Failure / symptom: ETA regressions after traffic-weight deploy; worker OOM; job runtime cliffs on dense subgraphs; incorrect topo order → pipeline deadlock in DAG schedulers. Resolution: Precompute / partition graphs (contraction hierarchies / hub labeling patterns); A* with admissible heuristic; explicit stack DFS; shard PYMK by user; treat “algorithm” as a service with SLOs, not a library call inside the request path. Seen at / similar to: Uber/Lyft routing; Google Maps-style ETA; LinkedIn Economic Graph / PYMK; Netflix/Meta DAG schedulers (Airflow/internal) for topo ordering.

String algorithms (senior awareness)

• KMP / Z-algorithm / Rabin-Karp for matching
• Trie for prefixes; suffix array/tree for advanced (often overkill unless domain is search)

Java: String since Java 9 stores a byte[] + coder (Latin-1 compact or UTF-16); immutable; caches hashCode (31 * h + c). StringBuilder = unsynchronized expandable byte[]/char buffer; StringBuffer = synchronized (prefer Builder). substring copies (Java 7u6+). Matching: String.indexOf / contains (simple search); Pattern / Matcher = NFA regex engine (catastrophic backtracking risk on hostile patterns). No JDK KMP/trie — implement or use libraries.

Production case study (high volume)

Context: WAF / API gateway for a public SaaS validates paths and headers with regexes at hundreds of K RPS; log redaction uses Pattern on multi-GB/hour streams. Why seniors care: Catastrophic backtracking is a CPU DoS (ReDoS) — one crafted input pins cores; allocating substring in a parse loop destroys throughput. Failure / symptom: Single request pegs a core; fleet CPU cliff after a “simple” validation regex change; GC from string churn in parsers. Resolution: Linear-time parsers / RE2-style engines where available; fuzz regexes; precompile Pattern; avoid nested quantifiers on user input; move heavy redaction off the request thread. Seen at / similar to: Cloudflare WAF; AWS WAF/API Gateway request validation; GitHub/large SaaS log pipelines.

Problem → approach mapping

Java under the hood (stdlib algorithms)

Correctness habits interviewers reward

1. Examples + edge cases first — empty, single, duplicates, overflow, negative weights
2. Invariants stated before coding
3. Complexity after approach, before deep code
4. Test the mid-point of the idea with a counterexample search if greedy

Systems angle (senior differentiator)

Whiteboard-optimal ≠ production-optimal:

Saying “I’d push this to the database / search index / stream processor” with a clear reason is senior behavior when appropriate — but don’t dodge a requested coding algorithm.

Production case study (high volume)

Context: Streaming analytics for a payments company needs distinct fraud-device counts over 24h windows at millions of events/min; a naive HashSet per window OOMs. Why seniors care: Whiteboard exact algorithms don’t survive cardinality; wrong sketch parameters → compliance/reporting error bands; skew (one merchant) breaks reducers. Failure / symptom: Executor OOM; Spark stage stragglers; “exact” counts disagree across regions. Resolution: HyperLogLog / Count-Min sketches with documented error; salt hot keys; compare sketch vs sampled exact offline; alert on sketch size and error budget. Seen at / similar to: Redis HLL; Datadog/observability cardinality; LinkedIn/Uber stream analytics engineering blogs.

What interviewers probe

1. Derive complexity of your code including hidden costs (hashing, sorting keys, copying).
2. Optimize from O(n²) → better and explain the insight.
3. Follow-ups: concurrent version? streaming version? disk too big?
4. Bug hunt: off-by-one in binary search; mutating while iterating; integer overflow.
5. Trade space for time (and when not to).
6. ReDoS / parallelSort / commonPool production failure modes.

Senior-level expectation: Clear communication under pressure; correct edge cases; ability to adjust approach when constraints change mid-interview — including “approximate at this QPS.”

Pitfalls

• Claiming O(1) hash ops without “average / expected”
• Using Dijkstra on negative weights
• Recursion depth on skewed trees / DFS on deep graphs
• Sorting when a linear pass or counting sort suffices
• Premature micro-optimization before clarifying constraints (n, memory, realtime?)
• Assuming Arrays.sort is always TimSort (primitives ≠ objects)
• Exact-in-memory algorithms for multi-million-event streams without sketches/external sort
• Hosting heavy parallelStream work on the same FJP as request handling

Cross-references

• Data structures
• Bit operators — bitmask DP
• CPU architecture — constants, cache effects on “fast” algorithms