DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Dynamic Programming Interview Problems

Master essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.

Problem-Solving Framework

For any DP problem in an interview:

Identify it is DP: Optimal value? Count ways? Has overlapping subproblems?
Define the state: What changes between subproblems?
Write the recurrence: How do states relate?
Determine base cases: What are trivial answers?
Choose approach: Memoization (easier to code) or tabulation (better space)?

Problem 1: Coin Change (Minimum Coins)

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount. You have infinite supply of each coin.

State: dp[amount] = minimum coins needed to make amount Transition: dp[a] = min(dp[a - coin] + 1) for each valid coin Base: dp[0] = 0 (zero coins for amount 0)

Example

def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for a in range(1, amount + 1): for coin in coins: if coin <= a and dp[a - coin] != float('inf'): dp[a] = min(dp[a], dp[a - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 # Example: coins=[1,5,10], amount=12 → 3 (10+1+1) print(coin_change([1, 5, 10], 12)) # 3

Time: O(amount × len(coins)), Space: O(amount)

Problem 2: Edit Distance (Levenshtein Distance)

Problem: Find minimum operations (insert, delete, replace) to transform word1 into word2.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1] Transition:

Characters match: dp[i][j] = dp[i-1][j-1]
Replace: dp[i-1][j-1] + 1
Delete from word1: dp[i-1][j] + 1
Insert into word1: dp[i][j-1] + 1

Example

def edit_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # Base cases for i in range(m + 1): dp[i][0] = i # Delete all for j in range(n + 1): dp[0][j] = j # Insert all for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j-1], # replace dp[i-1][j], # delete dp[i][j-1]) # insert return dp[m][n] print(edit_distance("horse", "ros")) # 3

Time: O(m×n), Space: O(m×n), optimizable to O(n)

Problem 3: Rod Cutting

Problem: Given a rod of length n and prices for each length, find maximum revenue from cutting.

State: dp[i] = maximum revenue from rod of length i

Example

def rod_cutting(prices, n): """prices[i] = price for rod of length i+1.""" dp = [0] * (n + 1) for length in range(1, n + 1): for cut in range(1, length + 1): dp[length] = max(dp[length], prices[cut-1] + dp[length - cut]) return dp[n] # prices[0]=1, prices[1]=5, prices[2]=8, prices[3]=9 print(rod_cutting([1, 5, 8, 9], 4)) # 10 (two pieces of length 2)

Time: O(n²), Space: O(n)

Problem 4: Climbing Stairs (Ways to Reach Top)

Problem: You can climb 1 or 2 steps. Count distinct ways to reach step n.

python example

def climb_stairs(n):
    if n <= 2: return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

print(climb_stairs(5))  # 8

This is Fibonacci in disguise! Time: O(n), Space: O(1)

Problem 5: House Robber

Problem: You cannot rob two adjacent houses. Maximize total money robbed.

State: dp[i] = max money from houses 0..i Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip or rob house i)

Example

def house_robber(nums): if not nums: return 0 if len(nums) == 1: return nums[0] prev2, prev1 = 0, 0 for num in nums: curr = max(prev1, prev2 + num) prev2, prev1 = prev1, curr return prev1 print(house_robber([2, 7, 9, 3, 1])) # 12 (rob houses 0, 2, 4: 2+9+1=12)

Time: O(n), Space: O(1)

House Robber II (Circular)

Houses are in a circle (first and last are adjacent). Solution: max(rob houses 0..n-2, rob houses 1..n-1).

Example

def house_robber_circular(nums): if len(nums) == 1: return nums[0] return max(house_robber(nums[:-1]), house_robber(nums[1:]))

Problem 6: Word Break

Problem: Can string s be segmented into dictionary words?

Example

def word_break(s, word_dict): n = len(s) dp = [False] * (n + 1) dp[0] = True # Empty string is always valid word_set = set(word_dict) for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n] print(word_break("leetcode", ["leet", "code"])) # True

Time: O(n² × k) where k is average word length for substring comparison

Problem 7: Decode Ways

Problem: A message of digits. '1' → A, '2' → B, ..., '26' → Z. Count valid decodings.

Example

def num_decodings(s): if not s or s[0] == '0': return 0 n = len(s) dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): # Single digit (1-9) if s[i-1] != '0': dp[i] += dp[i-1] # Two digits (10-26) two_digit = int(s[i-2:i]) if 10 <= two_digit <= 26: dp[i] += dp[i-2] return dp[n] print(num_decodings("226")) # 3: "BZ", "VF", "BBF"

