CareerCup

- Use a queue implemented as a resizable array to store the timestamps of all new requests
- maintain head/tail pointers as usual
- Also maintain three pointers: ptr_last_1hr_from_tail, ptr_last_1min_from_tail, ptr_last_1sec_from_tail

Updates to the Queue:
everytime a new timestamp is enqueued (added to tail):
- continue dequeueing while(timstamp[head]-timestamp[tail] > 1hour) . this ensures that we dont continue to keep storing timestamps we dont need.
- set ptr_last_1hr_from_tail = head
- decrement ptr_last_1min_from_tail until (timestamp[ptr_last_1min_from_tail] -timestamp[tail] > 1min)
- decrement ptr_last_1sec_from_tail until (timestamp[ptr_last_1sec_from_tail]-timestamp[tail] > 1sec)

Fetch counts from Queue:
On every new fetch request:
- for last 1 hour count: set fetch_1hr_ptr to ptr_last_1hr_from_tail and decrement fetch_1hr_ptr wile timestamp[fetch_1hr_ptr]-fetch_timestamp > 1hr ;
- for last 1 min count: set fetch_1min_ptr to ptr_last_1min_from_tail and decrement fetch_1min_ptr wile timestamp[fetch_1min_ptr]-fetch_timestamp > 1min;
- for last 1 sec count: set fetch_1sec_ptr to ptr_last_1sec_from_tail and decrement fetch_1sec_ptr wile timestamp[fetch_1sec_ptr]-fetch_timestamp > 1sec ;
- req count in last 1hr = (fetch_1hr_ptr-tail)
- req count in last 1min = (fetch_1min_ptr-tail)
- req count in last 1sec = (fetch_1sec_ptr-tail)

Depending on the nature of the request traffic, we could also use binary search when updating the various pointers instead of linear decrement.

Problem statement says that query can be for last second, last minute or last hour. We have to maintain list for each window.

My Solution:
--> Maintain a list of seconds, minutes, hour of size 60, 60 & 1 respectively.

Now, basically we have to run two operations:
1) Update all three array when user logs in.
2) Update all three array after each second. (All three array need not to be updated per second)

So array will be like:
second[60] = {0,0,0,0...0}
minute[60] = {0,0,0,0...0}
hour[24] = {0}

Now 1st operation: (Simple)
Whenever any user logs in, increment each arrays' 0th index. 0th index will always point to the last second, minute, hour.

Now 2nd operation:
Keep updating newest & keep outdating oldest index values. This can be done by timeout operation. Timeout value is 1 sec:

1) At each second:
    i) 60th node of array is removed & 0th node is added to second's array. (Not for initial 60 second when only insertion operation required) 
    ii) value of 60th node of second array is subtracted from 0th node of minutes array.(Not for initial 60 second)
2) At each 60th second, a new node with value of current node is inserted at the start of minute array. Now, minute array has 2 node
    i)  1st node will have value of 0th minute. (initial value of this node is same as old 0th node)
    ii) 2nd node will have value of 1st minute.
3) At each 60th min,
     i ) 60th node of minute array is removed & 0th node is inserted
     ii) hour index will be subtracted with 60th minute index value.

In above solution, I have taken array but all operation has been described as link link operation (insert & remove) for sake of simplicity.
So either we can take array of link list or these operation can be done like rotating array. We need to keep start & end index for each array.

The server requests is like a continuous input stream.
For the time consider a moving window with 1 second or 1 minute or 1 hour as the size of the window.
Consider last 1 second.
Maintain a HashMap<String, Integer> with key as the url and value as the count of the url requested.
Begin time is the time from when we want last 1 second url requests.
So from the log consider keep scanning till (time stamp for the request - begin time) <= 1 second.
For every such request satisfying the time criteria, if new request add the url to a hashmap with count as 1 ; else increment the count for the existing matching url.
Once a url is reached such that (time stamp for the request - begin time) > 1 second flush all the url and the counts onto some file and create a new HashMap.

