CC-11 : Find all requests received in last N seconds from the last request received.
Description:
Given a series of requests and time in milliseconds at what time the request was received, find all requests that were received in last N seconds from the time the last request was received. Request receipt time will be increasing order only.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
QueueRequestCounter queue=new QueueRequestCounter();
queue.setTimeWindow(5000);
System.out.println("Add requests..");
queue.request(1);
queue.getRequestsWithinTimeWindow();
queue.request(2);
queue.getRequestsWithinTimeWindow();
queue.request(5000);
queue.getRequestsWithinTimeWindow();
queue.request(6000);
queue.getRequestsWithinTimeWindow();
queue.request(7000);
queue.getRequestsWithinTimeWindow();
queue.request(8000);
queue.getRequestsWithinTimeWindow();
|
Time Window: 5000
Add request..
Number of requests within time window 1
Queue nodes: 1 <-
Add request..Number of requests within time window 2
Queue nodes: 1 <- 2 <-
Add request..Number of requests within time window 3
Queue nodes: 1 <- 2 <- 5000 <-
Add request..Number of requests within time window 2
Queue nodes: 5000 <- 6000 <-
Add request..Number of requests within time window 3
Queue nodes: 5000 <- 6000 <- 7000 <-
Add request..Number of requests within time window 4
Queue nodes: 5000 <- 6000 <- 7000 <- 8000 <-
|
Pseudocode:
| Initialize a new Queue to hold requests received in last N seconds. All requests received before N seconds can be discarded from the Queue.
|
| Whenever a request is received, check the requests at the start of Queue, if they are out of time window of N seconds, remove them from Queue. Then add latest request to the Queue.
|
| In methods getRequestsWithinTimeWindow(), print all elements of the Queue as the Queue only contains requests received in past N seconds from the time the last request was received.
|
Code:
public class QueueRequestCounter {
private Queue<Integer> reqQueue=new LinkedList<Integer>();
private int timeWindow=0;
public void setTimeWindow(int timeWindowinMs) {
timeWindow=timeWindowinMs;
}
public void request(int reqTimeInMs) {
while ((reqQueue.size()!= 0)&&
(reqTimeInMs - reqQueue.element() > timeWindow)){
reqQueue.remove();
}
reqQueue.add(reqTimeInMs);
}
public void getRequestsWithinTimeWindow() throws Exception{
System.out.println("Number of requests within time window "+reqQueue.size());
printQueue(reqQueue);
}
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.Queue;
import java.util.Iterator;
import java.util.LinkedList;
public class QueueRequestCounter {
private Queue<Integer> reqQueue=new LinkedList<Integer>();
private int timeWindow=0;
public void setTimeWindow(int timeWindowinMs) {
timeWindow=timeWindowinMs;
}
public void request(int reqTimeInMs) {
while ((reqQueue.size()!= 0)&&
(reqTimeInMs - reqQueue.element() > timeWindow)){
reqQueue.remove();
}
reqQueue.add(reqTimeInMs);
}
public void getRequestsWithinTimeWindow() throws Exception{
System.out.println("Number of requests within time window "+reqQueue.size());
printQueue(reqQueue);
}
public static void printQueue(Queue queue) throws Exception {
if (queue.size() == 0) { System.out.println("Queue empty"); return; }
System.out.println();
System.out.println("*********************************************************************");
System.out.print("Queue nodes: ");
Iterator itr=queue.iterator();
while (itr.hasNext()) {
System.out.print(itr.next());
System.out.print(" <- ");
}
System.out.println();
System.out.println("*********************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/* Test cases given below */
try {
QueueRequestCounter queue=new QueueRequestCounter();
queue.setTimeWindow(5000);
System.out.println("Time Window: "+5000);
System.out.println("Add request..");
queue.request(1);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(2);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(5000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(6000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(7000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(8000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(9000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(10000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(11000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(12000);
queue.getRequestsWithinTimeWindow();
System.out.print("Add request..");
queue.request(20000);
queue.getRequestsWithinTimeWindow();
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
}
}
}