Katkat
Back

Count Sensor Trios Within a Tolerance Band

IBMSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Count how many groups of three readings stay inside a tolerance band (max minus min within a limit). Tests sorting, a sliding window, combinatorial counting and handling of duplicates and large totals.

A greenhouse controller logs one temperature reading per sensor. Before it trusts an average, it wants to know how stable the readings are. For that it counts how many groups of three different sensors have readings that agree closely.

A trio is any set of three distinct indices i < j < k. A trio is stable when the highest of its three readings minus the lowest is less than or equal to tolerance.

Write a function that returns the number of stable trios.

def count_stable_trios(readings: list[int], tolerance: int) -> int: ...

Notes:

  • Trios are told apart by index, not by value. Two sensors with the same reading are still different sensors.
  • Equal readings are allowed in a trio. Their spread is 0.
  • A spread equal to tolerance counts as stable (the limit is inclusive).
  • With fewer than three readings the answer is 0.

Examples

readings  = [10, 14, 11, 19, 12], tolerance = 2
answer    = 1

Only the sensors reading 10, 11 and 12 qualify (spread 2). Any trio that includes 14 or 19 has a spread of at least 3.

readings  = [5, 5, 6, 5, 9], tolerance = 1
answer    = 4

The four sensors reading 5, 5, 6 and 5 all fall within 1 of each other, so any 3 of those 4 works: C(4, 3) = 4. The sensor reading 9 can't join any trio.

readings  = [3, 8], tolerance = 100
answer    = 0

Constraints

  • 0 <= len(readings) <= 10^5
  • 0 <= readings[i] <= 10^9, 0 <= tolerance <= 10^9
  • The answer can get close to C(10^5, 3), about 1.67 * 10^14. In a fixed-width language, use a 64-bit counter.
  • An O(n^3) or O(n^2) solution is too slow. Aim for O(n log n).

Hints

Hint 1

Being stable depends only on the multiset of values, not on where they sit. Can you reorder the array without changing the answer?

Hint 2

After sorting, decide that each trio is counted at the position of its largest element (its rightmost element in sorted order).

Hint 3

For a fixed right end r, every element from the leftmost index l with a[r] - a[l] <= tolerance up to r - 1 can be a partner. How many ways are there to pick two of them?

Hint 4

As r moves right, l never moves left, so a two-pointer sweep finds every l in O(n) total.

Follow-up questions

  • How would you count stable groups of size k instead of 3?
  • Now the readings arrive as a stream and the window is the last W readings. How would you maintain the count?
  • How would you return the stable trios themselves, and what does that cost in the worst case?
  • Suppose the condition were max - min >= tolerance instead. How do you reuse the same function?