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

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.

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])

Loading coding console...

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

Quick Overview

Implement a rate-limited hit counter

Constraints

Examples

Solution

Hints