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 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.

Input: ({'Loft': [5, 5, 3], 'Cabin': [4, 5], 'Studio': []}, 5, 5)

Expected Output: {'single_stays': ['Cabin', 'Loft'], 'split_stays': []}

Explanation: The trip is only one day long, so there is no possible split day. Cabin and Loft are both available on day 5, so they are valid single stays.

Input: ({'X': [-2, -1], 'Y': [1, 2], 'Z': [-2, 0, 1]}, -2, 1)

Expected Output: {'single_stays': [], 'split_stays': [['X', 'Z']]}

Explanation: Negative day numbers are allowed. X covers days -2 and -1, while Z covers days 0 and 1, so splitting after day -1 makes `[X, Z]` valid. No single listing covers the whole range.

Input: ({}, 1, 3)

Expected Output: {'single_stays': [], 'split_stays': []}

Explanation: With no listings, there are no possible single stays or split stays.

Solution

def solution(availability, startDay, endDay):
    listings = sorted(availability.keys())
    day_sets = {name: set(days) for name, days in availability.items()}
    prefix_end = {}
    suffix_start = {}

    for name in listings:
        days = day_sets[name]

        day = startDay
        while day <= endDay and day in days:
            day += 1
        prefix_end[name] = day - 1

        day = endDay
        while day >= startDay and day in days:
            day -= 1
        suffix_start[name] = day + 1

    single_stays = [name for name in listings if prefix_end[name] == endDay]

    split_stays = []
    if startDay < endDay:
        for first in listings:
            if prefix_end[first] < startDay:
                continue
            for second in listings:
                if first == second:
                    continue
                if suffix_start[second] > endDay:
                    continue
                if prefix_end[first] >= suffix_start[second] - 1:
                    split_stays.append([first, second])

    return {'single_stays': single_stays, 'split_stays': split_stays}

Explanation

**Idea:** For each listing, only two "contiguous reach" values matter relative to the query window `[startDay, endDay]`. - `prefix_end[name]`: the last day `k` such that **every** day in `[startDay, k]` is available — i.e. how far an unbroken run starting at `startDay` reaches. If `startDay` itself is missing, this is `startDay - 1`. - `suffix_start[name]`: the first day `k` such that **every** day in `[k, endDay]` is available — how far back an unbroken run ending at `endDay` reaches. Both are found with simple `while` scans over a `set` of each listing's days, so membership tests are O(1). **Single stays:** a listing works alone iff its prefix run already reaches the end, `prefix_end[name] == endDay`. These are collected in sorted order (`listings = sorted(...)`). **Split stays `[L1, L2]`:** we need a split day `k` with `startDay <= k < endDay`, where `L1` covers `[startDay, k]` and `L2` covers `[k+1, endDay]`. `L1` can cover up to `k = prefix_end[first]`; `L2` can cover starting from `k+1 = suffix_start[second]`, i.e. `k = suffix_start[second] - 1`. So a valid `k` exists iff: - `prefix_end[first] >= startDay` (L1 covers at least day `startDay`), - `suffix_start[second] <= endDay` (L2 covers at least day `endDay`, which also guarantees `k <= endDay-1`), and - the two ranges overlap: `prefix_end[first] >= suffix_start[second] - 1`. Iterating `first` then `second` in sorted order yields `split_stays` already sorted by first name then second name, so no extra sort is needed.

Time complexity: O(T + L*D + L^2), where T is the total number of availability entries (building the day sets), L is the number of listings, and D = endDay - startDay + 1 is the query window (each listing does two O(D) scans). The split-stay double loop is O(L^2).. Space complexity: O(T + L) — the per-listing day sets hold all T entries, plus O(L) for prefix_end/suffix_start maps and the output..

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.

Quick Overview

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.