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 Decagon.

What role is this question designed for?

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

Design Sliding-Window Average Tracker | Decagon Coding Question

Design Sliding-Window Average Tracker

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a class that tracks records in a sliding time window. Implement the following API: - `init(time_window)`: initialize the object with a window size. - `insert(record_id, value, timestamp)`: insert a new record. - `get_avg(timestamp)`: return the average `value` of all records whose timestamps fall within the most recent `time_window` ending at `timestamp`. Assumptions and requirements: - `record_id` is unique for each inserted record. - Timestamps are integers. - Calls to `insert(...)` and `get_avg(...)` are made with non-decreasing timestamps. - A record is considered active at time `t` if its timestamp is in the interval `[t - time_window + 1, t]`. - If no records are active in the window, return `0`. - The implementation should be optimized for the monotonic-timestamp constraint. Follow-up: - Support `update(record_id, new_timestamp)`, which changes the timestamp of an existing record while keeping its original value unchanged. - Explain how your design would change if inserts and queries could arrive with out-of-order timestamps.

Quick Answer: This question evaluates design and implementation of a time-windowed tracking data structure, focusing on streaming aggregation, handling monotonic timestamps, efficient updates, and time/space trade-offs.

Part 1: Implement Sliding-Window Average Tracker with Monotonic Timestamps

Design the core behavior of a sliding-window average tracker. You are given a fixed integer time_window and a sequence of API calls. Each insert adds a unique record_id with an integer value and timestamp. Each get_avg query asks for the average value of all currently inserted records whose timestamps are in the inclusive interval [timestamp - time_window + 1, timestamp]. Calls are made with non-decreasing timestamps, so the solution should take advantage of this monotonicity. If no records are active, return 0.0.

Constraints

1 <= time_window <= 10^9
0 <= len(operations) <= 2 * 10^5
record_id is unique for each insert operation
-10^9 <= value <= 10^9
-10^9 <= timestamp <= 10^9
The timestamps of insert and get_avg calls are non-decreasing across operations

Examples

Input: (3, [[1, 101, 10, 1], [1, 102, 20, 2], [2, 3], [1, 103, 30, 4], [2, 4], [2, 5]])

Expected Output: [15.0, 25.0, 30.0]

Explanation: At time 3 records at timestamps 1 and 2 are active. At time 4, timestamp 1 expires and records 2 and 4 are active. At time 5, only timestamp 4 remains active.

Input: (2, [[2, 1], [1, 1, 5, 3], [2, 5], [2, 6]])

Expected Output: [0.0, 0.0, 0.0]

Explanation: The first query has no records. The inserted record at timestamp 3 is outside the windows ending at 5 and 6.

Input: (4, [[1, 1, 7, 10], [2, 13], [2, 14]])

Expected Output: [7.0, 0.0]

Explanation: The window ending at 13 is [10, 13], so the record is included. The window ending at 14 is [11, 14], so it is excluded.

Input: (1, [[1, 1, 4, 5], [1, 2, 6, 5], [2, 5], [2, 6]])

Expected Output: [5.0, 0.0]

Explanation: With window size 1, only records exactly at the query timestamp are active. Both timestamp-5 records are active at time 5 and expired at time 6.

Hints

Because timestamps never go backwards, once a record expires it can never become active again.
Keep a queue of records ordered by timestamp and maintain a running sum of active values.

Part 2: Sliding-Window Average Tracker with Timestamp Updates

Extend the sliding-window average tracker to support timestamp updates. You are given a fixed integer time_window and a sequence of operations. Insert creates a record with a unique record_id, value, and timestamp. Update changes the timestamp of an existing record while preserving its original value. Query get_avg returns the average value of all current records whose current timestamps are in the inclusive interval [timestamp - time_window + 1, timestamp]. If no current records are active, return 0.0.

Constraints

1 <= time_window <= 10^9
0 <= len(operations) <= 2 * 10^5
record_id is unique for each insert operation
Every update refers to an existing record_id
-10^9 <= value <= 10^9
-10^9 <= timestamp, new_timestamp <= 10^9

Examples

Input: (3, [[1, 1, 10, 1], [1, 2, 30, 2], [2, 3], [3, 1, 10], [2, 3], [2, 10]])

Expected Output: [20.0, 30.0, 10.0]

Explanation: Initially both records are active at time 3. After record 1 moves to timestamp 10, only record 2 is active at time 3, and only record 1 is active at time 10.

Input: (4, [[1, 1, 8, 10], [2, 13], [2, 14], [3, 1, 14], [2, 14]])

Expected Output: [8.0, 0.0, 8.0]

Explanation: The record at timestamp 10 is included in [10, 13] but excluded from [11, 14]. After updating it to timestamp 14, it is included again.

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

Expected Output: [0.0]

Explanation: Edge case: querying with no records returns 0.0.

Input: (2, [[1, 1, 10, 1], [1, 2, 20, 3], [2, 3], [3, 1, 3], [2, 3]])

Expected Output: [20.0, 15.0]

Explanation: Before the update, only record 2 is active in [2, 3]. After moving record 1 to timestamp 3, both records are active.

Hints

A simple queue is no longer enough because an updated record may move to a different timestamp position.
Maintain counts and sums indexed by timestamp; an update is a removal at the old timestamp plus an insertion at the new timestamp.

Part 3: Sliding-Window Average Tracker with Out-of-Order Timestamps

Adapt the sliding-window average tracker for inserts and queries whose timestamps may arrive out of order. You are given a fixed integer time_window and a sequence of operations. Insert adds a unique record_id with a value and timestamp. Query get_avg returns the average value among records inserted by earlier operations whose timestamps are in the inclusive interval [timestamp - time_window + 1, timestamp]. Unlike the monotonic version, operation timestamps are arbitrary, so an expired record at one query time may become relevant again for a later query with an earlier timestamp.

Constraints

1 <= time_window <= 10^9
0 <= len(operations) <= 2 * 10^5
record_id is unique for each insert operation
-10^9 <= value <= 10^9
-10^9 <= timestamp <= 10^9
Insert and query timestamps may appear in any order

Examples

Input: (3, [[1, 1, 10, 10], [2, 10], [1, 2, 20, 8], [2, 10], [2, 7]])

Expected Output: [10.0, 15.0, 0.0]

Explanation: The second insert has an older timestamp than the previous query. It contributes to the later query at time 10, but not to the query at time 7.

Input: (5, [[1, 1, 100, 50], [2, 10], [2, 52]])

Expected Output: [0.0, 100.0]

Explanation: A record with timestamp 50 is not active for a query ending at 10, but is active for a query ending at 52.

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

Expected Output: [0.0]

Explanation: Edge case: querying before any insert returns 0.0.

Input: (4, [[1, 1, 5, -2], [1, 2, 7, 1], [2, 1], [2, 2]])

Expected Output: [6.0, 7.0]

Explanation: Negative timestamps are handled normally. The window ending at 1 is [-2, 1], while the window ending at 2 is [-1, 2].

Input: (1, [[1, 1, 3, 4], [1, 2, 9, 4], [2, 4], [2, 5]])

Expected Output: [6.0, 0.0]

Explanation: With window size 1, both timestamp-4 records are active only for the query ending at 4.

Hints

The queue-based monotonic solution fails because records cannot be permanently discarded based on one query timestamp.
Think of each insert as adding a point on a timestamp axis, and each query as asking for count and sum over a timestamp interval.

Quick Overview

This question evaluates design and implementation of a time-windowed tracking data structure, focusing on streaming aggregation, handling monotonic timestamps, efficient updates, and time/space trade-offs.