How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Compute last-5-minute QPS in memory | Databricks Coding Question

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.

Input: [('getQPS', 50), ('getQPS', 350)]

Expected Output: [0.0, 0.0]

Explanation: Edge case: no requests were ever recorded.

Input: [('record', 10), ('record', 10), ('getQPS', 10), ('record', 310), ('getQPS', 310)]

Expected Output: [0.00667, 0.00333]

Explanation: At t=10 there are 2 requests in the window. At t=310, requests at 10 are exactly on the excluded boundary, so only timestamp 310 counts.

Hints

Keep only timestamps that can still belong to the current 5-minute window.
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.

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

Expected Output: [0.0, 0.0]

Explanation: Edge case: there are no requests.

Input: ([5, 5, 5], [])

Expected Output: []

Explanation: Edge case: there are no queries.

Hints

Use one pointer to expand the right side of the window and another to shrink the left side.
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].

Input: [('getQPS', 50), ('record', 350), ('getQPS', 350)]

Expected Output: [0.0, 0.00333]

Explanation: Edge case: first query happens before any request is recorded.

Input: [('record', 0), ('record', 299), ('record', 300), ('record', 599), ('getQPS', 599), ('getQPS', 600)]

Expected Output: [0.00667, 0.00333]

Explanation: At t=599, timestamps 300 and 599 count. At t=600, timestamp 300 is exactly on the excluded left boundary.

Hints

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

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.