Quick Overview

This question evaluates a candidate's ability to manipulate intervals and set-based availability data, reason about contiguous date ranges, and enumerate valid single-listing and ordered two-listing split combinations.

Find valid split-stay listing combinations

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are building a feature that suggests a **split stay**: a guest stays in one home for the first part of a trip, then switches to a second home for the remainder. You are given: - A map `availability` from **listing name** (e.g., "A", "B") to a list of **available day numbers** (integers). - A requested **date range** `[startDay, endDay]` inclusive. Return **all valid split-stay options**: 1) **Single-listing stay**: any listing that is available for **every day** in `[startDay, endDay]`. 2) **Two-listing split stay**: any ordered pair `(L1, L2)` for which there exists a split day `k` with `startDay <= k < endDay` such that: - `L1` is available for every day in `[startDay, k]`, and - `L2` is available for every day in `[k+1, endDay]`. Notes / clarifications: - Availability is per-day; treat it as a set (duplicates don’t matter). - A listing may appear in at most one position within a split option (i.e., `L1 != L2`). - Output can be in any order; avoid duplicates. Example: - `A = [1,2,3,6,7,10,11]` - `B = [3,4,5,6,8,9,10,13]` - `C = [7,8,9,10,11]` - Query range: `[3, 11]` Determine which single listings and/or two-listing split stays satisfy the rules above.

Overview: This question evaluates a candidate's ability to manipulate intervals and set-based availability data, reason about contiguous date ranges, and enumerate valid single-listing and ordered two-listing split combinations.

Read the full Airbnb Software Engineer interview experience this question came from

You are given a dictionary `availability` where each key is a listing name and each value is a list of available day numbers. You are also given `startDay` and `endDay` for a requested trip, inclusive. Return all valid stay options in the form `{'single_stays': [...], 'split_stays': [...]}`. A single stay is any listing available for every day in `[startDay, endDay]`. A split stay is any ordered pair `[L1, L2]` with `L1 != L2` such that there exists a split day `k` where `startDay <= k < endDay`, `L1` is available for every day in `[startDay, k]`, and `L2` is available for every day in `[k + 1, endDay]`. Treat each availability list as a set, so duplicates do not matter. To make the output deterministic, return `single_stays` sorted lexicographically and `split_stays` sorted lexicographically by first listing name, then second listing name. For the example in the prompt, the correct result is `{'single_stays': [], 'split_stays': [['B', 'C']]}`.

Constraints

  • 0 <= len(availability) <= 200
  • All day numbers, `startDay`, and `endDay` are integers, and `startDay <= endDay`
  • 0 <= total number of availability entries across all listings <= 2 * 10^4
  • `endDay - startDay <= 365`
  • Availability lists may be unsorted and may contain duplicates

Examples

Input: ({'A': [1, 2, 3, 6, 7, 10, 11], 'B': [3, 4, 5, 6, 8, 9, 10, 13], 'C': [7, 8, 9, 10, 11]}, 3, 11)

Expected Output: {'single_stays': [], 'split_stays': [['B', 'C']]}

Explanation: No listing covers every day from 3 through 11. Listing B covers 3 through 6, and listing C covers 7 through 11, so splitting after day 6 gives the only valid ordered pair.

Input: ({'A': [1, 2, 3, 4], 'B': [3, 4], 'C': [1, 2], 'D': [1, 2, 3, 4, 4]}, 1, 4)

Expected Output: {'single_stays': ['A', 'D'], 'split_stays': [['A', 'B'], ['A', 'D'], ['C', 'A'], ['C', 'B'], ['C', 'D'], ['D', 'A'], ['D', 'B']]}

Explanation: A and D each cover the whole range alone. C can cover the first half and B the second half, and full-range listings A and D can also be used on one side of a split. Ordered pairs matter, so validity depends on which listing comes first.

