Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
extract day/hour/minute/second part in timestamp, and use them as key, each time to increment(), if key doesn't change, increase counter for that key, otherwise update key and reset counter to 1. In getCountInLastX(), get day/hour/minute/second part from current Date(), and compare them with existing keys, if not match, return 0, otherwise return counter for that key.
for example, key_day could be calculated as (timestamp / one_day * one_day), where one_day is 24 * 60 * 60 * 1000000 ns, similarly to key_hour is (timestamp / one_hour * one_hour), so key_X is used to only track timer in last X, and counter associated with key_X is to record how many timer in key_X.
class RealTimeCounterImpl implements RealTimeCounter{
//factor for seconds = 1;
//factor for minutes = 60;
//factor for hour = 1200;
//factor for day = 1200*24;
long getOneRange(long end, long factor){
long elapsedTime = end - (1000000000 * factor);
return elsapsedTime;
}
/*
* Keep saved the following data:
* - first time we incremented the counter
* - count in last day
* - count in last hour
* - count in last minute
* - count in last second
*
*/
int countInLastDay = 0;
int countInLastHour = 0;
int countInLastMinute = 0;
int countInLastSecond = 0;
long timeFirstInsertLastDay = 0;
long timeFirstInsertLastHour = 0;
long timeFirstInsertLastMinute = 0;
long timeFirstInsertLastSecond = 0;
void increment(){
long currentTime = time();
long start = getOneRange(currentTime, 1);
if (timeFirstInsertLastSecond == 0 || timeFirstInsertLastSecond < start) {
timeFirstInsertLastSecond = currentTime;
countInLastSecond = 1;
}else{
countInLastSecond++;
}
//the same should be done for the other three increments
}
int getCountInLastSecond(){
return countInLastSecond;
}
int getCountInLastMinute(){
return countInLastMinute;
}
int getCountInLastHour(){
return countInLastHour;
}
int getCountInLastDay(){
return countInLastDay;
}
}
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class Counter {
private enum StatsType {
SEC(1000), MIN(60000), HOUR(3600000), DAY(24*60*60*1000), MONTH(30*24*60*60*1000);
private final long divisor;
StatsType(int d) {
this.divisor = d;
}
}
static class Stats {
long key = 0;
long count = 0;
StatsType t;
Stats(StatsType t) {
this.t = t;
}
}
static class StatsPair {
Stats cur;
Stats saved;
public StatsPair(Stats cur, Stats saved) {
this.cur = cur;
this.saved = saved;
}
}
Map<StatsType, StatsPair> tab;
Counter() {
tab = new HashMap<Counter.StatsType, Counter.StatsPair>();
for(StatsType t : StatsType.values())
tab.put(t, new StatsPair(new Stats(t), new Stats(t)));
}
public void incr() {
long curMs = System.currentTimeMillis();
for(Entry<StatsType, StatsPair> e: tab.entrySet()) {
StatsPair sp = e.getValue();
StatsType ty = e.getKey();
long curKey = curMs/ty.divisor;
if( sp.cur.key != curKey ) {
sp.saved.key = sp.cur.key;
sp.saved.count = sp.cur.count;
sp.cur.key = curKey;
sp.cur.count = 0;
//System.out.println("moved to saved [" + ty + "] " + sp.saved.key + " " + sp.saved.count);
}
++sp.cur.count;
}
//System.out.println(tab);
}
private long getCountInLast(StatsType ty) {
long last = System.currentTimeMillis()/ty.divisor - 1;
StatsPair sp = tab.get(ty);
if ( sp.cur.key == last )
return sp.cur.count;
else if ( sp.saved.key == last )
return sp.saved.count;
return 0;
}
public long getCountInLastSec() {
return getCountInLast(StatsType.SEC);
}
public long getCountInLastMin() {
return getCountInLast(StatsType.MIN);
}
public long getCountInLastHour() {
return getCountInLast(StatsType.HOUR);
}
/**
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException {
Counter c = new Counter();
for(int i=0; i<100; i++)
c.incr();
Thread.sleep(2000);
for(int i=0; i<50; i++)
c.incr();
System.out.println(c.getCountInLastSec());
Thread.sleep(1000);
System.out.println(c.getCountInLastSec());
Thread.sleep(60000);
System.out.println(c.getCountInLastMin());
System.out.println(c.getCountInLastHour());
}
}
- zouzhile February 21, 2014