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

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

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