Frontend School

Listing Availability Queries

DSA
medium

Listing Availability Queries

Medium
Segment Tree
Data Structures
Arrays
Range Query
Point Update

Overview

At Airbnb, ensuring hosts can efficiently manage their listing availability is crucial. Hosts frequently need to update the booking status for specific days and quickly check if their listing is entirely available for a given date range. This problem simulates a core part of that functionality, challenging you to design an efficient data structure to handle such operations.

What you need to do / Task

You are tasked with implementing a function processAvailabilityQueries that takes an initial availability schedule for a listing and a sequence of operations. These operations include updating the booking status for a single day and querying whether a contiguous range of days is fully available.

Your solution should be optimized for scenarios with a large number of days and frequent queries/updates.

Input & output

Function Signature:

function processAvailabilityQueries(initialAvailability: number[], operations: [string, ...number[]][]): (number | boolean | null)[]

Parameters:

  • initialAvailability: An array of integers representing the initial availability status for days. Each element initialAvailability[i] is either 0 (available) or 1 (booked). Days are 0-indexed.
  • operations: An array of operations to perform. Each operation is an array following one of these formats:
    • ["update", dayIndex, status]: Updates the availability status of dayIndex to status. status will be 0 (available) or 1 (booked).
    • ["query", startDay, endDay]: Checks if all days from startDay to endDay (inclusive) are available (0).

Return Value: An array containing the results of each operation in the order they were processed. For "query" operations, return true if the range is fully available, false otherwise. For "update" operations, return null.

Clarifications

  • Day Indexing: All day indices (dayIndex, startDay, endDay) are 0-indexed and inclusive.
  • Availability Status: 0 means the day is available, 1 means the day is booked.
  • Query Definition: A range [startDay, endDay] is considered "fully available" only if every day within that range has an availability status of 0.

Examples

1

Example 1

Input:

initialAvailability = [0, 0, 1, 0, 0], operations = [["query", 0, 1], ["query", 1, 3], ["update", 2, 0], ["query", 1, 3]]

Output:

[true,false,null,true]

Note:

  1. query(0, 1): Days [0, 1] are [0, 0]. Max is 0, so fully available (true).
  2. query(1, 3): Days [1, 2, 3] are [0, 1, 0]. Max is 1, so not fully available (false).
  3. update(2, 0): Day 2 becomes 0. Availability is now [0, 0, 0, 0, 0].
  4. query(1, 3): Days [1, 2, 3] are [0, 0, 0]. Max is 0, so fully available (true).
2

Example 2

Input:

initialAvailability = [1, 0, 0], operations = [["query", 0, 0], ["query", 0, 2], ["update", 0, 0], ["query", 0, 2]]

Output:

[false,false,null,true]

Note:

  1. query(0, 0): Day [0] is [1]. Max is 1, so not fully available (false).
  2. query(0, 2): Days [0, 1, 2] are [1, 0, 0]. Max is 1, so not fully available (false).
  3. update(0, 0): Day 0 becomes 0. Availability is now [0, 0, 0].
  4. query(0, 2): Days [0, 1, 2] are [0, 0, 0]. Max is 0, so fully available (true).
3

Example 3

Input:

initialAvailability = [1, 1, 1, 1], operations = [["query", 0, 3], ["update", 0, 0], ["update", 1, 0], ["query", 0, 1], ["query", 2, 3]]

Output:

[false,null,null,true,false]

Note:

  1. query(0, 3): Days [0, 1, 2, 3] are [1, 1, 1, 1]. Max is 1, so not fully available (false).
  2. update(0, 0): Day 0 becomes 0. Availability is [0, 1, 1, 1].
  3. update(1, 0): Day 1 becomes 0. Availability is [0, 0, 1, 1].
  4. query(0, 1): Days [0, 1] are [0, 0]. Max is 0, so fully available (true).
  5. query(2, 3): Days [2, 3] are [1, 1]. Max is 1, so not fully available (false).

Constraints

Constraints & assumptions

  • The number of days N (length of initialAvailability) will be between 1 and 10^5.
  • The number of operations Q will be between 1 and 10^5.
  • initialAvailability[i] will be 0 or 1.
  • For "update" operations: 0 <= dayIndex < N, status is 0 or 1.
  • For "query" operations: 0 <= startDay <= endDay < N.
  • Time limit: 1 second.
  • Memory limit: 256 MB.

Out of scope

  • Handling invalid input (e.g., dayIndex out of bounds, malformed operations).
  • Complex booking logic (e.g., partial day bookings, pricing, user authentication).
  • Concurrency or distributed system aspects.

What interviewers evaluate

  • Correctness: The solution accurately processes all availability updates and queries according to the problem specification.
  • Efficiency: The chosen data structure and algorithms achieve optimal time complexity for range queries and point updates.
  • Clarity & Structure: The code is well-organized, readable, and demonstrates a clear understanding of the underlying data structure.
  • Edge Cases: The solution handles various edge cases, such as single-day ranges, full-range queries, and completely booked/available scenarios.

Loading editor...