Adobe-style coding patterns: DP, graphs, parsing, backtracking, stacks/heaps
Asked of: Software Engineer
Last updated
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)withmemo[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 —
dfsfor component/ordering,bfsfor shortest unweighted paths; detect cycles with color array (0/1/2) oronStack. -
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-heapfor 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.
Related concepts
- Arrays, Sliding Windows, DP And Stack PatternsCoding & Algorithms
- Arrays, Strings, Hash Maps, And Frequency CountingCoding & Algorithms
- Coding, Data Structures, And Parsing
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms
- Core Data Structures, Algorithms, And ComplexityCoding & Algorithms
- Dynamic Programming And Combinatorial CountingCoding & Algorithms