0/1 Knapsack Problem: DP Solution with Space Optimization
The 0/1 Knapsack problem is one of the most important DP patterns. Unlike coin change (unbounded knapsack), each item can […]
Dynamic Programming
Dynamic Programming
Dynamic Programming (DP) is one of the most challenging yet rewarding topics in technical interviews. Master the art of breaking problems into overlapping subproblems and building optimal solutions from the bottom up.
Core Concepts:
Memoization: Top-down recursive approach with caching
Tabulation: Bottom-up iterative approach
State definition: Identifying what to store in DP table
Recurrence relation: Mathematical formula for subproblems
Common Patterns:
0/1 Knapsack and variations
Longest Common Subsequence (LCS)
Edit distance and string matching
Matrix chain multiplication
Subset sum and partition problems
When to Use DP:
Problem has optimal substructure
Overlapping subproblems exist
Need to find optimal value (min/max)
Counting possibilities or combinations
Difficulty: Medium to Hard. Practice 20-30 problems to build pattern recognition.
Dynamic Programming
Longest Common Subsequence: DP Solution and Space Optimization
Longest Common Subsequence (LCS) is a fundamental string DP problem that appears in interviews at Google, Microsoft, and Amazon —
Dynamic Programming
Edit Distance (Levenshtein): DP Solution Explained
Edit Distance (Levenshtein Distance) is a classic string DP problem that appears in interviews at Google, Microsoft, and Dropbox. It’s
Dynamic Programming
Word Break Problem: Dynamic Programming Solution
Word Break (LeetCode 139) is a string DP problem that tests whether you can partition a string using a given
Dynamic Programming
Coin Change: Bottom-Up and Top-Down Dynamic Programming
Coin Change (LeetCode 322) is the canonical dynamic programming problem. It tests your ability to identify optimal substructure, choose between
Algorithms, Array, Dynamic Programming, Greedy
Kadane’s Algorithm: Maximum Subarray Sum
System Design Questions System Design: IoT Platform (Connected Devices at Scale) SRE and DevOps Interview Questions: SLOs, On-Call, and Incident
Algorithms, Dynamic Programming, String Manipulation
Longest palindrome in a string
Write a function to find the longest palindrome in a string. 2026 Update: Longest Palindrome — Character Frequency Approach There
Dynamic Programming, Math Problems
Prime number problem
You need to a number of floors in a building. There are 68 floors (numbered 1 to 64). Conditions: 1.
Dynamic Programming
Fruit Jar Problem
You have 3 jars that are all mislabeled. One jar contains Apple, another contains Oranges and the third jar contains
Algorithms, Dynamic Programming, String Manipulation
Find Longest Palindrome In A String
How will you find out the longest palindrome in a given string. 2026 Update: Longest Palindromic Substring — Expand Around
Data Structures, Dynamic Programming
How many floors can an egg be dropped without breaking?
Question: You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum
Brain Teasers, Data Structures, Dynamic Programming, Logic Puzzles
Red Marbles, Blue Marbles
Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the
Algorithms, Dynamic Programming, Logic Puzzles, String Manipulation
Palindromes
Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).10/02/2001when
Algorithms, Arrays, Dynamic Programming, Google Interview Questions, System Design
Webloggers
Five webloggers – joshua Allen, meg Hourihan, jason Kottke, robert Scoble, and joel Spolsky – were competing for karma points