933. Number of Recent Calls #

Problem #

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]

Note:

1. Each test case will have at most 10000 calls to ping.
2. Each test case will call ping with strictly increasing values of t.
3. Each call to ping will have 1 <= t <= 10^9.

Problem Summary #

Write a RecentCounter class to count recent requests. It has only one method: ping(int t), where t represents some time in milliseconds. Return the number of ping calls from 3000 milliseconds ago until now. Any ping within the time range [t - 3000, t] will be counted, including the current ping (at time t). It is guaranteed that each call to ping uses a larger t value than before.   Notes:

• Each test case will call ping at most 10000 times.
• Each test case will call ping with strictly increasing t values.
• Each call to ping has 1 <= t <= 10^9.

Solution Ideas #

• Design a class that can use the ping(t) method to calculate the number of pings in the [t-3000, t] interval. t is in milliseconds.
• This problem is relatively simple; use binary search in the ping() method.

Code #

type RecentCounter struct {
	list []int
}

func Constructor933() RecentCounter {
	return RecentCounter{
		list: []int{},
	}
}

func (this *RecentCounter) Ping(t int) int {
	this.list = append(this.list, t)
	index := sort.Search(len(this.list), func(i int) bool { return this.list[i] >= t-3000 })
	if index < 0 {
		index = -index - 1
	}
	return len(this.list) - index
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ping(t);
 */