Red Marbles, Blue Marbles
Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the […]
Brain Teasers, Data Structures, Dynamic Programming, Logic Puzzles
← Tech Interview
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
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,