Compute last-5-minute QPS in memory

Q: Compute last-5-minute QPS in memory

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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-ups

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)?

Compute last-5-minute QPS in memory

Quick Overview

Problem

Requirements / Constraints

Follow-ups

Comments (0)