Airbnb·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Jun 2026

Summary

Airbnb coding round with a pretty gnarly interval/availability problem that took me a while to fully parse. The problem was dressed up in product language but the core was algorithmic, which I should've seen faster.

Questions Asked (1)

Given a set of listings each with availability as a sorted list of day integers, and a requested date range [S, E], find all unordered pairs of listings that can form a valid split stay covering the full range. A valid split requires some cutoff T where one listing covers S through T consecutively and another covers T+1 through E consecutively. Discuss algorithm, complexity (aim for better than O(L² · R)), and edge cases like missing boundary days or overlapping coverage.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The product framing tripped me up longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and constraints, then propose an efficient algorithm that preprocesses each listing's availability into intervals to quickly check coverage for any sub-range. Use a hash map to index listings by the days they cover, and for each possible cutoff T, find pairs where one listing covers [S, T] and another covers [T+1, E], ensuring no double-counting of unordered pairs. Analyze time and space complexity, and discuss edge cases such as missing boundary days, overlapping coverage, and listings that individually cover the entire range.

Pro tip: Demonstrate product thinking by connecting the algorithm to real-world constraints like data freshness and scalability, and mention how you would handle ties or multiple valid splits (e.g., by preferring the split with the longest first stay or earliest cutoff).

1. Clarify requirements and constraints

Ask about input size, whether listings can cover the entire range alone, if overlapping coverage is allowed, and if the output should be unique pairs. Confirm that availability lists are sorted and contain day integers.

2. Preprocess availability into intervals

For each listing, compress its sorted availability list into maximal consecutive intervals. This reduces the problem to interval coverage checks and enables O(log R) or O(1) queries per listing.

3. Design efficient pair-finding algorithm

For each possible cutoff T from S to E-1, find listings that cover [S, T] and listings that cover [T+1, E]. Use hash maps to index listings by the start and end of their coverage, or by the intervals they contain, to avoid O(L^2) comparisons.

4. Analyze complexity and optimize

Aim for O(L log L + R * (L1 + L2)) where L1 and L2 are the number of listings covering the left and right ranges respectively, or better. Discuss trade-offs between preprocessing time and query time.

5. Handle edge cases and validate

Consider cases where no split exists, where a listing covers the entire range (should it be paired with itself? No, since unordered pairs of distinct listings), missing boundary days (S or E not covered by any listing), and overlapping coverage that might create multiple valid cutoffs.

Key Points to Mention

Preprocessing availability into intervals to enable fast range coverage checks.
Using a hash map to index listings by the days they cover, e.g., mapping each day to listings available on that day.
Iterating over possible cutoffs T and using set intersections or two-pointer techniques to find valid pairs efficiently.
Avoiding double-counting unordered pairs by enforcing an ordering (e.g., listing ID or cutoff T).
Time complexity: O(L log L + R * K) where K is the average number of listings covering a day, or better with optimized data structures.
Edge cases: listings that cover the entire range, missing boundary days, overlapping coverage, and no valid split.

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