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 Onsite rounds at Databricks.

What role is this question designed for?

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

Implement a rate-limited hit counter | Databricks Coding Question

Q: Implement a rate-limited hit counter

This question evaluates a candidate's understanding of designing efficient time-windowed data structures and algorithmic analysis, including space-time trade-offs and amortized complexity.

Implement a rate-limited hit counter

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are designing a hit counter that records the number of hits received in the past 5 minutes. Implement a class `HitCounter` with the following methods: - `void hit(int timestamp)`: Records a hit at the given `timestamp` (in seconds). The timestamp is given in seconds granularity and is strictly increasing across all calls. - `int getHits(int timestamp)`: Returns the number of hits received in the past 5 minutes (i.e., the past 300 seconds) including the current second, at the given `timestamp`. Constraints: - `1 <= timestamp <= 10^9`. - Methods will be called in non-decreasing order of `timestamp`. - The number of calls to both `hit` and `getHits` is up to 10^5. Describe the data structures and algorithms you would use to implement `HitCounter` so that both operations are efficient in time and memory. Do not write code; just specify the design and complexity.

Quick Answer: This question evaluates a candidate's understanding of designing efficient time-windowed data structures and algorithmic analysis, including space-time trade-offs and amortized complexity.

You are given two arrays, operations and timestamps, that simulate calls to a HitCounter class. Each operation is one of: - "hit": record one hit at the given timestamp - "getHits": return the number of hits received in the past 5 minutes (300 seconds), including the current second The timestamps are given in non-decreasing order. A hit at time t should be counted by getHits(x) if and only if x - 299 <= t <= x. Implement solution(operations, timestamps) and return a list containing the answers for every "getHits" operation in order. To solve this efficiently, design your data structure so that old hits can be removed as time moves forward without scanning the full history each time.

Constraints

0 <= len(operations) <= 10^5
len(operations) == len(timestamps)
operations[i] is either "hit" or "getHits"
1 <= timestamps[i] <= 10^9 when the input is non-empty
timestamps is in non-decreasing order

Examples

Input: (["hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"], [1, 2, 3, 4, 300, 300, 301])

Expected Output: [3, 4, 3]

Explanation: At time 4, the three earlier hits are counted. At time 300, hits at 1, 2, 3, and 300 are all within [1, 300]. At time 301, the hit at 1 expires, so only hits at 2, 3, and 300 remain.

Input: (["hit", "hit", "hit", "getHits", "hit", "getHits"], [1, 1, 1, 1, 300, 300])

Expected Output: [3, 4]

Explanation: Three hits happen at the same second, so getHits(1) returns 3. At time 300, the window is [1, 300], so those three hits plus the hit at 300 are counted.

Input: (["hit", "hit", "getHits", "getHits", "hit", "getHits"], [1, 300, 300, 301, 601, 601])

Expected Output: [2, 1, 1]

Explanation: At time 300, both hits at 1 and 300 are included. At time 301, the hit at 1 is outside [2, 301]. At time 601, the hit at 300 has also expired, leaving only the hit at 601.

Input: (["getHits", "hit", "getHits"], [10, 10, 10])

Expected Output: [0, 1]

Explanation: Before any hit is recorded, getHits returns 0. After recording one hit at time 10, getHits(10) returns 1.

Input: ([], [])

Expected Output: []

Explanation: With no operations, there are no getHits results to return.

Solution

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

    if len(operations) != len(timestamps):
        raise ValueError('operations and timestamps must have the same length')

    window = deque()  # (timestamp, count_at_that_second)
    total = 0
    answers = []

    for op, ts in zip(operations, timestamps):
        # Keep only hits in [ts - 299, ts]
        while window and window[0][0] <= ts - 300:
            old_ts, old_count = window.popleft()
            total -= old_count

        if op == 'hit':
            if window and window[-1][0] == ts:
                last_ts, last_count = window[-1]
                window[-1] = (last_ts, last_count + 1)
            else:
                window.append((ts, 1))
            total += 1
        elif op == 'getHits':
            answers.append(total)
        else:
            raise ValueError('invalid operation: ' + str(op))

    return answers

Time complexity: O(n) total, where n is the number of operations. Space complexity: O(min(n, 300)).

Hints

Because timestamps never decrease, expired hits will always be removed from the oldest side first.
Instead of storing every hit separately, group hits by timestamp and keep a running total of hits currently in the 300-second window.

Quick Overview

This question evaluates a candidate's understanding of designing efficient time-windowed data structures and algorithmic analysis, including space-time trade-offs and amortized complexity.