I did the exact same counter problem when I did a phone interview with Google last week. Below is an outline of how I went about solving the problem. Please note, this question was the third question asked during my one hour phone interview. If this question had been asked first, I would have probably not been able to do as good of a job on it. Since it was asked third, I was sufficiently 'in the zone' so the code came out relatively easily.
I started out by writing a quick doctest to define the interface:
>>> counter = Counter()
>>> counter.increment()
>>> counter.query(‘minute’)
1
>>> counter.query(‘hour’)
23
>>> counter.query(‘second’)
0
Then I wrote the class. My intention was to make it with as few moving parts as possible.
import datetime
class Counter(object):
def __init__(self):
self.points = []
def increment(self):
self.points.append(datetime.datetime.now())
def query(self, timeframe):
if timeframe == 'second':
delta_ago = datetime.timedelta(seconds=1)
elif timeframe == 'minute':
delta_ago = datetime.timedelta(minutes=1)
else timeframe == 'hour':
delta_ago = datetime.timedelta(hours=1)
return len([x for x in self.points if x > delta_ago])
The amount of time it took me to write the above code was probably less than 10 minutes. I was properly 'in the zone' at this point so I was able to get my thoughts out into code pretty well. The interviewer kept asking if I could make the code faster. I then came up with the idea to replace the last line with a for loop so it looked like this:
for i, x in enumerate(self.points):
if v < delta_ago:
return i
He still kept leaning on me to make it "faster". I wanted to tell him that it is very hard to optimize something when its not actually being used. "whiteboard optimizing" as I call it is pointless, because optimization should always be a process driven by actual performance data. But, I though it to be in my best interest to not argue with the interviewer, so I didn't say anything. I actually wanted the job, after all. I was about to give up when at the very last minute, I came up with the below idea.
class Counter(object):
def __init__(self):
self.minute_counter = 0
self.minute_counter_created = datetime.datetime.now()
self.hour_counter = 0
self.hour_counter_created = datetime.datetime.now()
self.second_counter = 0
self.second_counter_created = datetime.datetime.now()
def increment(self):
if datetime.datetine.now() < self.second_counter_created:
return self.second_counter += 1
else:
# reset timer
self.second_counter = 0
self.second_counter_created = datetime.datetime.now()
...
def query(self, timeframe):
if timeframe == ‘second’:
return self.second_counter
if timeframe == ‘minute’:
...
The interview sounded happy so see me find that solution. I have no idea if he sounded happy because he was impressed with my code, or if he was happy that the interview is finally over. At any rate, he asked me if I had any questions for him. We talked for a few minutes, then the call ended.
The final solution was something I came up with on the spur of the moment. After I hung up the phone, I continued to think about the problem. Now I realize my final solution is actually wrong. If you query the counter 1.1 seconds after you initialize it, you'll get back only the points in the last 0.1 seconds instead of the last 1.0 second.