Design Hit Counter

MediumDesigndesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Count page hits over a sliding five-minute window. Time is measured in whole seconds. Implement: - HitCounter() creates the counter. - hit(timestamp) records one hit at timestamp (several hits may share a timestamp). - getHits(timestamp) returns how many hits happened in the last 300 seconds, i.e. hits at times t with timestamp - 300 < t <= timestamp. All calls (both kinds) arrive with non-decreasing timestamps. Aim for amortized O(1) per call.

Examples

Input: ["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"] [[],[1],[2],[3],[4],[300],[300],[301]]
Output: [null,null,null,null,3,null,4,3]
At 4 all three hits count. At 300 the window (0, 300] holds 4 hits. At 301 the window is (1, 301], so the hit at time 1 has expired.
Input: ["HitCounter","hit","hit","getHits","getHits"] [[],[10],[10],[309],[310]]
Output: [null,null,null,2,0]
At 309 the window (9, 309] still contains both hits at 10. At 310 the window (10, 310] excludes them.

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • Timestamps are non-decreasing across all calls.
  • At most 10^4 calls are made.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems