How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Airbnb during technical interviews.

Minimize exact layover bookings | Airbnb Coding Question

Minimize exact layover bookings

Company: Airbnb

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a layover length `X` in hours and a list of available experience durations, where every value has exactly one decimal place. You want to spend exactly `X` hours on booked experiences. Rules: - You may book the same experience multiple times. - The total booked duration must equal `X` exactly. - Among all exact combinations, return the minimum number of bookings. - If no exact combination exists, return `0`. Example: - `durations = [3.0, 2.0]` - `X = 7.0` - Output: `3`, because `2.0 + 2.0 + 3.0 = 7.0` Explain your approach and handle decimal precision robustly.

Quick Answer: This question evaluates algorithmic problem-solving and numeric precision handling, specifically the ability to model exact-duration sums and minimize the number of bookings under strict equality constraints.

You are given a layover length X in hours and a list of available experience durations. Every duration and X has exactly one decimal place. You may book any experience multiple times. Find the minimum number of bookings needed so that the total booked duration is exactly X hours. If no exact combination exists, return 0. Because the values are decimal numbers, your implementation should avoid direct floating-point equality checks and handle precision robustly.

Constraints

0 <= len(durations) <= 200
0.0 <= X <= 1000.0
Each duration is greater than 0 and has exactly one decimal place
You may reuse any duration an unlimited number of times

Examples

Input: ([3.0, 2.0], 7.0)

Expected Output: 3

Explanation: Book durations 2.0, 2.0, and 3.0 to reach exactly 7.0 hours with 3 bookings.

Input: ([1.0, 3.0, 4.0], 6.0)

Expected Output: 2

Explanation: The best exact combination is 3.0 + 3.0 = 6.0, which uses 2 bookings.

Input: ([0.1, 0.2, 0.5], 0.7)

Expected Output: 2

Explanation: Using 0.2 + 0.5 reaches 0.7 exactly with only 2 bookings. This case checks decimal precision handling.

Input: ([2.2, 4.4], 3.3)

Expected Output: 0

Explanation: No combination of 2.2 and 4.4 can add up to exactly 3.3.

Input: ([], 5.0)

Expected Output: 0

Explanation: With no available experiences, it is impossible to reach 5.0 hours.

Input: ([2.5], 0.0)

Expected Output: 0

Explanation: A target of 0.0 hours requires no bookings, so the minimum is 0.

Input: ([2.5], 5.0)

Expected Output: 2

Explanation: Booking the 2.5-hour experience twice gives exactly 5.0 hours.

Hints

Since every value has exactly one decimal place, convert hours into integer tenths by multiplying by 10 before doing any comparisons.
After scaling, this becomes an unbounded minimum coin change problem: reach the exact target using the fewest items.

Quick Overview

This question evaluates algorithmic problem-solving and numeric precision handling, specifically the ability to model exact-duration sums and minimize the number of bookings under strict equality constraints.