Find valid split-stay listing combinations
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are building a feature that suggests a **split stay**: a guest stays in one home for the first part of a trip, then switches to a second home for the remainder.
You are given:
- A map `availability` from **listing name** (e.g., "A", "B") to a list of **available day numbers** (integers).
- A requested **date range** `[startDay, endDay]` inclusive.
Return **all valid split-stay options**:
1) **Single-listing stay**: any listing that is available for **every day** in `[startDay, endDay]`.
2) **Two-listing split stay**: any ordered pair `(L1, L2)` for which there exists a split day `k` with `startDay <= k < endDay` such that:
- `L1` is available for every day in `[startDay, k]`, and
- `L2` is available for every day in `[k+1, endDay]`.
Notes / clarifications:
- Availability is per-day; treat it as a set (duplicates don’t matter).
- A listing may appear in at most one position within a split option (i.e., `L1 != L2`).
- Output can be in any order; avoid duplicates.
Example:
- `A = [1,2,3,6,7,10,11]`
- `B = [3,4,5,6,8,9,10,13]`
- `C = [7,8,9,10,11]`
- Query range: `[3, 11]`
Determine which single listings and/or two-listing split stays satisfy the rules above.
Quick Answer: This question evaluates a candidate's ability to manipulate intervals and set-based availability data, reason about contiguous date ranges, and enumerate valid single-listing and ordered two-listing split combinations.
You are given a dictionary `availability` where each key is a listing name and each value is a list of available day numbers. You are also given `startDay` and `endDay` for a requested trip, inclusive. Return all valid stay options in the form `{'single_stays': [...], 'split_stays': [...]}`. A single stay is any listing available for every day in `[startDay, endDay]`. A split stay is any ordered pair `[L1, L2]` with `L1 != L2` such that there exists a split day `k` where `startDay <= k < endDay`, `L1` is available for every day in `[startDay, k]`, and `L2` is available for every day in `[k + 1, endDay]`. Treat each availability list as a set, so duplicates do not matter. To make the output deterministic, return `single_stays` sorted lexicographically and `split_stays` sorted lexicographically by first listing name, then second listing name. For the example in the prompt, the correct result is `{'single_stays': [], 'split_stays': [['B', 'C']]}`.
Constraints
- 0 <= len(availability) <= 200
- All day numbers, `startDay`, and `endDay` are integers, and `startDay <= endDay`
- 0 <= total number of availability entries across all listings <= 2 * 10^4
- `endDay - startDay <= 365`
- Availability lists may be unsorted and may contain duplicates
Examples
Input: ({'A': [1, 2, 3, 6, 7, 10, 11], 'B': [3, 4, 5, 6, 8, 9, 10, 13], 'C': [7, 8, 9, 10, 11]}, 3, 11)
Expected Output: {'single_stays': [], 'split_stays': [['B', 'C']]}
Explanation: No listing covers every day from 3 through 11. Listing B covers 3 through 6, and listing C covers 7 through 11, so splitting after day 6 gives the only valid ordered pair.
Input: ({'A': [1, 2, 3, 4], 'B': [3, 4], 'C': [1, 2], 'D': [1, 2, 3, 4, 4]}, 1, 4)
Expected Output: {'single_stays': ['A', 'D'], 'split_stays': [['A', 'B'], ['A', 'D'], ['C', 'A'], ['C', 'B'], ['C', 'D'], ['D', 'A'], ['D', 'B']]}
Explanation: A and D each cover the whole range alone. C can cover the first half and B the second half, and full-range listings A and D can also be used on one side of a split. Ordered pairs matter, so validity depends on which listing comes first.
Hints
- For each listing, precompute how far it can continuously cover from `startDay` and how far it can continuously cover backward from `endDay`.
- A pair `[L1, L2]` is valid if `L1`'s prefix coverage reaches at least one day before `L2`'s suffix coverage starts.