Hints

  1. For each listing, precompute how far it can continuously cover from `startDay` and how far it can continuously cover backward from `endDay`.
  2. A pair `[L1, L2]` is valid if `L1`'s prefix coverage reaches at least one day before `L2`'s suffix coverage starts.

Community answers

Answer by Xiaoming

Nice question

Answer by psiinyou

package dsa; import java.util.*; public class SplitStay { List> findSplitStays(Map> availability, int startDate, int endDate){ Map> avail = new HashMap<>(); List> result = new ArrayList<>(); for(Map.Entry> entry : availability.entrySet()){ avail.put(entry.getKey(), new HashSet<>(entry.getValue())); } Map maxPrefixEnd = new HashMap<>(); Map minSuffixEnd = new HashMap<>(); for(String listing : avail.keySet()){ Set days = avail.get(listing); int k1 = startDate-1; while(k1+1 <= endDate && days.contains(k1+1)) k1++; maxPrefixEnd.put(listing, k1); int k2 = endDate+1; while(k2-1 >= startDate && days.contains(k2-1)) k2--; minSuffixEnd.put(listing, k2); if(k1 == endDate) result.add(Arrays.asList(listing)); } List listings = new ArrayList<>(avail.keySet()); for(int i= 0; i < listings.size(); i++){ for(int j = 0; j < listings.size(); j++){ if(i == j) continue; String L1 = listings.get(i); String L2 = listings.get(j); int k1 = maxPrefixEnd.get(L1); int k2 = minSuffixEnd.get(L2); int leftBound = Math.max(k2-1, startDate); int rightBound = Math.min(endDate-1, k1); if(leftBound <= rightBound) result.add(Arrays.asList(L1, L2)); } } return result; } public static void main(String[] args) { // Test Case 1: Original Example Map> tc1 = new HashMap<>(); tc1.put("A", Arrays.asList(1, 2, 3, 6, 7, 10, 11)); tc1.put("B", Arrays.asList(3, 4, 5, 6, 8, 9, 10, 13)); tc1.put("C", Arrays.asList(7, 8, 9, 10, 11)); runTestCase("Test Case 1: Original Example", tc1, 3, 11); // Test Case 2: Perfect Split (No Ov

Loading coding console...

Show the approach

Approach

Idea: For each listing, only two "contiguous reach" values matter relative to the query window [startDay, endDay].

  • prefix_end[name]: the last day k such that every day in [startDay, k] is available — i.e. how far an unbroken run starting at startDay reaches. If startDay itself is missing, this is startDay - 1.
  • suffix_start[name]: the first day k such that every day in [k, endDay] is available — how far back an unbroken run ending at endDay reaches.

Both are found with simple while scans over a set of each listing's days, so membership tests are O(1).

Single stays: a listing works alone iff its prefix run already reaches the end, prefix_end[name] == endDay. These are collected in sorted order (listings = sorted(...)).

Split stays [L1, L2]: we need a split day k with startDay <= k < endDay, where L1 covers [startDay, k] and L2 covers [k+1, endDay]. L1 can cover up to k = prefix_end[first]; L2 can cover starting from k+1 = suffix_start[second], i.e. k = suffix_start[second] - 1. So a valid k exists iff:

  • prefix_end[first] >= startDay (L1 covers at least day startDay),
  • suffix_start[second] <= endDay (L2 covers at least day endDay, which also guarantees k <= endDay-1), and
  • the two ranges overlap: prefix_end[first] >= suffix_start[second] - 1.

Iterating first then second in sorted order yields split_stays already sorted by first name then second name, so no extra sort is needed.

Time complexity:
O(T + L*D + L^2), where T is the total number of availability entries (building the day sets), L is the number of listings, and D = endDay - startDay + 1 is the query window (each listing does two O(D) scans). The split-stay double loop is O(L^2).
Space complexity:
O(T + L) — the per-listing day sets hold all T entries, plus O(L) for prefix_end/suffix_start maps and the output.