Overview

The objective is to design a hit counter that will record the number of visits to a website till the last 5 min. It is a tricky question. Your design should be able to answer the below query in general

Number of hits for the last n minutes where 1 < = n <= 5

The solution described in this tutorial could also be extended to n minutes where n is greater than 5.

Idea is to have a data structure that could record the hit for each minute in the last five minutes.

For that, we can have below data structure

Counter Array – An array of integers of length 5.

Timestamp Array – An array of integers of length 5.

Counter[i] will store the count of hits in the ith minute

Timestamp[i] will store the last timestamp of a hit in the ith minute. It will be a number that will represent the epoch timestamp in min.

Below will be the algorithm

Get the epoch timestamp in min for the given timestamp. Let this be called timestamp_epoch

Divide that epoch timestamp by 5 and take the remainder. Let this remainder be called I

If timestamp[i] = timestamp_epoch then it means that the previous hit for the ith minute happened in the same minute. Therefore increase the counter. Basically do counter[i]++

If timestamp[i] != timestamp_epoch then it means that the last hit for the ith minute happened during a different minute. Therefore we need to reset the counter. Basically do counter[i] =1

Program

Below is the code for the same

package main

import "fmt"

var (
	counter   [5]int
	timestamp [5]int
)

func recordHit(timestamp_epoch int) {

	i := timestamp_epoch % 5

	if timestamp[i] != timestamp_epoch {
		counter[i] = 1
		timestamp[i] = timestamp_epoch
	} else {
		counter[i]++
	}

	fmt.Printf("After hit at time: %d\n", timestamp_epoch)
	fmt.Println(counter)
	fmt.Println(timestamp)
	fmt.Println()

}

func getNumberOfHit(timestamp_epoch int, minute int) (int, error) {

	if minute > 5 {
		return 0, fmt.Errorf("incorrect value of past minute passed")
	}
	hits := 0

	for k := timestamp_epoch; k > timestamp_epoch-minute; k-- {
		i := k % 5
		if timestamp[i] > timestamp_epoch-5 {
			hits = hits + counter[i]
		}
	}

	return hits, nil

}
func main() {
	recordHit(1000)

	recordHit(1000)

	hits, _ := getNumberOfHit(1000, 1)
	fmt.Printf("Current timestamp: %d,Last minue: %d,  Hits:%d\n\n", 1000, 1, hits)

	recordHit(1001)

	hits, _ = getNumberOfHit(1001, 2)
	fmt.Printf("Current timestamp: %d, Last minue: %d, Hits:%d\n\n", 1001, 2, hits)

	recordHit(1005)

	hits, _ = getNumberOfHit(1005, 5)
	fmt.Printf("Current timestamp: %d, Last minue: %d,  Hits:%d\n", 1005, 5, hits)

	hits, _ = getNumberOfHit(1005, 2)
	fmt.Printf("Current timestamp: %d, Last minue: %d, Hits:%d\n", 1005, 2, hits)

	recordHit(1007)
	hits, _ = getNumberOfHit(1007, 5)
	fmt.Printf("Current timestamp: %d, Last minue: %d, Hits:%d\n", 1007, 5, hits)

}

Output

After hit at time: 1000
[1 0 0 0 0]
[1000 0 0 0 0]

After hit at time: 1000
[2 0 0 0 0]
[1000 0 0 0 0]

Current timestamp: 1000,Last minue: 1,  Hits:2

After hit at time: 1001
[2 1 0 0 0]
[1000 1001 0 0 0]

Current timestamp: 1001, Last minue: 2, Hits:3

After hit at time: 1005
[1 1 0 0 0]
[1005 1001 0 0 0]

Current timestamp: 1005, Last minue: 5,  Hits:2
Current timestamp: 1005, Last minue: 2, Hits:1
After hit at time: 1007
[1 1 1 0 0]
[1005 1001 1007 0 0]

Current timestamp: 1007, Last minue: 5, Hits:2

Let’s understand it with an example as well

During start counter[i] = 0 for i =0 to 4. Also timestamp[i] = 0 for i =0 to 4

counter = [0, 0, 0, 0, 0]
timestamp = [0, 0, 0, 0, 0]

Let’s say the current epoch timestamp is in min is 1000. Let this be called timestamp_epoch

Let’s say there is one hit in the first minute
- i = 1000%5 which is 0
- timestamp[i] is 0. So timestamp[i] is not equal to timestamp_epoch.
- Do counter[i]++, which means counter[0] = 1
- Set timestamp[i] = 1000 which is the current timestamp in min. So counter and timestamp will be

counter = [1, 0, 0, 0, 0]
timestamp = [1000, 0, 0, 0, 0]

Let’s say there is another hit in the first minute
- i = 1000%5 which is 0
- timestamp[i] is 1. So timestamp[i] is equal to timestamp_epoch.
- Do counter[i]++ which means counter[0] = 2
- Set timestamp[0] = 1000 which is the current timestamp in min. So counter and timestamp will be

counter = [2, 0, 0, 0, 0]
timestamp = [1000, 0, 0, 0, 0]

Let’s say there is another hit in the second minute when the timestamp in the minute was 1001
- i = 1001%5 which is 1
- timestamp[1] is 0 currently. So timestamp[1] is not equal to timestamp_epoch.
- Do counter[1]++ which means counter[1] = timestamp_remainder
- Set timestamp[1] = 1001 which is timestamp_epoch in min. So counter and timestamp will be

counter = [2, 1, 0, 0, 0]
timestamp = [1000, 1001, 0, 0, 0]

Now let’s say there is another hit at 6 min. At that time the current epoch timestamp in min will be 1005. Why 1005? 1000 is the first minute then 1005 will be the sixth min)
- i = 1005%5 which is 0
- timestamp[0] is 1000. So timestamp[0] is not equal to timestamp_epoch.
- Reset counter. Do counter[0]=1 which means counter[0] = 1
- Set timestamp[0] = 1005 which is timestamp_epoch in min. So counter and timestamp will be

counter = [1, 1, 0, 0, 0]
timestamp = [1005, 1001, 0, 0, 0]

At any given time to get the number of hits per minute, we can simply add all the entries in the counter array.

Conclusion

This is all about designing a Hit Counter. Hope you have liked this article. Please share feedback in the comments