Frontend School

Autonomous Driving Sensor Reliability Analysis

DSA
medium

Autonomous Driving Sensor Reliability Analysis

Medium
Segment Tree
Data Structures
Range Query

Overview

In Tesla's autonomous driving systems, a vast array of sensors constantly monitor the vehicle's surroundings. The reliability of these sensors is paramount for safe and effective operation. As the vehicle traverses a route, different road segments might expose sensors to varying conditions, affecting their performance. It's crucial to quickly assess the weakest link in sensor reliability over any given sub-route to make informed decisions, such as adjusting driving behavior or triggering recalibration.

What you need to do / Task

You are tasked with implementing a system to efficiently manage and query sensor reliability scores along a predefined route. The route is divided into n discrete segments, each with an initial sensor reliability score. You will need to process a series of operations:

  1. Update: A sensor on a specific segment index undergoes recalibration, and its reliability score changes to a newValue.
  2. Query: Determine the minimum sensor reliability score over a continuous range of segments [L, R] (inclusive).

Your solution should provide fast responses to both update and query operations.

Input & output

Function Signature: function processSensorOperations(n: number, initialReliabilities: number[], operations: [string, number, number][]): number[]

  • n: An integer representing the total number of segments in the route. Segments are indexed from 0 to n-1.
  • initialReliabilities: An array of n integers, where initialReliabilities[i] is the initial reliability score for segment i.
  • operations: An array of operations to perform. Each operation is an array of three elements:
    • ["update", index, newValue]: Update the reliability score of segment index to newValue.
    • ["query", L, R]: Query the minimum reliability score within the range of segments [L, R] (inclusive).
  • Return Value: An array of integers, containing the results of all "query" operations, in the order they appear in the operations array.

Clarifications

  • Segment indices L, R, and index are 0-based.
  • For query operations [L, R], it is guaranteed that 0 <= L <= R < n.
  • For update operations [index, newValue], it is guaranteed that 0 <= index < n.
  • The initialReliabilities array will always have n elements.
  • Reliability scores are always non-negative integers.

Examples

1

Example 1

Input:

n = 5, initialReliabilities = [10, 20, 5, 15, 30], operations = [["query", 0, 4], ["update", 2, 12], ["query", 1, 3], ["query", 0, 1]]

Output:

[5, 12, 10]

Note:

Initial: [10, 20, 5, 15, 30]

  1. Query [0, 4]: min is 5 (at index 2).
  2. Update index 2 to 12. Array becomes [10, 20, 12, 15, 30].
  3. Query [1, 3]: min is 12 (at index 2).
  4. Query [0, 1]: min is 10 (at index 0).
2

Example 2

Input:

n = 3, initialReliabilities = [100, 50, 200], operations = [["query", 0, 0], ["update", 0, 40], ["query", 0, 2], ["update", 1, 30], ["query", 1, 1]]

Output:

[100, 40, 30]

Note:

Initial: [100, 50, 200]

  1. Query [0, 0]: min is 100.
  2. Update index 0 to 40. Array becomes [40, 50, 200].
  3. Query [0, 2]: min is 40 (at index 0).
  4. Update index 1 to 30. Array becomes [40, 30, 200].
  5. Query [1, 1]: min is 30.
3

Example 3

Input:

n = 1, initialReliabilities = [75], operations = [["query", 0, 0], ["update", 0, 90], ["query", 0, 0]]

Output:

[75, 90]

Note:

Initial: [75]

  1. Query [0, 0]: min is 75.
  2. Update index 0 to 90. Array becomes [90].
  3. Query [0, 0]: min is 90.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 0 <= initialReliabilities[i] <= 10^9 for all i
  • 0 <= newValue <= 10^9 for update operations
  • 1 <= operations.length <= 10^5
  • 0 <= L <= R < n for query operations
  • 0 <= index < n for update operations
  • It is assumed that all input parameters will be valid and adhere to these constraints.

Out of scope

  • Handling invalid input formats or out-of-bounds indices (assume valid inputs).
  • Implementing persistent data structures (a mutable segment tree is sufficient).
  • Complex range updates (e.g., adding a value to a range); only point updates are required.

What interviewers evaluate

  • Correctness: The solution must correctly implement minimum range queries and point updates.
  • Efficiency: The implementation should achieve optimal time complexity (O(log N) per operation) and space complexity (O(N) total).
  • Code Quality: Clarity, readability, and logical structure of the code, including proper variable naming and function decomposition.
  • Segment Tree Understanding: Demonstrated understanding of Segment Tree construction, query, and update mechanisms.

Loading editor...