Frontend School

Driver Availability Monitor

DSA
medium

Driver Availability Monitor

Medium
Segment Tree
Data Structures
Range Query
Point Update

Overview

Uber's operations heavily rely on real-time driver availability to ensure efficient ride-hailing services. Imagine a city divided into a series of N logical zones, indexed from 0 to N-1. At any given moment, each zone has a certain number of available drivers. As drivers go online/offline or move between zones, their availability count changes. We need a system to efficiently track these changes and provide quick insights into driver distribution across different areas.

This problem asks you to implement a data structure that can handle dynamic updates to driver counts in individual zones and perform two types of critical queries over arbitrary ranges of zones: calculating the total available drivers and identifying the maximum availability in any single zone within a given region.

What you need to do / Task

Implement the DriverAvailabilityMonitor class with the following methods:

  1. constructor(initialDrivers: number[]): Initializes the monitoring system with an array initialDrivers where initialDrivers[i] represents the initial number of available drivers in zone i.
  2. updateDrivers(zoneIndex: number, newCount: number): void: Updates the number of available drivers in the specified zoneIndex to newCount.
  3. queryTotalAvailable(startZone: number, endZone: number): number: Returns the sum of available drivers in all zones from startZone to endZone (inclusive).
  4. queryMaxAvailableZone(startZone: number, endZone: number): number: Returns the maximum number of available drivers found in any single zone within the range startZone to endZone (inclusive).

Input & output

  • initialDrivers: number[]: An array of non-negative integers representing the initial number of available drivers in each zone. initialDrivers[i] corresponds to zone i.
  • zoneIndex: number: The 0-indexed position of the zone to be updated.
  • newCount: number: The new non-negative number of available drivers for the specified zoneIndex.
  • startZone: number: The 0-indexed start of the query range (inclusive).
  • endZone: number: The 0-indexed end of the query range (inclusive).
  • Return Value (queryTotalAvailable, queryMaxAvailableZone): A non-negative integer representing the total available drivers or the maximum available drivers in the queried range, respectively.
  • Return Value (constructor, updateDrivers): void (implicitly null in test runner for class methods).

Clarifications

  • All zone indices are 0-based.
  • Queries and updates involve valid zoneIndex, startZone, and endZone within the bounds [0, N-1], where N is the number of zones.
  • startZone will always be less than or equal to endZone for queries.
  • The number of drivers will always be non-negative.

Examples

1

Example 1

Input:

operations = ["DriverAvailabilityMonitor","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryTotalAvailable"] params = [[[10,5,20,15]],[0,3],[0,3],[1,25],[0,3],[0,3],[2,8],[1,2]]

Output:

[null,50,20,null,70,25,null,33]

Note:

  1. Initialize with drivers: [10, 5, 20, 15]
  2. queryTotalAvailable(0, 3): Sum(10+5+20+15) = 50
  3. queryMaxAvailableZone(0, 3): Max(10,5,20,15) = 20
  4. updateDrivers(1, 25): Array becomes [10, 25, 20, 15]
  5. queryTotalAvailable(0, 3): Sum(10+25+20+15) = 70
  6. queryMaxAvailableZone(0, 3): Max(10,25,20,15) = 25
  7. updateDrivers(2, 8): Array becomes [10, 25, 8, 15]
  8. queryTotalAvailable(1, 2): Sum(25+8) = 33
2

Example 2

Input:

operations = ["DriverAvailabilityMonitor","queryMaxAvailableZone","updateDrivers","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryMaxAvailableZone"] params = [[[1,2,3]],[0,0],[0,10],[0,2],[1,2],[2,0],[0,2]]

Output:

[null,1,null,15,3,null,10]

Note:

  1. Initialize with drivers: [1, 2, 3]
  2. queryMaxAvailableZone(0, 0): Max(1) = 1
  3. updateDrivers(0, 10): Array becomes [10, 2, 3]
  4. queryTotalAvailable(0, 2): Sum(10+2+3) = 15
  5. queryMaxAvailableZone(1, 2): Max(2,3) = 3
  6. updateDrivers(2, 0): Array becomes [10, 2, 0]
  7. queryMaxAvailableZone(0, 2): Max(10,2,0) = 10

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (where N is the number of zones/length of initialDrivers)
  • 0 <= initialDrivers[i] <= 10^4
  • 0 <= newCount <= 10^4
  • 0 <= zoneIndex < N
  • 0 <= startZone <= endZone < N
  • 1 <= total number of operations (constructor, updates, queries) <= 10^5
  • Time complexity for updateDrivers, queryTotalAvailable, and queryMaxAvailableZone should be O(log N).
  • Space complexity should be O(N).

What interviewers evaluate

  • Correctness: The solution must correctly implement all required operations, including handling updates and range queries accurately.
  • Efficiency: The chosen data structure and algorithms should meet the specified O(log N) time complexity for operations and O(N) space complexity.
  • Code Structure and Readability: The code should be well-organized, easy to understand, and follow good software engineering practices.
  • Edge Case Handling: The solution should correctly handle edge cases such as single-element ranges, full-array ranges, and minimal/maximal driver counts.

Loading editor...