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

What role is this question designed for?

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

Design hit counter for last 5 minutes | Vercel Coding Question

Design hit counter for last 5 minutes

Company: Vercel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are launching a new webpage and need a last-minute server-side metric to track popularity in real time. Implement a hit counter that supports the following operations: - `track_hit(timestamp)`: record one hit at the given `timestamp` (an integer representing seconds since epoch or since process start). - `get_hit_count_in_last_5_minutes(timestamp)`: return how many hits occurred in the last 5 minutes (the last 300 seconds) up to and including the provided `timestamp`. Assumptions / clarifications: - Timestamps may be non-decreasing (typical in these problems), but state your approach if they can arrive out of order. - The function should be efficient in both time and memory. Follow-up: If there are a very large number of hits per second, how would you optimize the implementation to avoid storing one entry per hit (e.g., by using fixed-size time buckets)?

Quick Answer: This question evaluates competency in designing time-windowed counting mechanisms, efficient data structures for time-series events, and algorithmic performance under real-time constraints.

Part 1: Hit Counter for the Last 5 Minutes

You are given a sequence of hit-counter operations in chronological order. Implement a hit counter that supports two operations: - `track_hit`: record one hit at the given timestamp. - `get_hit_count_in_last_5_minutes`: return how many hits happened in the last 5 minutes up to and including that timestamp. For this problem, timestamps are non-decreasing. A hit at time `x` should be counted for a query at time `t` if `t - 299 <= x <= t`. If timestamps could arrive out of order, a simple queue would no longer be enough; you would need an ordered structure keyed by timestamp. In this problem, assume non-decreasing timestamps and focus on an efficient implementation.

Constraints

0 <= len(operations) == len(timestamps) <= 200000
Each operation is either `track_hit` or `get_hit_count_in_last_5_minutes`
0 <= timestamps[i] <= 10^9
Timestamps are non-decreasing

Examples

Input: (['track_hit', 'track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'track_hit', 'get_hit_count_in_last_5_minutes'], [1, 2, 300, 300, 301, 301])

Expected Output: [3, 3]

Explanation: At time 300, hits at 1, 2, and 300 are counted. At time 301, the hit at 1 expires, but the new hit at 301 is added, so the count is still 3.

Input: (['track_hit', 'track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'get_hit_count_in_last_5_minutes'], [10, 10, 10, 10, 309])

Expected Output: [3, 3]

Explanation: Multiple hits can happen at the same second. At time 309, hits from time 10 are still inside the window because 309 - 299 = 10.

Input: (['track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'get_hit_count_in_last_5_minutes'], [1, 300, 300, 301])

Expected Output: [2, 1]

Explanation: At time 300, both hits count. At time 301, the hit at time 1 is now outside the last 300 seconds.

Input: (['get_hit_count_in_last_5_minutes'], [50])

Expected Output: [0]

Explanation: No hits were tracked before the query.

Input: ([], [])

Expected Output: []

Explanation: Empty input should return an empty list.

Hints

Only hits from the last 300 seconds matter. Older hits can be discarded permanently.
Because timestamps are non-decreasing, each stored hit is added once and removed once.

Part 2: Memory-Optimized Hit Counter with Fixed-Size Buckets

You are given the same hit-counter operations as in Part 1, but now the system may receive a very large number of hits per second. Storing one entry per hit can use too much memory. Implement the hit counter using fixed-size time buckets. Since only the last 300 seconds matter, aggregate hits by second in a circular array of size 300. Supported operations: - `track_hit`: record one hit at the given timestamp. - `get_hit_count_in_last_5_minutes`: return how many hits happened in the last 5 minutes up to and including that timestamp. A hit at time `x` should be counted for a query at time `t` if `t - 299 <= x <= t`. Assume timestamps are non-decreasing. This bucketed ring-buffer approach is not safe for out-of-order timestamps without extra bookkeeping.

Constraints

0 <= len(operations) == len(timestamps) <= 1000000
Each operation is either `track_hit` or `get_hit_count_in_last_5_minutes`
0 <= timestamps[i] <= 10^9
Timestamps are non-decreasing
Your approach should avoid storing one item per individual hit

Examples

Input: (['track_hit', 'track_hit', 'track_hit', 'track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'get_hit_count_in_last_5_minutes', 'track_hit', 'get_hit_count_in_last_5_minutes'], [100, 100, 100, 100, 100, 100, 399, 400, 400])

Expected Output: [5, 5, 1]

Explanation: Five hits happen at time 100. They still count at time 399, but they expire by time 400; after tracking one new hit at 400, the count is 1.

Input: (['track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes'], [1, 301, 301])

Expected Output: [1]

Explanation: Both timestamps map to the same bucket index, so the older value must be overwritten when time 301 arrives.

Input: (['track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'get_hit_count_in_last_5_minutes'], [42, 42, 341, 342])

Expected Output: [2, 0]

Explanation: At time 341, hits at 42 are still included because 341 - 299 = 42. At time 342, they expire.

Input: (['track_hit', 'track_hit', 'track_hit', 'track_hit', 'track_hit', 'track_hit', 'get_hit_count_in_last_5_minutes', 'get_hit_count_in_last_5_minutes'], [1, 2, 2, 300, 300, 300, 300, 301])

Expected Output: [6, 5]

Explanation: At time 300, all six hits are within the window. At time 301, the hit at time 1 expires, leaving five.

Input: ([], [])

Expected Output: []

Explanation: Empty input should return an empty list.

Hints

Use exactly 300 buckets, one for each possible second offset in the sliding window.
Each bucket should store both a timestamp and a hit count so you can tell whether the bucket still belongs to the current window or needs to be reset.

Quick Overview

This question evaluates competency in designing time-windowed counting mechanisms, efficient data structures for time-series events, and algorithmic performance under real-time constraints.