Dynamic Programming Questions at Airbnb: What to Expect

Dynamic Programming (DP) is a critical skill for Airbnb technical interviews because it tests a candidate's ability to optimize complex, real-world problems. At Airbnb, engineering work often involves optimizing for constraints—whether it's pricing algorithms, search ranking, or resource scheduling. DP questions assess your problem-solving rigor and ability to break down a problem into overlapping subproblems, which mirrors the process of designing efficient, scalable systems. With 10 out of their 64 cataloged questions being DP, it's a pattern you cannot afford to overlook.

What to Expect — Types of Problems

Airbnb's DP questions tend to focus on practical optimization scenarios rather than purely academic puzzles. You can generally expect two categories:

1. Classic DP Variations: Problems that are adaptations of well-known DP patterns. For example, you might encounter a problem about maximizing the value of bookings (a variant of the "House Robber" problem) or finding the cheapest flight itinerary with constraints (a variant of "Cheapest Flights Within K Stops").
2. String/Path Optimization: Problems involving string manipulation or pathfinding on a grid. These test your ability to define a state (e.g., dp[i][j]) and find an optimal transition, such as calculating edit distance or counting unique paths with obstacles.

The problems often include a narrative about travel, stays, or listings, but the core DP structure underneath will be familiar if you've practiced the fundamentals.

How to Prepare — Study Tips with One Code Example

Start by mastering the core DP patterns: Fibonacci-style, 0/1 Knapsack, Longest Common Subsequence (LCS), and matrix path problems. Understand the difference between top-down (memoization) and bottom-up (tabulation) approaches. For Airbnb, ensure you can clearly explain your state definition and transition function.

A fundamental pattern to know is the "House Robber" problem, which models choosing non-adjacent elements for maximum sum—analogous to selecting non-conflicting bookings. Here is the bottom-up solution:

def rob(nums):
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

Recommended Practice Order

1. Foundation: Solve core problems on Fibonacci, Climbing Stairs, and the House Robber series. Build intuition for state and recurrence.
2. Core Patterns: Practice 0/1 Knapsack, Unbounded Knapsack (Coin Change), Longest Increasing Subsequence, and Longest Common Subsequence.
3. 2D DP: Move to matrix problems like Unique Paths and Minimum Path Sum.
4. Airbnb-Specific: Finally, tackle the tagged Airbnb DP questions. This sequenced approach ensures you recognize the underlying pattern when faced with a novel problem narrative.

Practice Dynamic Programming at Airbnb