Generate split-stay pairs efficiently

Q: Generate split-stay pairs efficiently

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.

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

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Airbnb.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Question

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

PracHub · Accepted Answer

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

Quick Overview

Solution

Hints

Quick Overview