Data Structures & Algorithms Interview Questions and Answers

DP solves problems with overlapping subproblems and optimal substructure by storing results and reusing them. Two styles:

• Top-down memoisation: recursion plus a cache, easy to write from the recurrence.
• Bottom-up tabulation: fill a table iteratively, avoids recursion depth issues.

# Fibonacci, bottom-up, O(n) time O(1) space
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# 0/1 knapsack, O(n * capacity)
def knapsack(items, cap):
    dp = [0] * (cap + 1)
    for weight, value in items:
        for c in range(cap, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[cap]

Signals: count ways, min/max cost, "can you reach", subsequence problems. State definition and transition are the key interview skills.