Katkat
Back

Design In-Memory QPS Counter

DatabricksMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates the ability to design and implement an in-memory time-series counter and sliding-window aggregation, emphasizing efficient data structures, handling high-frequency events, and memory-time trade-offs.

Implement an in-memory traffic counter.

You need to support two operations for each logical key, such as an endpoint, customer, or service name:

  • record(key, timestamp): a request for key happened at timestamp.
  • get_qps(key, now): return the average queries per second for key over the last 5 minutes, using the time window [now - 299, now].

Requirements:

  • All data must be stored in memory.
  • Timestamps are integer seconds.
  • Multiple requests may arrive with the same key and the same timestamp.
  • Start with a working solution for a 5-minute sliding window.

Follow-up discussion:

  1. How would you reduce memory usage?
  2. How would you extend the design to support a 24-hour window?
  3. How would you efficiently handle many requests that share the same timestamp?

Assume calls arrive in non-decreasing timestamp order.