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

Generate split-stay pairs efficiently | Airbnb Coding Question

Generate split-stay pairs efficiently

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given N Airbnb listings, each with available days as integers, and an inclusive requested date range [L, R], return all ordered pairs (X, Y) of distinct listings such that there exists a split day s in [L, R−1] where X is available for every day in [L, s] and Y is available for every day in [s+1, R]. Availability for each stay segment must be contiguous. Design an algorithm that improves on the naive O(N^2 · R) approach: describe data structures, core steps, and time/space complexity. Discuss how to handle sparse availability and large ranges. For the example A=[1,2,3,6,7,10,11], B=[3,4,5,6,8,9,10,13], C=[7,8,9,10,11] with [L, R]=[3, 11], the valid result is [(B, C)].

Quick Answer: This question evaluates algorithm design and data-structure competency, focusing on interval reasoning, efficient enumeration of ordered pairs under availability constraints, and time/space complexity analysis for large or sparse date ranges.

You are given a dictionary `listings` where each key is a listing ID and each value is a list of integer days when that listing is available. A guest wants to stay for every day in the inclusive range `[L, R]`, but may switch listings once. Return all ordered pairs `(X, Y)` of distinct listing IDs such that there exists a split day `s` with `L <= s < R` where `X` is available for every day in `[L, s]` and `Y` is available for every day in `[s+1, R]`. Each stay segment must be contiguous: missing even one day makes that segment invalid. Days may be unsorted, duplicated, sparse, and can be negative. Return the answer as a list of tuples sorted lexicographically by `X`, then by `Y`. A good solution should avoid checking every day in `[L, R]` for every pair.

Constraints

0 <= number of listings <= 2000
-10^9 <= L <= R <= 10^9
The total number of availability entries across all listings is at most 2 * 10^5
Availability lists may be unsorted and may contain duplicates
Do not assume the range size `R - L + 1` is small enough to scan directly for every pair

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: [('B', 'C')]

Explanation: B covers days 3 through 6 contiguously, and C covers days 7 through 11 contiguously, so splitting after day 6 works. No other ordered pair covers the full range.

Input: ({'P': [1,2,3], 'Q': [4,5], 'R': [3,4,5]}, 1, 5)

Expected Output: [('P', 'Q'), ('P', 'R')]

Explanation: P can cover the first segment. Q covers 4 to 5, so splitting after 3 gives (P, Q). R covers 3 to 5, so splitting after 2 gives (P, R).

Input: ({'A': [5], 'B': [5]}, 5, 5)

Expected Output: []

Explanation: There is no valid split day because `s` must satisfy `L <= s < R`, and here `L == R`.

Input: ({'N1': [0,-1,-2,-2], 'N2': [2,1,1], 'N3': [-2,-1,0,1,2]}, -2, 2)

Expected Output: [('N1', 'N2'), ('N1', 'N3'), ('N3', 'N2')]

Explanation: After sorting and deduplicating, N1 covers -2 to 0, N2 covers 1 to 2, and N3 covers -2 to 2. So N1 can hand off to N2 or N3, and N3 can hand off to N2.

Input: ({}, 1, 3)

Expected Output: []

Explanation: With no listings, no ordered pair can be formed.

Input: ({'A': [], 'B': [1,2], 'C': [3]}, 1, 3)

Expected Output: [('B', 'C')]

Explanation: A has no availability. B covers days 1 to 2 contiguously and C covers day 3, so splitting after day 2 gives the only valid pair.

Solution

def solution(listings, L, R):
    if L >= R or len(listings) < 2:
        return []

    def summarize(days):
        uniq = sorted(set(days))
        if not uniq:
            return L - 1, R + 1

        first_end = L - 1
        second_start = R + 1

        start = uniq[0]
        prev = uniq[0]

        def process_run(a, b):
            nonlocal first_end, second_start
            if a <= L <= b:
                first_end = min(b, R - 1)
            if a <= R <= b:
                second_start = max(a, L + 1)

        for d in uniq[1:]:
            if d == prev + 1:
                prev = d
            else:
                process_run(start, prev)
                start = d
                prev = d
        process_run(start, prev)

        return first_end, second_start

    first = {}
    second = {}
    for name, days in listings.items():
        fe, ss = summarize(days)
        first[name] = fe
        second[name] = ss

    ids = sorted(listings.keys())
    result = []

    for x in ids:
        if first[x] < L:
            continue
        for y in ids:
            if x == y:
                continue
            if second[y] > R:
                continue
            if first[x] >= second[y] - 1:
                result.append((x, y))

    return result

Time complexity: O(sum(m_i log m_i) + N^2), where m_i is the number of availability entries for listing i and N is the number of listings. Space complexity: O(N + max(m_i)) auxiliary space.

Hints

For each listing, you do not need to remember every possible split day. It is enough to know how far a contiguous run starting at `L` can extend, and how early a contiguous run ending at `R` can begin.
When availability is sparse, sort and deduplicate the days, then compress them into consecutive runs. Only the run containing `L` and the run containing `R` matter.

Quick Overview

This question evaluates algorithm design and data-structure competency, focusing on interval reasoning, efficient enumeration of ordered pairs under availability constraints, and time/space complexity analysis for large or sparse date ranges.