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

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.

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`

Loading coding console...

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}

Time complexity: O(T + L * D + L^2), where T is the total number of availability entries, L is the number of listings, and D is the number of days in the query range. Space complexity: O(T + L).

Quick Overview

Find valid split-stay listing combinations

Constraints

Examples

Solution

Hints