Airbnb·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Airbnb coding round, one meaty algorithmic problem about finding valid listing pairs across a date range split. The problem sounds like a search feature edge case but turns out to be a pretty involved intervals/bitmask question under the hood.

Questions Asked (1)

Given n listings each with a set of available dates, and a requested date range [start, end], find all distinct ordered pairs (A, B) of listings where you can stay at A for a contiguous prefix of the range and then move to B for the rest, with no gaps or overlaps. How do you represent availability efficiently and scan for valid split points?

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I went straight to a sorted set per listing and tried to think through the split point scan linearly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and defining an efficient representation for each listing's availability, such as a set of available dates or a sorted list of intervals. Then, for each listing, determine the longest contiguous prefix of the requested range it can cover, and for each possible split point, check if another listing can cover the remaining suffix. Use hash maps or interval trees to enable O(1) or O(log n) lookups for suffix availability, and iterate over all listings to collect distinct ordered pairs.

Pro tip: Emphasize that the split point must be exactly at a date boundary where the first listing's availability ends and the second's begins, and that you should precompute prefix and suffix coverage for each listing to avoid redundant checks. Also, mention that handling edge cases like full-range coverage by a single listing or no valid split is crucial for a robust solution.

1. Clarify requirements and constraints

Ask about input size, date granularity, whether listings can cover the entire range alone, and if pairs must be distinct. Confirm that the split must be contiguous with no gaps or overlaps.

2. Choose an efficient availability representation

Represent each listing's availability as a set of dates (e.g., hash set) or as sorted intervals. For fast prefix/suffix checks, precompute for each listing the earliest and latest dates it can cover within the range.

3. Compute prefix and suffix coverage

For each listing, find the longest contiguous prefix of [start, end] it can cover, and similarly the longest contiguous suffix. This can be done by scanning the range or using interval merging.

4. Scan for valid split points

For each listing A, consider each possible split point where A's prefix ends. Check if there exists a listing B (B ≠ A) that can cover the suffix starting at that split point. Use a hash map from start date to listings that can cover a suffix starting there.

5. Collect and deduplicate pairs

Gather all valid (A, B) pairs, ensuring they are distinct and ordered. Use a set to avoid duplicates if multiple split points yield the same pair.

Key Points to Mention

Time and space complexity trade-offs between different representations (e.g., hash sets vs. interval trees).
Handling of edge cases: single listing covering the entire range, no valid split, overlapping availabilities.
Use of prefix/suffix arrays or precomputation to avoid O(n^2) checks.
Efficiency of lookups: using hash maps to map split points to listings that can cover the suffix.
Distinctness of ordered pairs: ensuring (A, B) and (B, A) are treated as different and not duplicated.
Scalability considerations for large n and long date ranges, such as using date compression or interval indexing.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.