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 5-minute rolling average load | Databricks Coding Question

Quick Overview

This question evaluates understanding of sliding-window aggregation and efficient data-structure design for time-series event streams, focusing on computing a 5-minute rolling average load while managing performance and memory under high request volume.

Compute 5-minute rolling average load

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are building a monitoring component for a key–value (KV) store. Each request contributes **1 unit of load** at its request time. Design a data structure that supports the following operations efficiently: - `record(t)`: a request arrives at integer timestamp `t` (in seconds). Timestamps are non-decreasing across calls. - `avgLoad(t)`: return the **average load per second** over the last **5 minutes** ending at time `t`, i.e., over the interval `(t - 300, t]`. ### Requirements - Treat the time window as **exactly 300 seconds**. - If there are no requests in the window, return `0`. - `avgLoad(t)` should return a floating-point value: \[ \text{avg} = \frac{\#\text{requests in }(t-300, t]}{300} \] ### Example If requests were recorded at times `1, 2, 300, 301`: - `avgLoad(301) = 4 / 300` - `avgLoad(600) = 0 / 300 = 0` ### Constraints / Notes - The system may receive a large number of requests, so `avgLoad(t)` should be faster than scanning all historical events. - You may assume single-threaded access (no concurrency concerns).

Quick Answer: This question evaluates understanding of sliding-window aggregation and efficient data-structure design for time-series event streams, focusing on computing a 5-minute rolling average load while managing performance and memory under high request volume.

You are building a monitoring component for a key-value store. Each request contributes 1 unit of load at its request time. Implement a function that simulates two operations processed in order: - `record(t)`: a request arrives at integer timestamp `t`. - `avgLoad(t)`: return the average load per second over the last 5 minutes ending at time `t`, using the exact interval `(t - 300, t]`. Because this platform expects a single function, the operations are provided as two parallel arrays: - `ops[i]` is either `"record"` or `"avgLoad"` - `times[i]` is the timestamp for that operation Return a list containing the result of every `avgLoad` operation in the order they appear. Notes: - The window is exactly 300 seconds. - A request at time exactly `t - 300` does NOT count. - If there are no requests in the window, the average is `0.0`. - Timestamps are non-decreasing across all operations. - If multiple `record` operations happen at the same timestamp, each one counts separately.

Constraints

`0 <= len(ops) == len(times) <= 2 * 10^5`
`0 <= times[i] <= 10^9`
`times[i] <= times[i + 1]` for all valid `i`
`ops[i]` is either `"record"` or `"avgLoad"`

Examples

Input: (["record","record","record","record","avgLoad","avgLoad"], [10,20,300,301,301,600])

Expected Output: [0.013333333333333334, 0.0033333333333333335]

Explanation: At time 301, all requests at 10, 20, 300, and 301 are inside (1, 301], so the average is 4/300. At time 600, only the request at 301 is inside (300, 600], so the average is 1/300.

Input: (["avgLoad"], [100])

Expected Output: [0.0]

Explanation: No requests have been recorded, so the rolling average is 0.0.

Input: (["record","record","record","avgLoad","avgLoad"], [100,400,400,400,700])

Expected Output: [0.006666666666666667, 0.0]

Explanation: At time 400, the window is (100, 400], so the request at 100 is excluded and the two requests at 400 are counted: 2/300. At time 700, the window is (400, 700], so the requests at 400 are also excluded, giving 0.0.

Input: (["avgLoad","record","record","avgLoad","avgLoad","record","avgLoad"], [5,5,5,5,304,304,305])

Expected Output: [0.0, 0.006666666666666667, 0.006666666666666667, 0.0033333333333333335]

Explanation: Operations at the same timestamp are processed in order. The first query at 5 sees no requests. After two records at 5, the next query at 5 returns 2/300. The query at 304 still includes both requests at 5 because 5 is inside (4, 304]. After recording at 304, the query at 305 excludes time 5 and counts only time 304, giving 1/300.

Input: ([], [])

Expected Output: []

Explanation: There are no operations, so there are no `avgLoad` outputs.

Hints

Since the window size is fixed at exactly 300 seconds, think about storing counts per second in a fixed-size circular structure instead of keeping all history.
When you revisit the same bucket index, compare the stored timestamp with the current timestamp to decide whether to reset that bucket or add to it.

Quick Overview