Google interview question
Given: class EventCounter { public: void Increment() {} int GetEventsLastSecond() {} int GetEventsLast24Hours() {} }; Fill in the functions, where Increment is called on every event.
Interview Answer
Anonymous
package interview_questions; import java.util.Arrays; import java.util.LinkedList; import java.util.List; /** Assume time granularity of events is in milliseconds */ class EventCounter { static int BLOCK_SIZE=1024*128; class EventBlock { long events[]; int n=0; public EventBlock(){ events = new long[BLOCK_SIZE]; } public EventBlock(long givenEvents[]){ events = Arrays.copyOf(givenEvents, BLOCK_SIZE); } } long timestamp; long recentEvents[]; int nRecentEvents=0; List eventLog; EventCounter(){ recentEvents = new long[BLOCK_SIZE]; eventLog = new LinkedList(); } public void Increment() { // get current timestamp timestamp = System.currentTimeMillis(); if(nRecentEvents == BLOCK_SIZE){ eventLog.add(0,new EventBlock(recentEvents)); nRecentEvents=0; } recentEvents[nRecentEvents] = timestamp; nRecentEvents++; } /** * binary search index of * @return */ int GetEventsLastSecond() { long start = System.currentTimeMillis()-1000; int k = Arrays.binarySearch(recentEvents, 0 , nRecentEvents-1, start); if(nRecentEvents>0 && start start){ offset += BLOCK_SIZE; } else { int l = Arrays.binarySearch(block.events, start); offset += l; break; } } return offset + nRecentEvents; } else if(k==-1){ return 0; } else { return nRecentEvents-k; } } /* int GetEventsLast24Hours() { } */ };