Adobe-style coding patterns: DP, graphs, parsing, backtracking, stacks/heaps

What's being tested

Candidates must demonstrate mastery of core algorithmic patterns—especially dynamic programming, graph traversal, parsing, backtracking, and stack/heap techniques—applied to real coding problems. Interviewers are probing pattern recognition, correct complexity reasoning, and clean, testable implementations (correctness under edge cases and large inputs).

Patterns & templates

• Top-down DP (memoized recursion) — use dfs(state) with memo[state]; clear base cases; time ≈ number of states × transition cost, space = recursion depth + memo.

• Bottom-up DP (tabulation) — fill table iteratively; often reduces recursion overhead; prefer when states are enumerable; watch initialization edges.

• Graph traversal — dfs for component/ordering, bfs for shortest unweighted paths; detect cycles with color array (0/1/2) or onStack.

• Topological sort + DP on DAG — compute indegree, queue, then relax edges for longest/shortest path in DAG in O(V+E).

• Backtracking with pruning — generate candidates, reject early using bounds; apply ordering heuristics and memoization to avoid recomputation.

• Parsing with stacks — use stack for matching tokens/parentheses or evaluate expression via two-stack shunting-yard; be explicit about operator precedence.

• Heaps for order-statistics — maintain min-heap/max-heap for k-largest/smallest sliding windows; operations O(log k).

• Two-pointer / sliding window — for contiguous-subarray constraints; maintain invariant and update aggregate in O(1) per step.

Common pitfalls

Pitfall: Overlooking integer overflow on counts or sums; use 64-bit types and validate constraints early.

Pitfall: Returning early in DFS without marking visited leads to infinite recursion or revisits; always mark before recursing when appropriate.

Pitfall: Choosing naive exponential backtracking without pruning or memoization — explain why pruning bounds or DP memo reduce to polynomial in many practical cases.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.