← Airbnb Interview InsightsMachine Learning Engineer

Airbnb·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Airbnb ML engineer interview with a coding problem that's basically coin change dressed up in a travel scenario. Cute theming, but the float arithmetic gotcha is what separates people who've seen this before from people who haven't.

Questions Asked (1)

Q1

You have an X-hour layover in Paris and want to fill it exactly with Airbnb experiences. Given a list of experience durations (in hours, one decimal place), and the ability to book the same experience multiple times, find the minimum number of bookings that sum to exactly X hours. Return -1 if it's impossible.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

So it's unbounded coin change, minimum coins, but with decimal values instead of integers.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as the unbounded coin change problem where you need the minimum number of coins (experiences) to sum to a target (X hours). Use dynamic programming with a 1D array of size X+1, where dp[i] represents the minimum bookings to reach exactly i hours. Initialize dp[0]=0 and dp[i]=infinity for i>0, then for each experience duration, update dp[i] = min(dp[i], dp[i - duration] + 1) for i from duration to X.

Pro tip: Since durations are in hours with one decimal place, multiply all durations and X by 10 to convert to integers, avoiding floating-point precision issues. Also, clarify that experiences can be booked multiple times, which makes this the unbounded variant.

1. Clarify the problem

Confirm that experiences can be reused unlimited times and that we need the minimum number of bookings to sum exactly to X hours. Ask about constraints on X and the number of experiences to choose the appropriate algorithm.

2. Choose the algorithm

Identify this as the unbounded coin change problem and select dynamic programming as the optimal approach. Discuss time and space complexity: O(n*X) time and O(X) space, where n is the number of experiences.

3. Handle precision

Convert all durations and X to integers by multiplying by 10 to avoid floating-point errors. This ensures exact arithmetic and simplifies the DP implementation.

4. Implement DP

Initialize a DP array of size X+1 with infinity, set dp[0]=0, and iterate through each experience duration, updating dp[i] for i from duration to X. After processing, return dp[X] if it's not infinity, else -1.

5. Test and optimize

Test with edge cases like X=0, impossible sums, and large X. Mention potential optimizations like BFS for unweighted graphs or pruning if needed, but note DP is standard.

Key Points to Mention

  • This is the unbounded coin change problem (minimum coins to make a sum).
  • Dynamic programming with a 1D array gives O(n*X) time and O(X) space.
  • Multiply durations and X by 10 to avoid floating-point precision issues.
  • Initialize dp[0]=0 and dp[i]=infinity for i>0, then update dp[i] = min(dp[i], dp[i - duration] + 1).
  • Return -1 if dp[X] remains infinity, indicating it's impossible.
  • Consider edge cases: X=0 (return 0), no experiences, or durations larger than X.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.