Design Hit Counter


  • 1

    Write a hit counter for hits received in the past 5 minutes.

    The HitCounter has two methods:

    void hit()   // record a hit.
    
    long getHits()   // Return the number of hits in the last 5 minutes.
    

  • 0

    can you specify what is the maximum load of the counter? How many hits per second? Probably to fit in long ?


  • 0

    @elmirap Yes you can assume it fits in long.


  • 0

    @1337c0d3r I was thinking the same way as it was suggested in the design topic you offer us


  • 0

    Here is a suggestion. I assume that we use granularity second.ArrayDeque (thanks to @diptesh for the remind) is used, in which each element is time slot which corresponds to different seconds, when hit arrive. When hit arrives or information about it is looked for , list is resized according to the time.

    
    public class HitCounter {
        private final int WINDOW_SIZE = 300;
        class TimeSlot {
            public TimeSlot(long t) {
                time = t;
                hits = 1;
                
            }
            private long time;
            private long hits;      
        }
        
        private long hits;
        private long time;
    
        
        private Deque<TimeSlot> slots = new ArrayDeque<>(WINDOW_SIZE * 60);
        
        HitCounter() {
            time = System.currentTimeMillis()/1000;
        }
       private   void resize(long current) {    
            long before = current - WINDOW_SIZE;
            while (slots.size() > 0 && slots.getFirst().time < before) {
                hits -= slots.removeFirst().hits;             
            }
            if (slots.size() == 0) {            
                slots.add(new TimeSlot(current));
                
            }       
            time = slots.getFirst().time;
            
        }
        public void hit() {
            long current = System.currentTimeMillis()/1000;  
            if (time < current - WINDOW_SIZE)  {
                resize(current);           
            }
            else {
                if (slots.size() > 0 && slots.getLast().time == time) {
                    slots.getLast().hits++;               
                } else {
                    slots.add(new TimeSlot(current));
                }           
            }       
            hits++;
        }
    
        public long getHits() {
            long current = System.currentTimeMillis()/1000;       
            if (time < current - WINDOW_SIZE) 
                resize(current);
            return hits;
        }
    }

  • 0
    D

    @elmirap why not use ArrayDeque, instead of LinkedList. We get significant performance gain in ArrayDeque as compared to LinkedList.


  • 0

    @diptesh yes , good observation, I will edit implementation


  • 0

    @elmirap Great solution.

    I modified to use HashMap instead .

    Map<Long, Long> map = new HashMap<Long, Long>();
    Long hits = 0L, earliestTime = 0L;
    int SLOTS = 300 * 60;
    public void logHits(long time) { // time in seconds
        if(map.containsKey(time)) {
            map.put(time, map.get(time)+1);
        }else {
            map.put(time, 1L);
        }
        cleanUp(time);
        hits++;
    }
    
    public Long getHits(long time) { // time in seconds
        cleanUp(time);
        return hits;
    }
    
    public void cleanUp(long time) {
        while(time - earliestTime >= SLOTS) {
            if(map.containsKey(earliestTime)) {
                hits -= map.get(earliestTime);
                map.remove(earliestTime);
            }
            earliestTime = earliestTime + 1;
        }
    }

  • 0

    @andyreadsall , problem could be solved with maps, beacause we have only 300 entries (not so much)


  • 0
    B

    C++ implementation using std::deque

    #include<deque>
    #include<iostream>
    #include<chrono>
    #include<thread>
    #include<string>
    
    using namespace std;
    
    class HitCounter {
    private:
        typedef std::chrono::time_point<std::chrono::system_clock> hittime_t;
        struct _HitBucket {
            hittime_t timestamp;
            long hits = 0;
            _HitBucket() { timestamp = std::chrono::system_clock::now(); }
        };
        typedef struct _HitBucket hitbkt_t;
        deque<hitbkt_t> mBuckets;
        chrono::duration<unsigned> mDepth;
        long hits = 0;
    public:
        HitCounter(const unsigned size, const string name=""): mDepth{size} {};
    
        long getHits(void) { return hits; }
    
        void hit(void) {
            hittime_t now = std::chrono::system_clock::now();
    
            if(mBuckets.empty() or mBuckets.front().timestamp != now) {
                mBuckets.push_front(hitbkt_t());
            }
            mBuckets.front().hits++;
            hits ++;
            while(now - mBuckets.back().timestamp > mDepth) {
                hits -= mBuckets.back().hits;
                mBuckets.pop_back();
            }
        }
    };
    int main() {
        HitCounter hc10(10);
        HitCounter hc20(20);
    
        for(int i=0; i<40; i++) {
            std::this_thread::sleep_for(std::chrono::milliseconds(1000));
            for(int h=0; h<i; h++) {
                hc10.hit();
                hc20.hit();
            }
            cout << i << " hc10 " << hc10.getHits() << " ";
            cout << i << " hc20 " << hc20.getHits() << endl;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.