Problem 8: Maximum Subarray (Kadane\'s Algorithm)

Example

def max_subarray(nums): max_sum = curr_sum = nums[0] for num in nums[1:]: curr_sum = max(num, curr_sum + num) max_sum = max(max_sum, curr_sum) return max_sum print(max_subarray([-2,1,-3,4,-1,2,1,-5,4])) # 6 ([4,-1,2,1])

Problem 9: Unique Paths in Grid

Example

def unique_paths(m, n): dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[n-1]

Problem 10: Partition Equal Subset Sum

Problem: Can array be partitioned into two subsets with equal sum?

Example

def can_partition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[target]

This is a subset sum problem (special case of 0/1 knapsack).

Pattern Recognition Cheat Sheet

If the problem asks...	Think...	Pattern
Min/max with choices	DP with optimal substructure	Knapsack / Interval DP
Count ways	DP with additive recurrence	Climbing stairs / Coin change
Can it be done?	DP with boolean states	Subset sum / Word break
Optimal partitioning	Interval DP	MCM / Palindrome partition
Sequence optimization	1D/2D DP	LIS / LCS / Edit distance
Grid paths	2D DP	Unique paths / Min path sum
No adjacent constraint	Linear DP	House robber

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Dynamic Programming Interview Problems.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, dynamic, programming, interview

Related Data Structures & Algorithms Topics

Continue learning this concept

Dynamic ProgrammingDynamic Programming FundamentalsUnderstand the core principles of dynamic programming: overlapping subproblems, optimal substructure, and how DP differs from divide-and-conquer and greedy approaches.Dynamic ProgrammingFibonacci with Dynamic ProgrammingSee how DP transforms Fibonacci from exponential O(2^n) naive recursion to O(n) memoization, O(n) tabulation, and O(1) space-optimized solution.Dynamic Programming0/1 Knapsack ProblemMaster the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.Dynamic ProgrammingLongest Common Subsequence (LCS)Master the LCS problem with 2D DP table construction, backtracking for the actual subsequence, and its application in diff utilities.Dynamic ProgrammingLongest Increasing Subsequence (LIS)Solve LIS with O(n\u00b2) DP approach and the optimal O(n log n) patience sorting algorithm, with complete analysis and code.Dynamic ProgrammingMatrix Chain MultiplicationMaster the matrix chain multiplication problem with optimal parenthesization, gap-based DP table filling, and complete implementation.

PreviousTail Recursion - Optimization Technique NextDynamic Programming Fundamentals

DSA Notes

Dynamic Programming Interview Problems

Master essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.

Problem-Solving Framework

For any DP problem in an interview:

Identify it is DP: Optimal value? Count ways? Has overlapping subproblems?
Define the state: What changes between subproblems?
Write the recurrence: How do states relate?
Determine base cases: What are trivial answers?
Choose approach: Memoization (easier to code) or tabulation (better space)?

Problem 1: Coin Change (Minimum Coins)

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount. You have infinite supply of each coin.

State: dp[amount] = minimum coins needed to make amount Transition: dp[a] = min(dp[a - coin] + 1) for each valid coin Base: dp[0] = 0 (zero coins for amount 0)

Example

Time: O(amount × len(coins)), Space: O(amount)

Problem 2: Edit Distance (Levenshtein Distance)

Problem: Find minimum operations (insert, delete, replace) to transform word1 into word2.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1] Transition:

Characters match: dp[i][j] = dp[i-1][j-1]
Replace: dp[i-1][j-1] + 1
Delete from word1: dp[i-1][j] + 1
Insert into word1: dp[i][j-1] + 1

Example

Time: O(m×n), Space: O(m×n), optimizable to O(n)

Problem 3: Rod Cutting

Problem: Given a rod of length n and prices for each length, find maximum revenue from cutting.

State: dp[i] = maximum revenue from rod of length i

Example

Time: O(n²), Space: O(n)

Problem 4: Climbing Stairs (Ways to Reach Top)

Problem: You can climb 1 or 2 steps. Count distinct ways to reach step n.

python example

def climb_stairs(n):
    if n <= 2: return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

print(climb_stairs(5))  # 8

This is Fibonacci in disguise! Time: O(n), Space: O(1)

Problem 5: House Robber

Problem: You cannot rob two adjacent houses. Maximize total money robbed.

State: dp[i] = max money from houses 0..i Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip or rob house i)

Example

Time: O(n), Space: O(1)

House Robber II (Circular)

Houses are in a circle (first and last are adjacent). Solution: max(rob houses 0..n-2, rob houses 1..n-1).

Example

def house_robber_circular(nums): if len(nums) == 1: return nums[0] return max(house_robber(nums[:-1]), house_robber(nums[1:]))

Problem 6: Word Break

Problem: Can string s be segmented into dictionary words?

Example

Time: O(n² × k) where k is average word length for substring comparison

Problem 7: Decode Ways

Problem: A message of digits. '1' → A, '2' → B, ..., '26' → Z. Count valid decodings.

Example

Problem 8: Maximum Subarray (Kadane\'s Algorithm)

Example

Problem 9: Unique Paths in Grid

Example

def unique_paths(m, n): dp = [1] * n for _ in range(1, m): for j in range(1, n): dp[j] += dp[j-1] return dp[n-1]

Problem 10: Partition Equal Subset Sum

Problem: Can array be partitioned into two subsets with equal sum?

Example

This is a subset sum problem (special case of 0/1 knapsack).

Pattern Recognition Cheat Sheet

If the problem asks...	Think...	Pattern
Min/max with choices	DP with optimal substructure	Knapsack / Interval DP
Count ways	DP with additive recurrence	Climbing stairs / Coin change
Can it be done?	DP with boolean states	Subset sum / Word break
Optimal partitioning	Interval DP	MCM / Palindrome partition
Sequence optimization	1D/2D DP	LIS / LCS / Edit distance
Grid paths	2D DP	Unique paths / Min path sum
No adjacent constraint	Linear DP	House robber

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Dynamic Programming Interview Problems.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, dynamic, programming, interview

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousTail Recursion - Optimization Technique NextDynamic Programming Fundamentals