Design Hit Counter

Design Hit Counter is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given a class HitCounter that records hits at given timestamps (in seconds). Implement the following methods:

- hit(timestamp): Records a hit that happened at the given timestamp (an integer representing the current time in seconds). - getHits(timestamp): Returns the number of hits recorded in the past 5 minutes (i.e., in the time interval [timestamp - 299, timestamp], inclusive).

Both methods will be called with timestamps in chronological order (i.e., the timestamp parameter is always greater than or equal to the previous calls).

Return the number of hits in the past 5 minutes for each call to getHits.

Topics and companies

Topics: Array, Binary Search, Design, Queue, Data Stream.

Reported in interviews at Amazon, Microsoft, Apple, Bloomberg, Google, Yandex.

How to practise Design Hit Counter on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) amortized per hit and getHits call. Each hit and each removal in getHits is processed once, so total work is proportional to the number of hits. time and O(N), where N is the number of hits in the last 300 seconds. Each unique timestamp within the window is stored. space.

Open Design Hit Counter in the code editor, or read the Design Hit Counter editorial for a worked solution with its approach and complexity analysis.

Where Design Hit Counter sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Design Hit Counter

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern