Katkat
Back

Compute 5-minute rolling average load

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to maintain a rolling window average over a high-throughput stream of events using an efficient data structure that balances memory usage and query time complexity.

Problem Statement

You are building a monitoring service that receives a stream of load metrics. Each metric is a tuple (timestamp, load_value), where timestamp is an integer representing the time in seconds. Your task is to design a class RollingLoadTracker that computes the average system load over a 5-minute (300-second) rolling window.

Implement the following methods:

  1. record_metric(timestamp, load_value): Adds a new metric to the tracker. Note that metrics may arrive slightly out of chronological order, but will always be within a reasonable buffer (e.g., within 60 seconds of the latest timestamp received so far).
  2. get_average_load(current_timestamp): Returns the average load for the window [current_timestamp - 300, current_timestamp]. If no metrics exist within the window, return 0.

Constraints

  • timestamp is a positive integer.
  • Total number of metrics $N$ can be up to $1,000,000$.
  • The solution should optimize for query performance; ideally, get_average_load should be better than $O(N)$ per call.

Example

tracker = RollingLoadTracker()
tracker.record_metric(100, 10)
tracker.record_metric(200, 20)
tracker.record_metric(450, 30)

# Window for 500 is [200, 500]. Metrics included: (200, 20), (450, 30)
print(tracker.get_average_load(500)) # Output: 25.0

Edge Cases

  • Empty tracker.
  • Metrics arriving significantly before or after the 5-minute window.
  • Multiple metrics with the same timestamp.

Hints

Hint 1

Consider using a data structure that keeps metrics ordered by time, such as a double-ended queue or a sorted list.

Hint 2

Since you need to calculate an average, you can maintain a running sum of `load_value` and a count of metrics within the window to achieve O(1) average calculation after identifying expired metrics.

Hint 3

For out-of-order metrics, a simple queue might not suffice; consider using a balanced BST or a `collections.deque` combined with a sorting mechanism if you can assume the out-of-order jitter is bounded.

Follow-up questions

  • How would you modify your implementation if you needed to calculate the rolling 99th percentile of load instead of the average?
  • If the stream is massive and distributed across multiple servers, how would you aggregate the results without sending all individual metrics to a central node?
  • How does your solution handle memory if the application runs for months and the number of metrics per second is extremely high?