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 Technical Screen 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 hotel pairs to cover a split stay

Quick Overview

This question evaluates reasoning about interval coverage, set membership, combinatorial pairing of resources, and efficient processing of unsorted availability lists, reflecting skills in algorithm design and use of appropriate data structures.

Find hotel pairs to cover a split stay

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are implementing a simplified “split stay” feature. ## Problem You are given: - `n` hotels (or listings), indexed `0..n-1`. - For each hotel `i`, an **unsorted** list `avail[i]` of integer dates (e.g., days since epoch) indicating the dates that hotel is available. - A requested inclusive date range `[start_date, end_date]`. A **split stay** means the guest stays in **two different hotels** in two **contiguous, non-empty** segments that exactly cover the requested range: - Choose a split point `s` such that `start_date ≤ s < end_date`. - Hotel `A` must be available for **every date** in `[start_date, s]`. - Hotel `B` must be available for **every date** in `[s+1, end_date]`. - The stay is “forward only”: the first segment is earlier than the second; no interleaving/overlap beyond the shared boundary between `s` and `s+1`. - Hotels must be different: `A != B`. ## Output Return **all distinct valid combinations** as tuples: `(A, B, s)` meaning hotel `A` covers the left segment `[start_date, s]` and hotel `B` covers the right segment `[s+1, end_date]`. Notes: - If `avail[i]` contains duplicates, they should not create duplicate output tuples. - If no split stay is possible, return an empty list. ## Example (informal) If `[start_date, end_date] = [10, 13]` and a split `s=11` is chosen, then hotel `A` must cover dates `{10,11}` and hotel `B` must cover `{12,13}`.

Quick Answer: This question evaluates reasoning about interval coverage, set membership, combinatorial pairing of resources, and efficient processing of unsorted availability lists, reflecting skills in algorithm design and use of appropriate data structures.

You are implementing a simplified split-stay feature. You are given `n` hotels, indexed `0..n-1`. For each hotel `i`, `avail[i]` is an unsorted list of integer dates on which that hotel is available. You are also given an inclusive requested date range `[start_date, end_date]`. A valid split stay uses exactly two different hotels and exactly one split point `s` such that `start_date <= s < end_date`: - Hotel `A` covers every date in `[start_date, s]` - Hotel `B` covers every date in `[s+1, end_date]` - Both segments must be non-empty - `A != B` Return all distinct valid tuples `(A, B, s)`, where hotel `A` covers the left segment and hotel `B` covers the right segment. Important details: - `avail[i]` may be unsorted and may contain duplicates. - Duplicates in `avail[i]` must not create duplicate output tuples. - Return the result sorted by split point `s` ascending, then by `A` ascending, then by `B` ascending. - If no valid split stay exists, return an empty list.

Constraints

1 <= len(avail) <= 2000

Loading coding console...

Examples

Input: ([[10, 11], [12, 13], [10, 11, 12], [11, 12, 13]], 10, 13)

Expected Output: [(0, 3, 10), (2, 3, 10), (0, 1, 11), (0, 3, 11), (2, 1, 11), (2, 3, 11), (2, 1, 12), (2, 3, 12)]

Explanation: There are three possible split points: 10, 11, and 12. For each split, combine hotels that fully cover the left prefix with hotels that fully cover the right suffix, excluding pairs using the same hotel.

Input: ([[5, 4, 4, 6], [7, 6, 6], [5, 6, 7], [4, 5]], 5, 7)

Expected Output: [(0, 1, 5), (0, 2, 5), (2, 1, 5), (3, 1, 5), (3, 2, 5), (0, 1, 6), (0, 2, 6), (2, 1, 6)]

Explanation: The availability lists are unsorted and contain duplicates, but duplicates should not change the result. The valid splits are `s=5` and `s=6`.

Input: ([[-2, -1, 0], [1, 0], [-2, -1], [0, 1]], -2, 1)

Expected Output: [(0, 1, -1), (0, 3, -1), (2, 1, -1), (2, 3, -1), (0, 1, 0), (0, 3, 0)]

Explanation: This checks that negative dates work correctly. Split `s=-2` is impossible, while `s=-1` and `s=0` both produce valid hotel pairs.

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

Expected Output: []

Explanation: No pair of different hotels can cover two contiguous non-empty segments that exactly span dates 1 through 4.

Input: ([[10], [10, 11]], 10, 10)

Expected Output: []

Explanation: The requested range has only one date, so it cannot be split into two non-empty contiguous segments.

Solution

def solution(avail, start_date, end_date):
    n = len(avail)

    # Need two non-empty contiguous segments, so at least two dates are required.
    if n < 2 or start_date >= end_date:
        return []

    # left_end[i] = largest date x such that hotel i covers every date in [start_date, x]
    # If hotel i does not cover start_date, left_end[i] will stay start_date - 1.
    left_end = [start_date - 1] * n

    # right_start[i] = smallest date x such that hotel i covers every date in [x, end_date]
    # If hotel i does not cover end_date, right_start[i] will stay end_date + 1.
    right_start = [end_date + 1] * n

    for i, days in enumerate(avail):
        day_set = set(days)  # removes duplicates and allows O(1) average membership checks

        d = start_date
        while d <= end_date and d in day_set:
            left_end[i] = d
            d += 1

        d = end_date
        while d >= start_date and d in day_set:
            right_start[i] = d
            d -= 1

    ans = []

    # Generate results in required order: s ascending, then A ascending, then B ascending.
    for s in range(start_date, end_date):
        left_hotels = []
        right_hotels = []

        for i in range(n):
            if left_end[i] >= s:
                left_hotels.append(i)
            if right_start[i] <= s + 1:
                right_hotels.append(i)

        for a in left_hotels:
            for b in right_hotels:
                if a != b:
                    ans.append((a, b, s))

    return ans

Time complexity: O(T + n * R + K), where `T` is the total number of availability entries, `R = end_date - start_date + 1`, and `K` is the number of returned tuples. Space complexity: O(n + M + K), where `M` is the maximum number of unique dates in a single hotel's availability list and `K` is the size of the returned result.

Quick Overview

Find hotel pairs to cover a split stay

Constraints

Examples

Solution

Hints