Frontend School

Count Sensor Data Inversions

DSA
medium

Count Sensor Data Inversions

Medium
Divide and Conquer
Sorting
Arrays

Overview

Tesla's autonomous vehicles rely heavily on accurate sensor data. Detecting anomalies or unusual patterns in these data streams is crucial for safety and performance. An "inversion" in a sequence of sensor readings (e.g., temperature, pressure, or lidar returns) can indicate a temporary deviation from an expected trend, a potential sensor malfunction, or an unusual vehicle state that requires attention.

What you need to do / Task

Implement a function that efficiently counts the total number of inversions in a given array of sensor readings. An inversion is defined as a pair of indices (i, j) such that i < j but readings[i] > readings[j].

Input & output

  • readings: An array of numbers representing a sequence of sensor data points.
  • Return: A single integer representing the total count of inversions.

Clarifications

  • An empty array or an array with one element has 0 inversions.
  • The readings can be any non-negative number. Duplicate values are possible; readings[i] > readings[j] means strictly greater.

Examples

1

Example 1

Input:

readings = [1, 5, 2, 4, 3]

Output:

4

Note:

The inversions are (5 at index 1, 2 at index 2), (5 at index 1, 4 at index 3), (5 at index 1, 3 at index 4), and (4 at index 3, 3 at index 4).

2

Example 2

Input:

readings = [3, 1, 2]

Output:

2

Note:

The inversions are (3 at index 0, 1 at index 1) and (3 at index 0, 2 at index 2).

3

Example 3

Input:

readings = [1, 2, 3, 4, 5]

Output:

0

Note:

The array is already sorted, so there are no inversions.

Constraints

Constraints & assumptions

  • 1 <= readings.length <= 10^5
  • 0 <= readings[i] <= 10^9
  • The input array will only contain non-negative integers.

Out of scope

  • Handling non-numeric input.
  • Optimizing for memory beyond standard auxiliary array usage for merge sort.
  • Real-time processing or stream processing (assume batch processing for this problem).

What interviewers evaluate

  • Ability to identify and implement an efficient divide and conquer algorithm (O(N log N)).
  • Correctness in handling edge cases and array manipulations.
  • Clarity and organization of code.
  • Communication of algorithmic approach and complexity.

Loading editor...