Red Marbles, Blue Marbles
4 min read Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the […] Read article
Brain Teasers, Data Structures, Dynamic Programming, Logic Puzzles
← techinterview
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, Logic Puzzles, String Manipulation
Palindromes
3 min read Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).10/02/2001when Read article
Algorithms, Arrays, Dynamic Programming, Google Interview Questions, System Design
Webloggers
4 min read Five webloggers – joshua Allen, meg Hourihan, jason Kottke, robert Scoble, and joel Spolsky – were competing for karma points Read article
Dynamic Programming
Hen
2 min read If a hen and a half lay an egg and a half in a day and a half, how many Read article
Brain Teasers, Dynamic Programming
X Implies Y
3 min read Part I (you can’t use paper, you have to figure it out in your head) i have a black triangle, Read article