Quick Overview

This question evaluates understanding of time-based data structures and algorithms for sliding-window counters, including fixed-size array bucketing, handling timestamp collisions within buckets, refactoring for reuse, and time/space complexity analysis.

Implement a sliding-window hit counter

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a hit counter that supports recordHit(timestamp) and getHits(pastSeconds). Use a fixed-size array to maintain a sliding time window (e.g., last 300 seconds) so each operation is O( 1) and memory is bounded. Explain how you handle timestamp collisions within buckets, generalize to arbitrary window sizes, refactor for reusability, and compare trade-offs versus alternatives (queue, deque, hashmap with buckets). Analyze time and space complexity.

Quick Answer: This question evaluates understanding of time-based data structures and algorithms for sliding-window counters, including fixed-size array bucketing, handling timestamp collisions within buckets, refactoring for reuse, and time/space complexity analysis.

Design a reusable hit counter backed by a fixed-size circular array. You are given a maximum window size in seconds and a sequence of operations. Each operation is either ('hit', t), which records one hit at integer timestamp t, or ('get', t, past_seconds), which asks for the number of hits whose timestamps fall in the inclusive range [t - past_seconds + 1, t]. Use a fixed-size array of length window_size so memory stays bounded. Because different timestamps can map to the same bucket, each bucket must store both the latest timestamp written there and the count for that timestamp. When a bucket is reused for a newer timestamp, any stale count in that bucket must be overwritten. Return a list containing the answers to all 'get' operations in order. Assume timestamps across the full operation list are non-decreasing, and every query satisfies 1 <= past_seconds <= window_size.

Constraints

  • 1 <= window_size <= 10^5
  • 0 <= len(operations) <= 2 * 10^5
  • Timestamps are non-decreasing across all operations
  • For every ('get', t, past_seconds), 1 <= past_seconds <= window_size
  • There may be multiple hits at the same timestamp

Examples

Input: (5, [('hit', 1), ('hit', 2), ('hit', 2), ('get', 2, 2), ('get', 5, 5), ('hit', 7), ('get', 7, 5), ('get', 7, 1)])

Expected Output: [3, 3, 1, 1]

Explanation: Hits occur at times 1, 2, and 2. At t=2 over the last 2 seconds, all 3 hits count. At t=5 over the last 5 seconds, those same 3 hits still count. Recording a hit at 7 reuses the bucket for timestamp 2, but the old value is stale and is overwritten. At t=7, only the hit at 7 is inside the last 5 seconds and the last 1 second.

Input: (3, [('get', 1, 1), ('hit', 1), ('hit', 1), ('get', 1, 1), ('get', 3, 3), ('hit', 4), ('get', 4, 3)])

Expected Output: [0, 2, 2, 1]

Explanation: The first query happens before any hits, so it returns 0. Two hits are recorded at timestamp 1. They are both counted at t=1 for the last second and at t=3 for the last 3 seconds. After a hit at 4, only that new hit remains inside the range [2, 4].

Hints

  1. Map each timestamp t to a bucket using t % window_size.
  2. A bucket needs both a stored timestamp and a count. If the stored timestamp is different from the current one, the old count is stale and should be replaced.

Loading coding console...