Number of Recent Calls

ping from pikachu at 5320ms

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

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

 

Constraints:

• 1 <= t <= 109
• Each test case will call ping with strictly increasing values of t.
• At most 104 calls will be made to ping.

최근 온 ping의 range에 해당하는 최근 ping들의 갯수를 리턴하는 문제이다. 모든 콜이 점점 larger value를 준다고 했기 때문에, sorting이 필요 없었고, queue를 사용했다. 

 

import java.util.*;
class RecentCounter {
    Queue<Integer> queue;
    public RecentCounter() {
        queue = new LinkedList<>();
    }
    
    public int ping(int t) {
        queue.add(t);
            while(queue.peek() < t - 3000){
                queue.poll();
        }

        return queue.size();
    }
}

큐에 ping이 오면, 새로운 숫자를 집어넣고, 그 숫자에서 3000을 뺀 숫자가 앞쪽에 위치하면 하나씩 지우는 형식이었다. 최악으로는 O(N)까지 갈 수 있다. 60%정도의 속도를 보여주었다.