A balanced binary tree such as AVL or red block and arrange nodes as per arrival time of request. Every node should also have a counter of no.of nodes rooted at the left child of that node.

Here all operations takes O(logn)

Use a max-heap and put the events as them come in. The latest event will be at the top. Time complexity is O(n log n) for inserts.
Then you can query the heap with max() in O(1) time and extract-max() in O(log n) time and get the events in last sec, min, or hour.

Add request listener to track request.

long startTime = new Date().getTime();

int lastSecondRequests = 0;
long lastMinuteRequests = 0;
long lastHourRequests = 0;

long whichSecond = 0;
long whichMinute = 0;

void requestHandler(HttpRequest request) {
	long currentTime = new Date().getTime();
	
	long secondSpan = Math.round((currentTime - startTime) / 1000 + 0.5);
	long minuteSpan = Math.round((currentTime - startTime) / 60 * 1000 + 0.5);
	long hourSpan = Math.round((currentTime - startTime) / 3600 * 1000 + 0.5);

	if(hourSpan > whichHour)  {
		whichHour = HourSpan;
		lastHourRequests = 1;
	} else {
		lastHourRequests++;
	}

	if(minuteSpan > whichMinute)  {
		whichMinute = minuteSpan;
		lastMinuteRequests = 1;
	} else {
		lastMinuteRequests++;
	}
	
	if(secondSpan > whichSecond)  {
		whichSecond = secondSpan;
		lastSecondRequests = 1;
	} else {
		lastSecondRequests++;
	}
	
}

Isn't it simpler to just store the timestamps of all requests from current time - hour up to current time in a queue?

You can create the a queue which contains all the timestamps as requests come in.
Then every time interval say every 1millisecond remove all the timestamps in the head which is 1 hour old.

All you have to do to get the count is is peek from the head of the queue up to last the time stamp which is current queue timestamp > current time - hour/minute/seconds.

Or alternatively just create a score array say int score[3] and update every millisecond by reading the queue as described above and update the counters.

Use a RingBuffer of Size 3600, each element of the buffer is an int (or maybe an AtomicInt) and represents a counter for one second.

We'll have a variable for the current postion in the buffer, this will be used by readers to figure out where to start reading. And by the writer to know when it's advanced and needs to set the current position's counter to 1.

On each update calculate the current postion: requests_time/1000 % 3600

class RequestCounter{
	int[] ring = new int[3600]; // this could be an AtmoicInt array to be thread safe.
        long currentPos = 0;
        public void increment(long requestTs){
            writePos = requestTs/1000 % 3600;
            if(writePos == currentPos){
                  ring[writePos]++;
            }else{
		 ring[writePos] = 1;
                 currentPos = writePos;
            }
        }
        public int  getCountForLast(int seconds){
            if(seconds > 3600) //Error?
  		 seconds = 3600;
            int count = 0;
            int stopAt = currentPos-seconds;
            for(pos = currentPos; pos > stopAt ; pos--){
                  count += ring[pos%3600] ;
            }
            return count;
       }
       //below write methods that call getCountForLast with 1, 60, 3600
  }

Added benefit : RingBuffers will better utilize cache lines and avoid False Sharing.

One straight forward way may be:
Maintain a LinkedList of nodes with <timeStamp, request> pairs.
As requests come, keep adding to this linked list (sorted by timestamps).

Maintain 3 pairs of pointers.
1st pair of pointers = lastSecondStart, lastSecondEnd
2nd pair=lastMinuteStart, lastMinuteEnd
3rd pair=lastHourStart, lastHourEnd

After every second do below:
lastSecondStart = lastSecondEnd->next;
lastSecondEnd=move right to node by a 'second' using currentTime & node.timeStamp;

lastMinuteStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastMinuteEnd=lastSecondEnd;

lastHourStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastHourEnd=lastMinuteEnd;

Essentially 3 traversals to right. Num of nodes depends on num of requests in that second.

