Katkat
Back

Compute last-5-minute QPS in memory

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates design of in-memory data structures and sliding-window time-series aggregation for real-time metrics, testing understanding of space/time trade-offs, streaming algorithms, and handling monotonic timestamps.

Problem

You are building a lightweight in-memory component that tracks the query load (QPS) of a service.

Design a data structure with two operations:

  • record(timestamp) — called once per incoming request.
  • getQPS(timestamp) — returns the average QPS over the last 5 minutes ending at timestamp.

Define the QPS at time t as:

[ \text{QPS}(t) = \frac{#{\text{requests with } time \in (t-300,\ t] }}{300} ]

Requirements / Constraints

  • Timestamps are in seconds.
  • Calls to record and getQPS may be interleaved.
  • Assume timestamps are non-decreasing across calls.
  • Aim for efficient per-call time complexity.

Follow-up questions

  • How would you implement this using a **sliding window**?
  • How can you **reduce memory usage** while keeping performance good (e.g., avoid storing every request timestamp)?