Airbnb·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Airbnb SWE interview with a pretty gnarly algorithmic problem involving listing availability and date ranges. The problem looked deceptively manageable until you actually had to beat the naive approach.

Questions Asked (1)

Given N Airbnb listings each with a set of available days, and a requested date range [L, R], return all ordered pairs of distinct listings (X, Y) such that there's some split day s where X covers [L, s] continuously and Y covers [s+1, R] continuously. The naive O(N^2 * R) solution isn't acceptable. Describe a better algorithm with data structures, complexity analysis, and handling for sparse availability and large ranges.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

I started with the brute force just to make sure I understood the problem, then got stuck for a bit on how to actually precompute the useful stuff.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reframe the problem as finding, for each split day s, the intersection of listings that cover [L, s] and those that cover [s+1, R]. Precompute prefix and suffix coverage sets using interval trees or bitsets, then efficiently enumerate ordered pairs by intersecting these sets. Address sparsity and large ranges by compressing days and using hash-based or sorted interval representations.

Pro tip: Emphasize that the split day s can be any day in [L, R-1], and that the same listing can appear in both prefix and suffix sets but must be distinct in the pair. Also, mention that if availability is sparse, iterating over only the days where coverage changes (event points) reduces work significantly.

1. Clarify and formalize

Restate the problem: for each split s in [L, R-1], find all ordered pairs (X, Y) with X covering [L, s] and Y covering [s+1, R], X ≠ Y. Confirm that listings may have multiple availability intervals and that coverage must be continuous.

2. Preprocess availability

For each listing, merge overlapping intervals and clip to [L, R]. Build data structures to quickly answer: which listings cover a given day? and which cover a given range continuously? Consider interval trees, segment trees with sets, or bitsets if N is small.

3. Compute prefix and suffix coverage sets

For each day d in [L, R], compute P[d] = set of listings covering [L, d] and S[d] = set of listings covering [d, R]. Use incremental updates: P[d] = P[d-1] ∩ listings covering d, and similarly for S from right to left. Store these sets efficiently (e.g., as bitsets or hash sets).

4. Enumerate valid pairs

For each split s from L to R-1, iterate over listings in P[s] and for each X, find Y in S[s+1] with Y ≠ X. If using bitsets, compute the intersection and then subtract X. Output all ordered pairs. Optimize by skipping splits where P[s] or S[s+1] is empty.

5. Analyze complexity and handle edge cases

Time: O((R-L+1) * (N/word_size) + total_pairs) with bitsets, or O(total_events * average_set_size) with sparse sets. Space: O((R-L+1) * N/word_size) for bitsets, or O(N * number_of_intervals) for sparse. Discuss large ranges: compress days to event points where coverage changes; only splits at these points matter. Handle sparse availability by using hash sets and iterating over smaller sets.

Key Points to Mention

Interval merging and clipping to the query range to reduce data size.
Using bitsets for fast set intersections when N is moderate (e.g., N ≤ 10^4).
For large N or sparse data, use inverted indices: for each day, store the set of listings covering it, then intersect incrementally.
Day compression: only days where the set of covering listings changes (event points) need to be considered as split candidates.
Complexity analysis: O((R-L+1) * N/64) with bitsets, or O(total_events * average_set_size) with sparse sets; output-sensitive if many pairs.
Handling X ≠ Y: when enumerating, either subtract X from the suffix set or skip if X is the only element.

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