Caveats: 1.If there are not too many requests this works.
2. Concurrent requests can be handled by making add() method synchronized. But too many of these can tamper performance.

I already answered to this question.With respect to that answer some1 asked me that I missed synchronization and told if I use lock then it may degrade the performance that means all request can't be tracked per second.

we need a data structure that can handle this.

I would go with already synchronized data structures like hashtable. With keys as "previous_hour", "pevious_minute", previous_second", "current_hour", "current_minute", current_second". I will also have variables for current_hour, current_minute, current_second, new_hour, new_minute,new_second.

Every time, a request comes in check if new_second is different than previous, then update the map. Or increase the current counts.

I am going to handle this in a controversial way, which is to use a HashMap to store the #requests for each second. Then to calculate the #requests for the past second, minute and hour, I only need 3,600 checks to the HashMap, which is O(1). The downside is that the HashMap can get big really fast, and so we might also want to throw in some code to remove any obsolete keys from it.

class CountRequests {
	private long startTime = new Date().getTime();

	private HashMap<Long, Integer> counts = new HashMap<Long, Integer>();

	void handleRequest() {
		long currentTime = new Date().getTime();
		long offset = (currentTime - startTime) / 1000;
		synchronized(counts) {
			if(!counts.containsKey(offset))
				counts.put(offset, 0);
			counts.put(offset, 1 + counts.get(offset));
		}
	}

	// return the #requests in past second, minute, hour as an array
	int[] getCounts() {
		int[] freq = new int[3];
		long currentTime = new Date().getTime();
		long offset = (currentTime - startTime) / 1000;
		int total = 0;
		synchronized(counts) {
			for(int i=0; i<3600; i++) {
				long index = offset-i;
				if(counts.containsKey(index))
					total += counts.get(index);
				if(i == 0)
					freq[0] = total;
				else if(i == 59)
					freq[1] = total;
				else if(i == 3599)
					freq[2] = total;
			}
		}
		return freq;
	}
}

The question is ill-formed. Not clear if they are asking for a continuous timeframe, or discrete time intervals. Discrete time interval problem is solvable... continuous is not (on a real machine executing real machine instructions each cycle).

I am thinking about a solution which behaves better in concurrent environment.

To lock less often and to save memory, I suggest that we keep the resolution say about 1%. This means we update the count each 10ms for the 1s number, each 0.6 s for the 1min and each 0.6 min for the 1 hour. The 1 min and 1 hour counts are just simpler variant of the same, so let's think only about the 1 sec timer.

We can have a AtomicLong count, to which it adds. When it realizes that 10ms has passed, it takes this count and sends it to a list with the timestamp, similarly to what others described. We can lock on sendToList, but usually there will be no concurrency because it happens just once in 10 ms. The "optimistic locking" in AtomicLong.compareAndSet takes care about the rest of the concurrency.

AtomicLong count = new AtomicLong(0);
// last timestamp
AtomicLong lt = new AtomicLong(System.currentTimeMillis()); 

void newRequest() {
	long c = count.getAndIncrement();
    long t = System.currentTimeMillis();
	long lt2 = lt.get();
	// each 10 ms
	if(t / 10 != lt2 / 10) {
		// try to write the new timestamp - on failure, assume other thread is just doing the same and do nothing
		if(lt.compareAndSet(lt2, t)) {
			sendToList(lt2, c);
		}
	}
}

There is a very simple elegant solution to this using circular queue. Idea is to have a circular queue of size 3600*SamplesPerSec
At every sample interval, collect count till last sample and add it to circular queue.
- To get count of last 1 second, return sum of last SamplesPerSec elements
- To get count of last 1 minute, return sum of last SamplesPerSec*60 elements
- To get count of last 1 hr, return sum of last SamplesPerSec*3600 elements

All operation like returning sum and purging old entries are O(1)

interface RequestHandler {
    long numOfRequestsInLastSecond();

    long numOfRequestsInLastMinute();

