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.

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

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.

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

Hints

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

Loading coding console...

Show the approach

Approach

The brute force would test every candidate split day for every pair. Instead, this solution precomputes, once per listing, the only two numbers a split decision ever depends on.

Per-listing summary (summarize). Sort the unique days and split them into maximal contiguous runs. For a listing's prefix role we only care: starting at L, how far right does an unbroken streak reach? That's first_end. If the run containing day L is [a, b], then first_end = min(b, R-1) (capped at R-1 since the split day s must satisfy s < R); if the listing isn't available on L, first_end stays L-1 (unusable). Symmetrically, for the suffix role, second_start is the earliest day from which an unbroken streak reaches R: max(a, L+1) for the run containing R, else R+1.

Pairing. Listing X can cover [L, s] for any s <= first[X]; listing Y can cover [s+1, R] for any s >= second[Y] - 1. A common split day exists exactly when second[Y] - 1 <= first[X], i.e. first[X] >= second[Y] - 1. The guards first[x] >= L (X actually starts at L) and second[y] <= R (Y actually reaches R) discard listings that can't fill their half. Iterating x, then y, over the sorted id list with x != y yields all valid ordered pairs already in lexicographic order, so no final sort is needed.

It's correct because contiguity means each segment's feasibility collapses to a single boundary day, and the inequality is precisely "some s lies in both feasible windows."

Time complexity:
O(sum(m_i log m_i) + N^2)
Space complexity:
O(N + max(m_i))