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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

What role is this question designed for?

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

Find hotel pairs to cover a split stay

Q: Find hotel pairs to cover a split stay

This question evaluates reasoning about interval coverage, set membership, combinatorial pairing of resources, and efficient processing of unsorted availability lists, reflecting skills in algorithm design and use of appropriate data structures.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are implementing a simplified “split stay” feature. ## Problem You are given: - `n` hotels (or listings), indexed `0..n-1`. - For each hotel `i`, an **unsorted** list `avail[i]` of integer dates (e.g., days since epoch) indicating the dates that hotel is available. - A requested inclusive date range `[start_date, end_date]`. A **split stay** means the guest stays in **two different hotels** in two **contiguous, non-empty** segments that exactly cover the requested range: - Choose a split point `s` such that `start_date ≤ s < end_date`. - Hotel `A` must be available for **every date** in `[start_date, s]`. - Hotel `B` must be available for **every date** in `[s+1, end_date]`. - The stay is “forward only”: the first segment is earlier than the second; no interleaving/overlap beyond the shared boundary between `s` and `s+1`. - Hotels must be different: `A != B`. ## Output Return **all distinct valid combinations** as tuples: `(A, B, s)` meaning hotel `A` covers the left segment `[start_date, s]` and hotel `B` covers the right segment `[s+1, end_date]`. Notes: - If `avail[i]` contains duplicates, they should not create duplicate output tuples. - If no split stay is possible, return an empty list. ## Example (informal) If `[start_date, end_date] = [10, 13]` and a split `s=11` is chosen, then hotel `A` must cover dates `{10,11}` and hotel `B` must cover `{12,13}`.

Quick Answer: This question evaluates reasoning about interval coverage, set membership, combinatorial pairing of resources, and efficient processing of unsorted availability lists, reflecting skills in algorithm design and use of appropriate data structures.

You are implementing a simplified split-stay feature. You are given `n` hotels, indexed `0..n-1`. For each hotel `i`, `avail[i]` is an unsorted list of integer dates on which that hotel is available. You are also given an inclusive requested date range `[start_date, end_date]`. A valid split stay uses exactly two different hotels and exactly one split point `s` such that `start_date <= s < end_date`: - Hotel `A` covers every date in `[start_date, s]` - Hotel `B` covers every date in `[s+1, end_date]` - Both segments must be non-empty - `A != B` Return all distinct valid tuples `(A, B, s)`, where hotel `A` covers the left segment and hotel `B` covers the right segment. Important details: - `avail[i]` may be unsorted and may contain duplicates. - Duplicates in `avail[i]` must not create duplicate output tuples. - Return the result sorted by split point `s` ascending, then by `A` ascending, then by `B` ascending. - If no valid split stay exists, return an empty list.

Constraints

1 <= len(avail) <= 2000
0 <= sum(len(hotel_dates) for hotel_dates in avail) <= 2 * 10^5
-10^9 <= each date <= 10^9
start_date <= end_date
0 <= end_date - start_date <= 2000
The total number of valid output tuples fits in memory

Examples

Input: ([[10, 11], [12, 13], [10, 11, 12], [11, 12, 13]], 10, 13)

Expected Output: [(0, 3, 10), (2, 3, 10), (0, 1, 11), (0, 3, 11), (2, 1, 11), (2, 3, 11), (2, 1, 12), (2, 3, 12)]

Explanation: There are three possible split points: 10, 11, and 12. For each split, combine hotels that fully cover the left prefix with hotels that fully cover the right suffix, excluding pairs using the same hotel.

Input: ([[5, 4, 4, 6], [7, 6, 6], [5, 6, 7], [4, 5]], 5, 7)

Expected Output: [(0, 1, 5), (0, 2, 5), (2, 1, 5), (3, 1, 5), (3, 2, 5), (0, 1, 6), (0, 2, 6), (2, 1, 6)]

Explanation: The availability lists are unsorted and contain duplicates, but duplicates should not change the result. The valid splits are `s=5` and `s=6`.

Input: ([[-2, -1, 0], [1, 0], [-2, -1], [0, 1]], -2, 1)

Expected Output: [(0, 1, -1), (0, 3, -1), (2, 1, -1), (2, 3, -1), (0, 1, 0), (0, 3, 0)]

Explanation: This checks that negative dates work correctly. Split `s=-2` is impossible, while `s=-1` and `s=0` both produce valid hotel pairs.

Input: ([[1, 3], [2, 4], [1, 2], [4]], 1, 4)

Expected Output: []

Explanation: No pair of different hotels can cover two contiguous non-empty segments that exactly span dates 1 through 4.

Input: ([[10], [10, 11]], 10, 10)

Expected Output: []

Explanation: The requested range has only one date, so it cannot be split into two non-empty contiguous segments.

Hints

For each hotel, you do not need every possible split explicitly. It is enough to know how far it can continuously cover starting from `start_date`, and how early it can continuously cover backward from `end_date`.
Once you know which hotels can cover the left side and which can cover the right side for a split `s`, generate all pairs except those where the two hotel indices are the same.

Quick Overview

This question evaluates reasoning about interval coverage, set membership, combinatorial pairing of resources, and efficient processing of unsorted availability lists, reflecting skills in algorithm design and use of appropriate data structures.