Super easy design O(1) hit() O(s) getHits() no fancy data structure is needed!


  • 128

    O(s) s is total seconds in given time interval, in this case 300.
    basic ideal is using buckets. 1 bucket for every second because we only need to keep the recent hits info for 300 seconds. hit[] array is wrapped around by mod operation. Each hit bucket is associated with times[] bucket which record current time. If it is not current time, it means it is 300s or 600s... ago and need to reset to 1.

    public class HitCounter {
        private int[] times;
        private int[] hits;
        /** Initialize your data structure here. */
        public HitCounter() {
            times = new int[300];
            hits = new int[300];
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            int index = timestamp % 300;
            if (times[index] != timestamp) {
                times[index] = timestamp;
                hits[index] = 1;
            } else {
                hits[index]++;
            }
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            int total = 0;
            for (int i = 0; i < 300; i++) {
                if (timestamp - times[i] < 300) {
                    total += hits[i];
                }
            }
            return total;
        }
    }

  • 0
    G

    Very cool!
    I was wondering why the C++ version of your algorithm cannot pass the OJ.

    class HitCounter {
    public:
        /** Initialize your data structure here. */
        HitCounter() {
            times.resize(300);
            hits.resize(300);
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            int idx = timestamp % 300;
            if (times[idx] != timestamp) {
                times[idx] = timestamp;
                hits[idx] = 1;
            } else {
                ++hits[idx];
            }
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            int res = 0;
            for (int i = 0; i < 300; ++i) {
                if (timestamp - times[i] < 300) {
                    res += hits[i];
                }
            }
            return res;
        }
    
    private:
        vector<int> times, hits;
    };

  • 0

    127 ms for java version


  • 0

    @grandyang I have just fixed the issue, please try again.


  • 0
    F

    Hi @xuyirui, why need to check times[idx] != timestamp?, is this means multiple hits on same second is allowed? like I can do : "hits(4), hits(5), hits(4)"? I am quite confused about this, please correct me if I am wrong.


  • 1

    the order in your example will never happen because the description says chronological order (ie, the timestamp is monotonically increasing). Let's say at time 5, there were 10 hits, you fill hits[5] = 10, then at time 605 you have hit(605), hit(605), hit(605). For the first hit(605), you want to reuse the spot hits[5] as 605 % 300 = 5. But you need to reset it to 0 first, then do hits[5]++ 3 times.


  • 0
    F

    I got your points! Thanks a lot!


  • 8

    Hi @xuyirui , thanks for your brilliant solution.

    I'm thinking about the follow up.

    What if there is 1000 hit(5) at time 5? Will there be a concurrent issue that many threads are trying to increment hit[5]? (In this problem, it seems there's no multi thread situation; however for a general hit counter, I think it will be a multithread.)

    I override your solution using AtomicInteger and AtomicIntegerArray which can handle the multithread situation. Please correct me if I'm on the wrong direction.

    import java.util.concurrent.atomic.AtomicIntegerArray;
    
    public class HitCounter {
    	AtomicIntegerArray time;
    	AtomicIntegerArray hit;
        /** Initialize your data structure here. */
        public HitCounter() {
            time  = new AtomicIntegerArray(300);
            hit = new AtomicIntegerArray(300);
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
        	int index = timestamp % 300;
        	if (time.get(index) != timestamp) {
        		time.set(index, timestamp);
        		hit.set(index, 1);
        	} else {
        		hit.incrementAndGet(index);//add one
        	}
            
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
        	int total = 0;
        	for (int i = 0; i < 300; i++) {
        		if (timestamp - time.get(i) < 300) {
        			total += hit.get(i);
        		}
        	}
        	return total;
        }
    }
    
    

  • 7
    A

    @coderBear changing two arrays to AtomicIntegerArray does not make it thread safe. For instance, two threads enter the if statement in hit() at the same time.


  • 0
    This post is deleted!

  • 0

    How it is giving correct answer when timestamp is 301? Thanks in advance


  • 0
    This post is deleted!

  • 0
    X

    How do we ensure this code is thread-safe


  • 0

    @xxie add a MUTEX lock for hit and getHits functions.


  • 0

    If we want to make it thread-safe, why don't we use only one array and use to store tuples and then use a MUTEX lock to protect this array?


  • 4

    Here's a Python version that is easy to get it work in multithread env.

    class HitCounter(object):
    
        def __init__(self):
            self.q = [(0, 0)] * 300
            
        def hit(self, timestamp):
            idx = timestamp % 300
            time, hit = self.q[idx]
            if time != timestamp:
                self.q[idx] = timestamp, 1
            else:
                self.q[idx] = time, hit + 1
    
        def getHits(self, timestamp):
            ans = 0
            for i in xrange(0, len(self.q)):
                time, hit = self.q[i]
                if timestamp - time < 300:
                    ans += hit
            return ans
    

  • 0
    F
    This post is deleted!

  • 0
    F

    Hi @xuyirui,
    quick question- is this code thread safe? It seems like multiple threads could access the hit and getHit methods at the same time- shouldn't they be synchronized methods?


  • 0
    J

    @shuxu Brilliant! Love it!


  • 0
    X

    Good idea!
    A bit improvements:

    private final int[][] hits = new int[300][2];
    
    /** Record a hit.
    @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        final int idx = timestamp % 300;
    
        if (hits[idx][0] != timestamp) {
            hits[idx][0] = timestamp;
            hits[idx][1] = 1;
        } else {
            hits[idx][1]++;
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        return Arrays.stream(hits).filter(e -> timestamp - e[0] < 300).mapToInt(e -> e[1]).sum();
    }
    

Log in to reply
 

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