Dropbox Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
List<Long> hitTime = new LinkedList<Long>();
void recordHit(){
hitTime.add(System.currentTimeMillis());
}
int getCount(){
long startTime = System.currentTimeMillis() - 30 * 1000;
int cnt = 0;
ListIterator<Long> it = hitTime.listIterator(hitTime.size());
while(it.hasPrevious()){
if(it.previous() > startTime)
cnt++;
else
break;
}
return cnt;
}
In java
1. Initialize queue for dateTime class.
2. Maintain a counter to track number of elements in queue at given time.
3. For recordHit(), make current timestamp entry in queue (BlockingQueue in java).
4. For getCounter(), keep dequeue expired values from queue. return the counter.
5. Create a timertask in java which runs in separate thraed and keep queue in sync by removing expired entries.
package designQs;
import java.util.Date;
import java.util.HashMap;
public class CareerCupDropBox {
static Integer ID = 0;
static HashMap< Date , Integer> hitMap = new HashMap<Date , Integer >();
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public static void recordHit() {
//ID++;
hitMap.put(new Date(), ++ID);
}
public static int getCount(){
Date date = new Date();
return ID - hitMap.get(new Date( date.getTime() - 300000)) ;
}
}
One thing to be considered is the synchronized use of static variable ID is important
package com.madhukar.test;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
public class CarrerCupDBTest {
List<Long> hitTime = new LinkedList<Long>();
void recordHit(){
hitTime.add(System.currentTimeMillis());
}
int getCount(){
long startTime = System.currentTimeMillis() - 5 * 60 * 1000; // 5 minutes back time
int cnt = 0;
ListIterator<Long> it = hitTime.listIterator(hitTime.size());
while(it.hasPrevious()){
if(it.previous() > startTime)
cnt++;
else
break;
}
return cnt;
}
public static void main(String[] args) {
}
}
long hit=0;
long count;
long hitStartTime = System.currentTimeMillis();
long currTime=0;
Calendar calendar = Calendar.getInstance();
public void recordHit(){
calendar.setTime(new Date());
if(hit==0){
hitStartTime = calendar.get(Calendar.MINUTE);
}
hit++;
count=hit;
if(calendar.get(Calendar.MINUTE)-hitStartTime==5){
count =0;
hitStartTime = calendar.get(Calendar.MINUTE);
}
}
public long getCount(){
return count;
}
long hit=0;
long count;
long hitStartTime = System.currentTimeMillis();
long currTime=0;
Calendar calendar = Calendar.getInstance();
public void recordHit(){
calendar.setTime(new Date());
if(hit==0){
hitStartTime = calendar.get(Calendar.MINUTE);
}
hit++;
count=hit;
if(calendar.get(Calendar.MINUTE)-hitStartTime==5){
count =0;
hitStartTime = calendar.get(Calendar.MINUTE);
}
}
public long getCount(){
return count;
}
long hit=0;
long count;
long hitStartTime = System.currentTimeMillis();
long currTime=0;
Calendar calendar = Calendar.getInstance();
public void recordHit(){
calendar.setTime(new Date());
if(hit==0){
hitStartTime = calendar.get(Calendar.MINUTE);
}
hit++;
count=hit;
if(calendar.get(Calendar.MINUTE)-hitStartTime==5){
count =0;
hitStartTime = calendar.get(Calendar.MINUTE);
}
}
public long getCount(){
return count;
}
long hit=0;
long count;
long hitStartTime = System.currentTimeMillis();
long currTime=0;
Calendar calendar = Calendar.getInstance();
public void recordHit(){
calendar.setTime(new Date());
if(hit==0){
hitStartTime = calendar.get(Calendar.MINUTE);
}
hit++;
count=hit;
if(calendar.get(Calendar.MINUTE)-hitStartTime==5){
count =0;
hitStartTime = calendar.get(Calendar.MINUTE);
}
}
public long getCount(){
return count;
long hit=0;
long count;
long hitStartTime = System.currentTimeMillis();
long currTime=0;
Calendar calendar = Calendar.getInstance();
public void recordHit(){
calendar.setTime(new Date());
if(hit==0){
hitStartTime = calendar.get(Calendar.MINUTE);
}
hit++;
count=hit;
if(calendar.get(Calendar.MINUTE)-hitStartTime==5){
count =0;
hitStartTime = calendar.get(Calendar.MINUTE);
}
}
public long getCount(){
return count;
}
It is very good question as I cannot see a good/generic solution with natural limit on the resource (container's memory) while extending the parameter (get recordHit for last 5min, 5 hours, 5 years...). If there is no limit on the resource OR we presume the number of hits for the 5 min is much less than available bytes in memory, I would use (in C++/STL notation with abstract time_t type) the deque<time_t> container (called myDeque below) with a helper function to remove expired times:
void RemoveOld(time_t tm, deque<time_t>& dqTimes) {
while( !dqTimes.empty() && dqTimes.front() < tm )
dqTimes.pop_front();
}
void recordHit() {
time_t tm = --CurrentTime--;
RemoveOld(tm - 5 Min, myDeque);
myDeque.push_back(tm);
}
long getCount() {
time_t tm = --CurrentTimeMinus5Min--;
RemoveOld(tm, myDeque);
return myDeque.size();
}
import queue
import datetime
import time
q = queue.deque()
def recordHit():
tm = datetime.datetime.utcnow()
tm5 = tm - datetime.timedelta(seconds=5)
print (tm)
q.appendleft(calculatetimeinmili(tm))
removeold(calculatetimeinmili(tm5))
getCount()
def getCount():
print (len(q))
def removeold(time):
while len(q)> 0 :
tmptime = q.pop()
if tmptime > time:
q.append(tmptime)
break
def calculatetimeinmili(tm):
return (tm.hour * 3600 + tm.minute * 60 + tm.second)*1000000 +tm.microsecond
recordHit()
time.sleep(3)
recordHit()
time.sleep(1)
recordHit()
time.sleep(3)
recordHit()
time.sleep(6)
recordHit()
I would just use a circular buffer
#include <time.h>
#include <mutex>
#define NUM_BUCKETS 512
struct Bucket {
time_t time {0};
long count {0};
};
Bucket bucketedCounts[NUM_BUCKETS];
std::mutex mtx;
void recordHit() {
time_t curTime;
time(&curTime);
auto idx = (curTime % NUM_BUCKETS);
std::lock_guard<std::mutex> lock(mtx);
auto& count = bucketedCounts[idx].count;
if (bucketedCounts[idx].time != curTime) {
bucketedCounts[idx].time = curTime
count = 1;
} else {
++count;
}
}
long getCount() {
time_t curTime;
time(&curTime);
int curIdx = (curTime % NUM_BUCKETS);
long numHits = 0;
{
std::lock_guard<std::mutex> lock(mtx);
if (bucketedCounts[curIdx].time == curTime) {
numHits += bucketedCounts[curIdx].count;
}
}
for (time_t checkTime = curTime - 300; checkTime < curTime - 1; ++checkTime) {
int idx = (checkTime % NUM_BUCKETS);
if (bucketedCounts[idx].time == checkTime) {
numHits += bucketedCounts[idx].count;
}
}
return numHits;
}
- Uchman21 April 27, 2016