Katkat
Back

Implement a Streaming VMStat Alert

MetaSite Reliability Engineer · Technical Screen
MediumSite Reliability EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to design a memory-efficient sliding window mechanism for monitoring high-frequency system metrics in real-time.

Problem Statement

You are building a real-time monitoring agent for a virtual machine. You need to implement a class MetricMonitor that tracks the average system CPU usage over a sliding window of the last K seconds.

Your system receives a stream of events, where each event is a tuple (timestamp, cpu_usage). The timestamp is an integer representing seconds, and cpu_usage is a float. You must implement the following methods:

  1. record_metric(timestamp, cpu_usage): Ingests a new metric point. You can assume timestamps are provided in non-decreasing order.
  2. get_average(): Returns the moving average of CPU usage for all data points that fall within the interval [current_time - K + 1, current_time], where current_time is the timestamp of the most recent record.

Constraints

  • K (window size) is a positive integer.
  • Total number of events N can be very large; efficiency is critical.
  • Minimize memory usage; do not store every individual metric if you can aggregate them by timestamp.

Examples

# K = 3
monitor = MetricMonitor(3)
monitor.record_metric(10, 50.0)
monitor.record_metric(11, 60.0)
monitor.record_metric(12, 70.0)
print(monitor.get_average()) # (50+60+70)/3 = 60.0

monitor.record_metric(13, 80.0)
# Window is now [11, 13]: (60+70+80)/3 = 70.0
print(monitor.get_average())

Edge Cases

  • Multiple metrics recorded for the same timestamp.
  • Large gaps between timestamps where no data is recorded.
  • get_average called before any metrics are recorded (return 0.0).

Hints

Hint 1

Use a double-ended queue (deque) to store aggregated metrics per second, keeping track of the sum and count within the window.

Hint 2

When a new metric arrives, remove all entries from the front of the queue that fall outside the window defined by `[latest_timestamp - K + 1, latest_timestamp]`.

Hint 3

Consider storing tuples of `(timestamp, sum_of_usage, count_of_entries)` in your queue to handle multiple updates per second efficiently.

Follow-up questions

  • How would you modify this implementation to track the 95th percentile of CPU usage instead of the average?
  • If the stream was distributed across multiple machines, how would you aggregate the metrics centrally?
  • What impact does the choice of `K` have on the memory footprint of your solution, and how could you optimize for very large `K`?