Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
(Poster here.)
Another point of clarification: "in the last X" is measured relative to the current nanosecond, i.e., it refers to the time interval [time() - X, time()]. This is a continuously updating and moving window of time.
If the timer is at nano scale, then a queue will not be ideal solution: Assuming 32 bytes/ message, holding a day's worth of timestamp in a queue would require 3600 * 24 * 10^9 * 32 bytes which would be in peta bytes.
if at each nanosecond an increment request is coming then it might consume 10^9*3600*24 bytes = 777PB
if interviewer has mentioned that we have nano sec accuracy then we have to serve the accuracy in providing the answer.
one solution i can think of is to write all entries in the file
File F
long counter // using it as string because long cannot hold more than 9 digits
increment()
{
F.Append(Time() + ":" + ++counter)
}
getCountInLastSecond()
{
long currentTime = Time()
long lastcounter = BinarySearchInFile(currentTime - Math.Pow(10, 9))
return this.counter-lastcounter;
}
// similarly we can implement other get methods
class A implements RealTimeCounter {
private volatile ArrayList<Long> timers = new ArrayList<Long>();
private static java.util.Timer timer = new Timer();
private static TimerTask task = new TimerTask() {
public void run(){
// query for today's date
removeEntriesLongerThanDay();
}
};
static {
// run once every day say 10pm, you can change this to any other time or any frequency.
DateTime now = new DateTime(DateTimeZone.forID("US/Eastern"));
DateTime fivePM = now.withTime(22,00,0,0);
timer.scheduleAtFixedRate(task, fivePM.toDate(), 1000*60*60*24);
}
public void increment() {
timers.add (System.currentTimeMillis()) ;
}
private int getCounters(long n) {
int count = 0;
long currentTime = System.currentTimeMillis();
for (Long val:timers) {
if ( (( currentTime - val )/ n) > 0 )
count ++;
}
return count;
}
public int getCountInLastSecond() {
return getCounters(1000) ;
}
public int getCountInLastMinute() {
return getCounters (60*1000) ;
}
public int getCountInLastHour() {
return getCounters (60*60*1000) ;
}
public int getCountInLastDay() {
return getCounters (24*60*60*1000) ;
}
/**
* Removes the entries which are older than day,
* this will make sure the ArrayList 'timers' doesn't
* grow very very long as we are cleaning up entries eventually.
* @param null
* @return null
*/
private void removeEntriesLongerThanDay() {
if (getCountInLastDay() <= 0 )
return;
long currentTime = System.currentTimeMillis();
ArrayList<Long> removalIndexes = new ArrayList<Long>();
long n = 24* 60 * 60 * 1000; // Number of sec in 1 day.
for (int i = 0; i < timers.size(); i++) {
if ( (( currentTime - timers.get(i) )/ n) > 0 ) {
removalIndexes.add((long) i);
}
}
synchronized(timers){
for (Long index:removalIndexes)
timers.remove(index);
}
}
}
Read the question carefully. "timer time() with nanosecond precision". You are using precision at millisecond level. Also they havent mentioned that your "get" requests have to return values at second/minute boundaries. They could be rolling window. For Ex: If current time is 10 PM 48 min 56 sec 77777777 ns, then the getRequestsInLastSec request should return the num requests between 10 PM 47 min 77777777 ns to 10 PM 48 min 56 sec 77777777 ns.
You also made a wild assumption that you could cron a timer to purge the request queue. Such assumptions are invalid.
I am not sure if you read the code carefully, so let me put things in clear perspective for you:
1) The timer object is of type "java.util.Timer" and not the timer time() class which the author mentions in the question. So they are two separate entities. java.util.Timer is a class under the java.lang package. [See: docs.oracle.com/javase/1.5.0/docs/api/java/util/Timer.html].
2) My assumption of using the milli sec doesn't make any difference in the output required / expected. If there were say 1,000 ticks happening in 100 nano seconds then from my logic they would appear to happen in 0 millisec ( they actually happened in 0.000100 millisec). Since we are only concerned with the number of ticks (or number of times increment was called) so the code would still return 1000 ticks. which is the response expected here.
3) The problem also states that the space usage shouldn't grow depending on the number of call backs to increment(), since the API has methods defined only till the getCountInLastDay() so I am clearing any timers or calls which happened more than 24 hours ago will not only put a cap on the storage but also remove any data which is stored but never used or read anymore.
4) You still haven't explained why you have used 10^9 multiplication factor here. The question says "timer time()" has nano second precision so that "just" means if there were say 10,000 ticks happened in 100 nano seconds then you will be able to differentiate the difference in the timings of the individual ticks to the nano second level. It has nothing to do with the address space or how much memory will be consumed. (fyi : the default precision level is till microseconds so nano second isn't that far either :P )
5) Assuming you took some basic programming course :P at some level in your life, let me ask you on what basis do you have your "wild" assumption of using 32 "bytes" per message, what programming language uses that much memory to store information for primitive or non primitive variables. Please enlighten me. :) I may have still let you go if you had used "32 bits" NOT "32 bytes" to store information. With these two corrections I am sure your claim of using petabytes of memory will come down.
Dude.. First off control your arrogance. I am a MS from a top univ and currently Sr Soft Dev at Amazon in Seattle working on several big data/distributed systems. So I know my CS concepts well enough. From having interviewed several SDEs both on phone and in house, I can certainly say with confidence that your answer would most certainly be rejected.
1. I do know that you used java.util.Timer and not the timer mentioned by the question. I pointed out that no big tech companies will appreciate this kind of hacky way of clearing a queue at a specified time. These are not the way real systems are built.
2. The 10^9 comes from a fact that the timer gives ticks at nanosecond precision. So if you were to store each and every timestamp, you would need a queue of 10^9 * 3600 * 24.
3. In the minimum you need to store the request UUID, timestamp in the queue. If you have a clock at nanosecond precision and it gives you the number of nanoseconds passed since the epoch of 1st January 1970 (which is what most of timers do), calculate the number of bytes required to store such a number.
The above reply by Anonymous is mine.
In the above reply, hope you understood why the queue size has a factor of 10^9. It is because if you have a highly available service and at worst case a request happens every nanosecond, you will end up adding that to the ArrayList.
Let me tell you some things that interviewers look for when they ask such questions, based on my experience:
It is but obvious that the service is a distributed service (especially these questions are asked in Google/Amazon). In a real world system, a loadbalancer fans out requests to app servers/web server. A web request hits one machine in your fleet. How do we maintain a count of an entity (like webrequests) over several machines? How do we ensure consistency of data? What happens if a get Request is made (say by another consumer) along with many put requests (In your case "increment" method) i.e. do you have synchronization issues? What happens if a host fails before a count is incremented? There are many things that you need to consider/clarify when you are asked such question, before jumping into a solution and claiming to be alan turing.
stackoverflow.com/questions/17562089/how-to-count-number-of-requests-in-last-second-minute-and-hour
- Anonymous January 29, 2014