How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Find a split-stay booking across listings

Q: Find a split-stay booking across listings

This question evaluates understanding of interval coverage and algorithmic problem solving, specifically reasoning about continuous date ranges, split-interval feasibility, and efficient handling of multiple sorted availability intervals.

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are implementing a simplified **split-stay** search. You are given: - A desired trip interval **[start, end)**, where dates are represented as integers (e.g., days). The guest stays nights `start, start+1, ..., end-1`. - `n` listings. For each listing `i`, you are given a set of **available** (bookable) date intervals `avail[i]`, each as **[li, ri)**. Intervals within a listing are non-overlapping and sorted. A trip is feasible if it can be covered by: 1. **One listing** that is available for the entire interval **[start, end)**, OR 2. **Exactly two listings** `(A, B)` with a single switch day `mid` such that: - Listing `A` covers **[start, mid)** - Listing `B` covers **[mid, end)** - `start < mid < end` (both stays are non-empty) - There are **no gaps** and no overlap requirements beyond continuous coverage. ### Task Return whether the trip is feasible. If feasible, return **one valid plan**: - Either `(A)` for a single-listing stay, or - `(A, B, mid)` for a split stay. ### Constraints (you may assume) - `1 ≤ n ≤ 2e5` - Total number of availability intervals across all listings ≤ `2e5` - Dates fit in 32-bit signed integers. ### Notes - Listings are identified by integer IDs `0..n-1`. - Availability intervals are inclusive of `li` and exclusive of `ri`.

Quick Answer: This question evaluates understanding of interval coverage and algorithmic problem solving, specifically reasoning about continuous date ranges, split-interval feasibility, and efficient handling of multiple sorted availability intervals.

You are implementing a simplified split-stay search. You are given a desired trip interval [start, end), where dates are integers. The guest stays nights start, start+1, ..., end-1. There are n listings, identified by IDs 0..n-1. For each listing i, avail[i] is a sorted list of non-overlapping availability intervals (li, ri), meaning the listing is bookable on [li, ri). A trip is feasible if it can be covered by either: 1. One listing that covers the entire interval [start, end), or 2. Two distinct listings A and B with exactly one switch day mid such that: - start < mid < end - listing A covers [start, mid) - listing B covers [mid, end) - there are no gaps in coverage Adjacent intervals inside the same listing, such as (3, 5) and (5, 7), should be treated as continuous availability. Return a pair (feasible, plan): - (True, (A,)) if one listing covers the entire trip - (True, (A, B, mid)) if a valid split-stay plan exists - (False, None) if no valid plan exists If multiple valid plans exist, returning any one of them is acceptable.

Constraints

1 <= len(avail) <= 2 * 10^5
The total number of intervals across all listings is at most 2 * 10^5
Intervals inside each listing are sorted by start and do not overlap
Dates fit in 32-bit signed integers
start < end
For the split-stay case, A and B must be different listing IDs

Examples

Input: ([[(1,10)],[(1,4),(5,9)]], 2, 7)

Expected Output: (True, (0,))

Explanation: Listing 0 is available for the full interval [2,7), so a single-listing stay works.

Input: ([[(1,4)],[(4,8)],[(2,3),(3,5)]], 1, 8)

Expected Output: (True, (0, 1, 4))

Explanation: Listing 0 covers [1,4) and listing 1 covers [4,8), so switching on day 4 gives continuous coverage.

Input: ([[(1,3),(3,6)],[(6,8)]], 2, 6)

Expected Output: (True, (0,))

Explanation: The two intervals of listing 0 touch, so together they form continuous availability [1,6), which covers the whole trip.

Input: ([[(1,3)],[(4,6)],[(6,7)]], 1, 7)

Expected Output: (False, None)

Explanation: No single listing covers [1,7), and no pair of distinct listings can cover it without a gap.

Input: ([[(-5,-2)],[(-2,1)],[(-10,-6)]], -5, 1)

Expected Output: (True, (0, 1, -2))

Explanation: Listing 0 covers [-5,-2) and listing 1 covers [-2,1), so a valid split exists with switch day -2.

Input: ([[],[(0,2)],[(2,4)]], 0, 4)

Expected Output: (True, (1, 2, 2))

Explanation: Listing 1 covers [0,2) and listing 2 covers [2,4). The empty listing does not affect the answer.

Hints

First merge touching intervals within each listing into maximal continuous blocks.
For each listing, you only need to know two things: how far right it can continuously cover starting from start, and how far left it can continuously cover ending at end.

Quick Overview

This question evaluates understanding of interval coverage and algorithmic problem solving, specifically reasoning about continuous date ranges, split-interval feasibility, and efficient handling of multiple sorted availability intervals.