Compute split-stay listing pairs

Q: Compute split-stay listing pairs

This is a Coding & Algorithms interview question from Airbnb for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Compute split-stay listing pairs

Comments (0)