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

What role is this question designed for?

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

Implement sliding-window timestamped average

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Implement a class that maintains a time-based sliding window of records and can return the average score within the current window. ### Requirements - The class is initialized with an integer `window_size` (a duration in the same units as `timestamp`, e.g., seconds). - Each record is a pair `(timestamp, score)`. - The class exposes two methods: 1. `insert_record(timestamp, score)`: insert a new record. 2. `get_average(current_time)`: return the average of all `score` values whose `timestamp` is within the current window. ### Window definition At any operation time `T` (i.e., during `insert_record` or `get_average`), records are considered **valid** if: - `timestamp` is in the range `[T - window_size, T]` (inclusive), and - any record older than `T - window_size` must be evicted before proceeding. ### Additional notes / assumptions - `get_average` should return a sensible value when there are no valid records (define behavior, e.g., return `0` or `null`). - Timestamps may be non-decreasing across calls (state and use this assumption if needed), or you may design to handle out-of-order timestamps. ### Deliverables Describe/implement the class and its methods with appropriate time and space complexity considerations.

Quick Answer: This question evaluates understanding of time-based sliding-window data structures, streaming aggregation, and the handling of timestamped records with efficient incremental updates and evictions.

Implement the behavior of a class that maintains a time-based sliding window of records. Each record is a pair (timestamp, score). On this platform, instead of writing a class directly, implement a function solution(window_size, operations) that processes operations in order and returns the results of all average queries.\n\nEach operation is one of:\n- ("insert", timestamp, score): Before inserting, evict every record with timestamp < timestamp - window_size. Then insert the new record.\n- ("get", current_time): Before answering, evict every record with timestamp < current_time - window_size. Then return the average of all scores whose timestamps are in [current_time - window_size, current_time].\n\nIf no records are valid during a get operation, return 0 for that query.\n\nAssume operation times are non-decreasing across the entire operations list.

Constraints

0 <= len(operations) <= 2 * 10^5
0 <= window_size <= 10^9
Operation times are non-decreasing across all operations
-10^9 <= score <= 10^9
All timestamps and current_time values are integers

Examples

Input: (10, [('insert', 1, 4), ('insert', 5, 8), ('get', 5), ('insert', 12, 6), ('get', 12)])

Expected Output: [6.0, 7.0]

Explanation: At time 5, both records 4 and 8 are inside the window, so the average is 6.0. Before inserting at time 12, the record at time 1 is evicted because 1 < 12 - 10. The remaining scores are 8 and 6, so the average at time 12 is 7.0.

Input: (3, [('insert', 1, 5), ('insert', 3, 7), ('get', 3), ('insert', 6, 9), ('get', 6)])

Expected Output: [6.0, 8.0]

Explanation: At time 3, both scores 5 and 7 are valid, so the average is 6.0. Before inserting at time 6, the score at time 1 is evicted because 1 < 6 - 3. Then scores 7 and 9 remain, giving an average of 8.0.

Input: (5, [('insert', 0, 10), ('insert', 5, 20), ('get', 5), ('get', 6)])

Expected Output: [15.0, 20.0]

Explanation: This checks the boundary condition. At time 5, timestamps in [0, 5] are valid, so both 10 and 20 are included. At time 6, the valid range is [1, 6], so the record at timestamp 0 is evicted and only 20 remains.

Input: (4, [('get', 0), ('insert', 2, 10), ('get', 2), ('get', 7)])

Expected Output: [0, 10.0, 0]

Explanation: The first query has no records, so it returns 0. At time 2, the only record is 10. By time 7, that record is too old because 2 < 7 - 4, so the final query again returns 0.

Input: (2, [('insert', 1, -2), ('insert', 1, 8), ('insert', 3, 6), ('get', 3), ('get', 4)])

Expected Output: [4.0, 6.0]

Explanation: When querying at time 3, the valid range is [1, 3], so all three scores -2, 8, and 6 are included, giving 12 / 3 = 4.0. At time 4, the valid range is [2, 4], so both timestamp-1 records are evicted and only 6 remains.

Solution

def solution(window_size, operations):
    from collections import deque

    window = deque()
    running_sum = 0
    result = []

    def evict(cutoff):
        nonlocal running_sum
        while window and window[0][0] < cutoff:
            _, score = window.popleft()
            running_sum -= score

    for op in operations:
        if op[0] == 'insert':
            _, timestamp, score = op
            evict(timestamp - window_size)
            window.append((timestamp, score))
            running_sum += score
        elif op[0] == 'get':
            _, current_time = op
            evict(current_time - window_size)
            if window:
                result.append(running_sum / len(window))
            else:
                result.append(0)
        else:
            raise ValueError('Unknown operation: {}'.format(op[0]))

    return result

Time complexity: O(n), where n is the number of operations. Space complexity: O(k), where k is the number of records currently in the window at its largest size (O(n) worst-case).

Hints

Because operation times never go backward, once a record expires it will never become valid again.
Use a FIFO structure to store active records and keep a running sum so each get query can be answered in O(1) amortized time after evictions.

Quick Overview

This question evaluates understanding of time-based sliding-window data structures, streaming aggregation, and the handling of timestamped records with efficient incremental updates and evictions.