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.

Compute split-stay listing pairs | Airbnb Coding Question

Compute split-stay listing pairs

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a set of Airbnb listings, each with availability represented as a sorted list of day integers, and a requested inclusive date range [S, E], compute all unordered pairs of listings (X, Y) that can form a split stay covering the entire range. A valid split stay exists if there is an integer T with S ≤ T < E such that listing X has every day from S through T available consecutively and listing Y has every day from T+1 through E available consecutively. Return each pair once (order-insensitive), and specify the algorithm, time/space complexity targets (strive for better than O(L^2 · R)), and edge cases (e.g., missing boundary days, overlapping coverage on both listings, identical availability, or no possible pairs). Example data: A -> [1,2,3,6,7,10,11], B -> [3,4,5,6,8,9,10,13], C -> [7,8,9,10,11]; for [3,11] the valid pair is [B, C].

Quick Answer: This question evaluates the ability to manipulate interval availability data, reason about contiguous date ranges and split boundaries, and design efficient pairing algorithms with attention to time and space complexity.

You are given Airbnb listings and their available days. Each listing ID maps to a sorted list of available day integers. Given an inclusive requested date range [S, E], return all unordered pairs of distinct listings that can form a valid split stay covering the entire range. A pair {X, Y} is valid if there exists an integer split point T with S <= T < E such that: - listing X is available on every day from S through T consecutively, and - listing Y is available on every day from T + 1 through E consecutively. The two listings may overlap in coverage, and one listing may even cover the whole range by itself. However, the pair must contain two different listing IDs, and each unordered pair should be returned only once. Return each pair as a 2-element list of listing IDs in lexicographic order, and return the full result sorted lexicographically by pair. If no pairs are possible, return an empty list. Your goal should be better than checking every pair across every day in the range.

Constraints

0 <= len(listings) <= 2000
0 <= sum(len(days) for days in listings.values()) <= 200000
Each availability list is sorted in ascending order and contains distinct integers
Days may be negative or positive integers, and S <= E
If S == E, the answer is always [] because no split point T exists with S <= T < E

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 consecutively, and C covers days 7 through 11 consecutively, so splitting at T = 6 works. No other unordered pair covers the full range.

Input: ({'X': [1,2,3,4], 'Y': [2,3,4], 'Z': [1,2,3,4]}, 1, 4)

Expected Output: [['X', 'Y'], ['X', 'Z'], ['Y', 'Z']]

Explanation: X and Z each cover the whole range, while Y covers 2 through 4. X can pair with Y, Z can pair with Y, and X can pair with Z. This also covers the identical-availability case for X and Z.

Input: ({'H1': [1,2], 'H2': [4,5], 'H3': [2,3,4]}, 1, 5)

Expected Output: []

Explanation: No pair can cover every day from 1 through 5 consecutively. There is always a missing boundary day or an uncovered gap.

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

Expected Output: []

Explanation: The requested range has only one day, so there is no valid split point T with 5 <= T < 5.

Solution

def solution(listings, S, E):
    if S >= E or not listings or len(listings) < 2:
        return []

    def prefix_end(days):
        n = len(days)
        i = 0
        while i < n and days[i] < S:
            i += 1
        if i == n or days[i] != S:
            return S - 1

        end = S
        prev = S
        i += 1

        while i < n:
            d = days[i]
            if d == prev:
                i += 1
                continue
            if d > E:
                break
            if d == prev + 1:
                end = d
                prev = d
                i += 1
            else:
                break
        return end

    def suffix_start(days):
        i = len(days) - 1
        while i >= 0 and days[i] > E:
            i -= 1
        if i < 0 or days[i] != E:
            return E + 1

        start = E
        prev = E
        i -= 1

        while i >= 0:
            d = days[i]
            if d == prev:
                i -= 1
                continue
            if d < S:
                break
            if d == prev - 1:
                start = d
                prev = d
                i -= 1
            else:
                break
        return start

    ids = sorted(listings.keys())
    pref = {}
    suff = {}

    for listing_id in ids:
        days = listings.get(listing_id, [])
        pref[listing_id] = prefix_end(days)
        suff[listing_id] = suffix_start(days)

    result = []
    for i in range(len(ids)):
        a = ids[i]
        for j in range(i + 1, len(ids)):
            b = ids[j]
            a_then_b = pref[a] >= S and suff[b] <= E and pref[a] + 1 >= suff[b]
            b_then_a = pref[b] >= S and suff[a] <= E and pref[b] + 1 >= suff[a]
            if a_then_b or b_then_a:
                result.append([a, b])

    return result

Time complexity: O(A + L^2), where A is the total number of availability entries across all listings and L is the number of listings. Space complexity: O(L), excluding the output list.

Hints

For each listing, compute how far it can cover consecutively starting from S, and how early it can cover consecutively ending at E.
After that preprocessing, a pair is valid in O(1): one listing's prefix coverage must reach at least one day before the other listing's suffix coverage begins.

Quick Overview

This question evaluates the ability to manipulate interval availability data, reason about contiguous date ranges and split boundaries, and design efficient pairing algorithms with attention to time and space complexity.