Katkat
Back

Determine Exact Layover Booking

AirbnbSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Determine if a subset of layover activities can be booked such that their total cost exactly matches a target voucher balance, handling floating-point currency without precision loss.

Problem Statement

Airbnb offers curated day experiences for travelers on long layovers. A traveler has received a promotional voucher with an exact monetary value voucher_amount (e.g., "45.50"). The terms of the voucher require that the total cost of the booked activities equals the voucher value exactly, and each activity can be booked at most once.

You are given a list of available activities, where each activity is represented as a tuple (name, price). The price and voucher amount are given as strings formatted with up to two decimal places representing dollars and cents.

Write a function find_exact_layover_booking(activities, voucher_amount) that returns a list of activity names that sum exactly to the voucher amount. If multiple valid combinations exist, return any one of them. If no combination matches the exact voucher amount, return an empty list [].

Function Signature

def find_exact_layover_booking(activities: list[tuple[str, str]], voucher_amount: str) -> list[str]:
    pass

Input

  • activities: A list of tuples (name, price) where name is a unique non-empty string and price is a string representing a non-negative decimal currency value (e.g., "12.75", "5", "0.50").
  • voucher_amount: A string representing the non-negative decimal voucher target.

Output

  • A list of activity names (list[str]) whose prices sum exactly to voucher_amount, or [] if no such combination exists.

Constraints

  • 0 <= len(activities) <= 40
  • 0.00 <= float(voucher_amount) <= 500.00
  • Activity prices have at most 2 decimal digits.
  • Direct floating-point arithmetic (e.g., float("0.1") + float("0.2")) may introduce precision errors and should be avoided.

Examples

Example 1:

activities = [
    ("City Bike Tour", "25.50"),
    ("Museum Pass", "15.00"),
    ("Food Tasting", "20.00"),
    ("Airport Lounge", "30.50")
]
voucher_amount = "45.50"

# Output: ["City Bike Tour", "Food Tasting"]
# Explanation: 25.50 + 20.00 = 45.50.

Example 2:

activities = [
    ("Spa Access", "40.00"),
    ("Walking Tour", "15.25"),
    ("Coffee Roasting", "12.50")
]
voucher_amount = "50.00"

# Output: []
# Explanation: No combination of activities sums exactly to 50.00.

Edge Cases

  • voucher_amount is "0.00": An empty list [] is a valid sum of zero items.
  • Single activity matches the voucher exactly.
  • All activities together do not reach the voucher amount.

Hints

Hint 1

Avoid floating-point arithmetic errors by converting all currency strings into integer cents before performing calculations.

Hint 2

Formulate the task as a 0/1 knapsack (subset sum) problem where the target capacity is the voucher amount in cents.

Hint 3

Since the target capacity in cents is at most 50,000, you can use dynamic programming with a hash map or array to track reachable sums and reconstruct the chosen items.

Follow-up questions

  • How would you modify your solution if each activity could be booked an unlimited number of times instead of at most once?
  • If the voucher amount was in the millions (ruling out pseudo-polynomial DP) but the number of activities remained around 40, what algorithmic approach would you use?
  • How would you return the combination that maximizes the total rating or popularity if each activity also came with a customer score?