Quick Overview

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.

Compute last-5-minute QPS in memory

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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 1. How would you implement this using a **sliding window**? 2. How can you **reduce memory usage** while keeping performance good (e.g., avoid storing every request timestamp)?

Quick Answer: 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.

Part 1: Online In-Memory QPS Tracker

You are given a sequence of interleaved operations for an in-memory request tracker. Each operation is either ('record', timestamp), meaning one request arrived at that second, or ('getQPS', timestamp), meaning you must return the average QPS over the last 5 minutes ending at that timestamp. For a query time t, count all recorded requests with timestamps in the interval (t-300, t], then divide by 300. Timestamps are integers in seconds and are non-decreasing across all operations. Return the answers for all getQPS operations in order, rounded to 5 decimal places.

Constraints

  • 0 <= len(operations) <= 200000
  • 0 <= timestamp <= 10^9
  • Timestamps are non-decreasing across all operations
  • Each 'record' operation represents exactly one request
  • QPS(t) = count of requests in (t-300, t] / 300

Examples

Input: [('record', 1), ('record', 2), ('record', 300), ('getQPS', 300), ('getQPS', 301)]

Expected Output: [0.01, 0.00667]

Explanation: At t=300, requests in (0,300] are 1,2,300 => 3/300 = 0.01. At t=301, request 1 falls out, so 2/300 = 0.00667.

Input: [('record', 100), ('record', 100), ('record', 400), ('getQPS', 400), ('getQPS', 401)]

Expected Output: [0.00333, 0.00333]

Explanation: At t=400, timestamps equal to 100 are excluded because the window is open on the left: (100,400]. Only timestamp 400 counts.

Hints

  1. Keep only timestamps that can still belong to the current 5-minute window.
  2. A deque works well because old requests leave from the front and new requests arrive at the back.

Part 2: Last-5-Minute QPS with a Sliding Window

You are given two sorted arrays: - requests[i]: the timestamp of the i-th request - queries[j]: a time at which you must compute the average QPS For each query time t, compute: QPS(t) = (# of requests with timestamp in (t-300, t]) / 300 Both arrays are non-decreasing. Return the QPS for every query in order, rounded to 5 decimal places. Your goal is to do this efficiently using a sliding window instead of scanning all requests for every query.

Constraints

  • 0 <= len(requests), len(queries) <= 200000
  • 0 <= requests[i], queries[j] <= 10^9
  • requests is sorted in non-decreasing order
  • queries is sorted in non-decreasing order
  • QPS(t) = count of requests in (t-300, t] / 300

Examples

Input: ([1, 2, 300], [300, 301])

Expected Output: [0.01, 0.00667]

Explanation: At t=300 all three requests count. At t=301, timestamp 1 falls outside the window.

Input: ([100, 100, 400], [399, 400, 700])

Expected Output: [0.00667, 0.00333, 0.0]

Explanation: At t=399 both 100s count. At t=400 they are excluded because the left boundary is open. At t=700, timestamp 400 is also excluded.

Hints

  1. Use one pointer to expand the right side of the window and another to shrink the left side.
  2. Because queries are sorted, both pointers only move forward.

Part 3: Memory-Optimized QPS Tracker with 300 Buckets

Implement the same online QPS tracker as in Part 1, but under a stricter memory goal: do not store every request timestamp. You are given interleaved operations: - ('record', timestamp): record one request at that second - ('getQPS', timestamp): return average QPS over the interval (timestamp-300, timestamp] Timestamps are integer seconds and are non-decreasing across all operations. Because the window is exactly 300 seconds wide, design a solution that uses only O(300) extra memory by aggregating requests per second. Return answers for all getQPS operations in order, rounded to 5 decimal places.

Constraints

  • 0 <= len(operations) <= 200000
  • 0 <= timestamp <= 10^9
  • Timestamps are non-decreasing across all operations
  • Use only O(300) extra memory
  • QPS(t) = count of requests in (t-300, t] / 300

Examples

Input: [('record', 1), ('record', 2), ('record', 300), ('getQPS', 300), ('getQPS', 301)]

Expected Output: [0.01, 0.00667]

Explanation: This matches the basic definition of QPS over the last 300 seconds.

Input: [('record', 100), ('record', 100), ('record', 400), ('getQPS', 400), ('getQPS', 401)]

Expected Output: [0.00333, 0.00333]

Explanation: The two requests at time 100 are excluded at t=400 because the interval is (100,400].

Hints

  1. Since timestamps are whole seconds, at most 300 distinct second-values can matter for any query.
  2. Use index = timestamp % 300, but also store the absolute timestamp in each bucket so you can tell whether a bucket is stale.

Loading coding console...