Google Interview Question Software Engineer / Developers
Country: United States
Why would you need 24*60*60 elements in the array? You only need to store the last hour (60*60 elements).
You also need to maintain the index for the array and when you hit the last element (3599th element), you roll over and overwrite the 1st element.
Also, at the end of every hour, you should print out the number of hourly hits (or save to database or whatever)
When you need the number hits for the last minute, you just sum the last 60 elements in the array. If you need hits for the last hour, you sum the elements of the entire array.
if all we need is hits-per-last-sec, hits-per-last-min and hits-per-last-hour, then we can use "rolling sums":
- one cur-sec counter for the current second
- sec[60] for last 60 sec, sum(sec) a summary of all sec and a now-sec cyclic pointer
- min[60 for last 60 min, sum(sec) a summary of all min and a now-min cyclic pointer
Whenever a second is over:
- subtract sec[now-60] from the sum(sec)
- add cur-sec to the sum(sec)
- write cur-sec instead of sec[now-60]
- increment the cyclic pointer
Whenever a min is over:
- subtract min[now-60] from the sum(min)
- add sum(sec) to sum(min)
- write sum(sec) instead of min[now-60]
- increment the cyclic pointer
The same approach can be cheaply extended to last-day, last-week, etc.
All the operations are O(1).
My interpretation of the question: Given a website you have to find number of hits in the last second, last minute and last hour.
Idea:
Have all the counters as data member and two methods click() and query(), click updates the counter whenever the site gets a hit and query gives you hits in the last second, last minute or last hour.
Following is the pseudocode for member functions for second counter. Could be easily extended to minutes and hours.
class counter{
private:
int hitspersecond; //hits in last second
int lastsec; //last hit instant
public:
void click(){
currentsec = getcurrenttimeinsec() //absolute time in second, use standard library funtion to get that
if(currentsec == lastsec) hitspersecond++; //lastsec is last hit absolute time in seconds
else {
hitspersecond=1;
lastsec=currentsec;
}
//Similar code for minutes and hours
}
void Query(){
if(getcurrenttimeinsec() == lastsec) return hitspersecond;
else return 0;
//Similar code for minutes and hours
}
};
We can simply use an array keeping a track of every second. The length of the array for 24 hours = 24 * 60 * 60. So we will have int[] clicksPerSec = new int[86400];
- GKalchev October 25, 2012To make it O(1) amortized(since summing) time to find the clicks in last minute/ hour/ day or any query in a range, we can sum the clicks int the array arr[i] += arr[i-1] (note: here we can overflow the integer). So whenever we need to have the clicks for a specific second we return arr[second] - arr[second - 1]. For minutes we return arr[minute * 60] - arr[(minute - 1) * 60], etc..