Java solution using a HashMap -- seems very fast


  • 0
    A
    class HitCounter {
    
    // algorithm 2017/09/04: each hit has a TTL 1=>300, 2=>301, 3=>302
    //  whenever a call to either hit, or getHits is called, we clear the TTL cache
    
    /** Initialize your data structure here. */
    public HitCounter() {
    
    }
    
    /** Record a hit.
     @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        enforceTTL(timestamp);
    
        int TTL         = timestamp + 299;
        Integer hitsObj = TTLCache.get(TTL);
    
        if (null == hitsObj) {
            TTLCache.put(TTL, 1);
        } else {
            TTLCache.put(TTL, hitsObj + 1);
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
     @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        enforceTTL(timestamp);
    
        int result = 0;
        for (Map.Entry<Integer, Integer> entry : TTLCache.entrySet()) {
            assert(entry.getKey() >= timestamp);
            result += entry.getValue();
        }
        return result;
    }
    
    // private
    private void enforceTTL(int timestamp) {
        Iterator<Map.Entry<Integer, Integer>> iterator = TTLCache.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> entry = iterator.next();
            if (entry.getKey() < timestamp) {
                iterator.remove();  // stale entry?
            }
        }
    }
    
    HashMap<Integer, Integer> TTLCache = new HashMap<>();
    

    }


Log in to reply
 

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