Frontend School

Identify Missing Sensor IDs

DSA
easy

Identify Missing Sensor IDs

Easy
Arrays
Sorting
Searching
Two Pointers

Overview

In a distributed sensor network, each sensor reports its data with a unique, sequential ID. Occasionally, due to network issues or sensor malfunctions, some data packets (and thus their associated IDs) might be lost. To ensure data integrity and identify potential gaps, we need a mechanism to pinpoint which sensor IDs, within an expected range, were not received.

What you need to do / Task

Implement a function findMissingSensorIDs that takes a sorted array of unique sensor IDs that were successfully received, along with a lower and upper bound representing the full expected range of IDs. The function should return a new array containing all sensor IDs that are within the specified range but were not present in the received list, sorted in ascending order.

Input & output

Function Signature:

function findMissingSensorIDs(ids: number[], lowerBound: number, upperBound: number): number[]
  • ids: A number[] representing a list of unique sensor IDs that were successfully received. This array is guaranteed to be sorted in non-decreasing order.
  • lowerBound: A number indicating the minimum expected sensor ID in the range.
  • upperBound: A number indicating the maximum expected sensor ID in the range.

Return:

  • A number[] containing all IDs that are within [lowerBound, upperBound] but not present in ids. The returned array must also be sorted in ascending order.

Clarifications

  • The ids array is guaranteed to be sorted and contain unique elements.
  • lowerBound will always be less than or equal to upperBound.
  • The ids array may contain numbers outside the [lowerBound, upperBound] range. These numbers should be ignored when determining missing IDs.
  • An empty ids array means all numbers in the [lowerBound, upperBound] range are missing.

Examples

1

Example 1

Input:

ids = [0, 1, 3, 5, 7], lowerBound = 0, upperBound = 7

Output:

[2, 4, 6]

Note:

IDs 2, 4, and 6 are within the range [0, 7] but not present in the input list.

2

Example 2

Input:

ids = [], lowerBound = -5, upperBound = 0

Output:

[-5, -4, -3, -2, -1, 0]

Note:

Since no IDs were received, all IDs in the range [-5, 0] are considered missing.

3

Example 3

Input:

ids = [10, 20, 30], lowerBound = 15, upperBound = 25

Output:

[15, 16, 17, 18, 19, 21, 22, 23, 24, 25]

Note:

The range [15, 25] is partially covered by existing IDs, resulting in the identified missing ones.

Constraints

Constraints & assumptions

  • 0 <= ids.length <= 10^5
  • -10^9 <= ids[i], lowerBound, upperBound <= 10^9
  • ids is sorted in non-decreasing order.
  • ids contains unique elements.
  • lowerBound <= upperBound

Out of scope

  • Input validation (e.g., checking if ids is sorted or contains duplicates; assume constraints hold).

What interviewers evaluate

  • Correctness in handling various scenarios, including edge cases like empty input arrays or ranges that don't overlap with received IDs.
  • Optimal time complexity that leverages the sorted nature of the input ids array.
  • Efficient use of space, avoiding unnecessary auxiliary data structures.
  • Clarity and readability of the code, demonstrating good software engineering practices.

Loading editor...