TreeSet solution


  • 0
    H

    The idea is to use a node to record:

    1. how many times a timestamp is hit and
    2. how many hits in the last 300 seconds.

    The nodes are organised into a binary search tree,

    When adding a new node at the end, we use the last node's accumulated count minus count of all nodes in the front which fall outside of the window.

    In the test cases getHits can use a timestamp which is bigger than the last hit timestamp, therefore I added the weird overload hit(int, boolean).

    public class HitCounter {
    
    private static class CountNode {
        int selfCount; //just this second
        int accumulatedCount; //300 from here.
    
        CountNode(int selfCount, int accumulatedCount) {
            this.selfCount = selfCount;
            this.accumulatedCount = accumulatedCount;
        }
    
        void increase() {
            this.selfCount++;
            this.accumulatedCount++;
        }
    }
    
    private static final int PERIOD = 300;
    private TreeMap<Integer, CountNode> index = new TreeMap<>();
    
    /**
     * Initialize your data structure here.
     */
    public HitCounter() {
    }
    
    /**
     * Record a hit.
     *
     * @param timestamp - The current timestamp (in seconds granularity).
     */
    public void hit(int timestamp) {
        hit(timestamp, true);
    }
    
    private void hit(int timestamp, boolean hit) {
    
        Map.Entry<Integer, CountNode> last = index.lastEntry();
        if (last == null) {
            if (hit)
                index.put(timestamp, new CountNode(1, 1));
        } else {
            if (last.getKey() == timestamp) {
                if (hit)
                    last.getValue().increase();
            } else {
                int minKey = timestamp - PERIOD + 1; //inclusive
                if (last.getKey() < minKey) {
                    index.clear();
                    if (hit)
                        index.put(timestamp, new CountNode(1, 1));
                } else {
                    int totalSoFar = last.getValue().accumulatedCount;
                    while (index.firstKey() < minKey) {
                        totalSoFar -= index.pollFirstEntry().getValue().selfCount;
                    }
                    int val = hit ? 1 : 0;
                    index.put(timestamp, new CountNode(val, totalSoFar + val));
                }
            }
        }
    }
    
    /**
     * Return the number of hits in the past 5 minutes.
     *
     * @param timestamp - The current timestamp (in seconds granularity).
     */
    public int getHits(int timestamp) {
        hit(timestamp, false); //push timestamp forward
        Map.Entry<Integer, CountNode> entry = index.floorEntry(timestamp);
        if (entry == null)
            return 0;
        return entry.getValue().accumulatedCount;
    }
    

    }


Log in to reply
 

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