    long numOfRequestsInLastHour();

    void count(LocalDateTime timestamp);
}

class RequestCounter implements RequestHandler {

    private AtomicInteger secondCounter = new AtomicInteger();
    private AtomicInteger minuteCounter = new AtomicInteger();
    private AtomicInteger hourCounter = new AtomicInteger();

    private static final DateTimeFormatter secondFormatter = DateTimeFormatter.ofPattern("MMddyyyyHHmmss");
    private static final DateTimeFormatter minuteFormatter = DateTimeFormatter.ofPattern("MMddyyyyHHmm");
    private static final DateTimeFormatter hourFormatter = DateTimeFormatter.ofPattern("MMddyyyyHH");

    private String currentSecondKey;
    private String currentMinuteKey;
    private String currentHourKey;


    public long numOfRequestsInLastSecond() {
        return secondCounter.longValue();
    }

    public long numOfRequestsInLastMinute() {
        return minuteCounter.longValue();
    }

    public long numOfRequestsInLastHour() {
        return hourCounter.longValue();
    }

    private void countSeconds(String secondKey) {
        secondCounter.getAndUpdate(existingValue -> {
            if (secondKey.equals(currentSecondKey)) {
                return existingValue + 1;
            } else {
                currentSecondKey = secondKey;
                return 1;
            }
        });
    }

    private void countMinutes(String minuteKey) {
        minuteCounter.getAndUpdate(existingValue -> {
            if (minuteKey.equals(currentMinuteKey)) {
                return existingValue + 1;
            } else {
                currentMinuteKey = minuteKey;
                return 1;
            }
        });
    }

    private void countHours(String hourKey) {
        hourCounter.getAndUpdate(existingValue -> {
            if (hourKey.equals(currentHourKey)) {
                return existingValue + 1;
            } else {
                currentHourKey = hourKey;
                return 1;
            }
        });
    }

    public void count(LocalDateTime timestamp) {
        countSeconds(secondFormatter.format(timestamp));
        countMinutes(minuteFormatter.format(timestamp));
        countHours(hourFormatter.format(timestamp));
    }
}

... Just a long long circular queue of 3600 elements will suffice and all operations will take constant time.

Sorry for misspell ..
I am not sure Google really asks so easy question? :P

import java.util.Date;

class RequestHandler {
    
    long counter = 0;
    
    synchronized void incrementCounter() {
        counter++;
    }
    
    long getCounter() {
        return counter;
    }
    
}



class Request implements Runnable {
    
    RequestHandler handler = null;
    
    Request(RequestHandler handler) {
        this.handler = handler;
    }

    @Override
    public void run() {
        this.handler.incrementCounter();
    }
    
}


/**
 * 
 */
public class ThreadTest {
    
    static final long MAX_REQUEST = 18000;
    
    public static void main(String ... args) throws InterruptedException {
        RequestHandler handler = new RequestHandler();
        
        long start_time = new Date().getTime();
        System.out.println("Before request thread(s) creation .....");
        //System.out.println("Start time : " + start_time);
        
        for(long i = 0; i < MAX_REQUEST ; i++) {
            new Thread(new Request(handler)).start();
        }
        
        long end_time = new Date().getTime();
        System.out.println("Immediate after request thread(s) creation .....");
        System.out.println("Duration : " + (end_time - start_time));
        start_time = end_time;
        System.out.println("Request Counter : " + handler.getCounter());
        
        Thread.sleep(1000);
        
        end_time = new Date().getTime();
        //System.out.println("After one minute of request thread(s) creation.....");
        //System.out.println("Duration : " + (end_time - start_time));
        //System.out.println("Request Counter : " + handler.getCounter());
    }
    
}

I tried this code in my 8GB RAM, 64bit environment and 3.40 GHZ in windows environment with 18000 request.

and I got the result ..
Before request thread(s) creation .....
Immediate after request thread(s) creation .....
Duration : 967
Request Counter : 18000