14 articles
Master LeetCode 1976 Number of Ways to Arrive at Destination: extend Dijkstra to count the number of distinct shortest paths simultaneously, returning the count modulo 10^9+7. A FAANG-favourite shortest-path counting interview question asked at Google, Amazon, and Meta.
Find the length of the longest strictly increasing subsequence in O(n log n) using patience sorting — a binary search on a maintained tails array that is simpler and faster than classic DP.
LeetCode 338 Counting Bits: compute popcount for every integer 0..n in O(n). Master the elegant DP recurrence dp[i] = dp[i >> 1] + (i & 1) that FAANG interviewers love.
The complete 1D Dynamic Programming roadmap for FAANG interviews — Fibonacci, House Robber, Kadane, Coin Change, LIS, Jump Game, Decode Ways, and Palindrome patterns with Python and JavaScript templates.
The full 1D Dynamic Programming cheatsheet for FAANG interviews — eight pattern transitions, knapsack loop directions, LIS patience sort, and the complete problem index in one place.
The complete 2D Dynamic Programming roadmap for FAANG interviews — LCS, Edit Distance, grid path counting, interval DP, stock state machines, and 2D knapsack with Python and JavaScript templates.
The full 2D Dynamic Programming cheatsheet for FAANG interviews — seven pattern transitions, stock state machine, interval DP template, LCS reconstruction, and the complete problem index.
Maximise score jumping through an array where each jump covers 1 to k steps. Combine DP with a monotonic deque to find the sliding window maximum of recent DP values in O(n) time.
Solve probability DP problems used by quantitative interviews. Master expected value recurrences, geometric distribution, knight probability, and the soup servings memoization trick.
Solve LeetCode 85 Maximal Rectangle in O(m times n) by reducing each row to a histogram and applying the monotonic stack. A FAANG hard interview classic.
Find the longest contiguous substring shared by two strings. The DP solution is O(n*m), binary search plus rolling hash gives O((n+m) log min(n,m)) expected, and suffix array plus LCP achieves O((n+m) log(n+m)).
The four canonical string DP problems — edit distance, longest common subsequence, interleaving strings, and regular expression matching — share a common 2D state structure. Master the family and you cover 80 percent of FAANG string DP questions.
LC 337 House Robber III extends the classic House Robber DP to a binary tree where adjacent nodes cannot both be robbed. The optimal O(n) solution uses post-order DFS returning a (rob, skip) pair — a fundamental tree DP pattern tested at Amazon and Microsoft.
LC 1483 Kth Ancestor of a Tree Node answers each query in O(log k) after O(n log n) preprocessing using binary lifting — a sparse table DP technique that also powers LCA algorithms and is commonly tested at Amazon.