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.
Algorithms, Dynamic Programming, String Manipulation
Longest palindrome in a string
Write a function to find the longest palindrome in a string.
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.
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
Brain Teasers, Dynamic Programming
X Implies Y
Part I (you can’t use paper, you have to figure it out in your head) i have a black triangle,