Katkat
Back

Implement alert queries and spike detection

LinkedInMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process a stream of events with time-based constraints, requiring an efficient sliding-window approach and the use of monotonic data structures for spike detection.

Problem Statement

You are building an alerting system that monitors a high-throughput stream of numerical metrics. You need to implement a class AlertSystem that tracks the last k seconds of data and triggers an alert if the current metric is significantly higher than previous values.

Define the class AlertSystem with the following methods:

  1. record(timestamp, value): Records a metric value at a specific integer timestamp (in seconds).
  2. get_spike_count(window_size): Returns the number of events within the last window_size seconds that are strictly smaller than the current (most recent) metric.

Constraints

  • Timestamps arrive in non-decreasing order.
  • window_size is an integer representing the lookback period in seconds.
  • The system must handle frequent record calls efficiently.

Example

# Timeline: (t=1, v=10), (t=2, v=5), (t=3, v=12), (t=4, v=8), (t=5, v=15)

sys = AlertSystem()
sys.record(1, 10)
sys.record(2, 5)
sys.record(3, 12)
sys.record(4, 8)
sys.record(5, 15)

# For get_spike_count(3): 
# Look at events in the last 3 seconds (t=3, 4, 5). 
# Values: [12, 8, 15]. 
# 12 < 15 and 8 < 15. Count = 2.
print(sys.get_spike_count(3)) # Output: 2

Edge Cases

  • window_size larger than the total duration of recorded events.
  • Multiple events occurring at the same timestamp.
  • Empty history.

Hints

Hint 1

Use a Deque or a list of tuples to store events in a way that allows efficient removal of outdated entries.

Hint 2

Since you only care about events within the last 'window_size', consider using a two-pointer approach or binary search on the recorded history to isolate the relevant time slice.

Hint 3

If the number of calls to 'record' is massive, consider how you might maintain a sorted window or an auxiliary structure to avoid re-scanning the history for every 'get_spike_count' call.

Follow-up questions

  • How would you modify this solution if the timestamps arrived out-of-order?
  • What data structure would you use if we needed to calculate the 'moving average' of the window in O(1) time?
  • How would you scale this system to handle millions of events per second across multiple distributed nodes?