c# O(S) hit/GetHits using arrays


  • 0
    public class HitCounter
        {
            int maxSeconds = 300;
            int counterBase;
            int windowCounter;
            int[] counters, snapshot;
            /** Initialize your data structure here. */
            public HitCounter()
            {
                counters = new int[maxSeconds + 1];
                snapshot = new int[maxSeconds + 1];
                counterBase = 0;
                windowCounter = 0;
            }
    
            /** Record a hit.
                @param timestamp - The current timestamp (in seconds granularity). */
            public void Hit(int timestamp)
            {
                if (timestamp - counterBase > maxSeconds)
                {
                    // Snapshot and then add to fresh window.
                    TakeSnapshot(timestamp);
                }
    
                counters[timestamp - counterBase]++;
                windowCounter++;
            }
    
            /** Return the number of hits in the past 5 minutes.
                @param timestamp - The current timestamp (in seconds granularity). */
            public int GetHits(int timestamp)
            {
    
                int retVal = 0;
                if (timestamp - counterBase > maxSeconds)
                {
                    // Snapshot and then add to fresh window.
                    TakeSnapshot(timestamp);
                }
    
                int prevWindow = counterBase > 0 ? counterBase - (timestamp - maxSeconds) : 0;
    
                // We need to take inWindow elements from current window and prevWindow elements from the previousWindow
                retVal += windowCounter;
                if (prevWindow > 0)
                {
                    // We need to get the time from reqStart to end;
                    int snapshotIdx = maxSeconds - prevWindow + 1;
                    retVal += snapshot[snapshotIdx];
                }
    
                return retVal;
            }
    
            private void TakeSnapshot(int timestamp)
            {
                int nextCycle = timestamp/maxSeconds, curCycle = counterBase/maxSeconds;
                if (nextCycle - curCycle == 1)
                {
                    int prevSum = 0;
                    for (int i = maxSeconds; i >= 0; i--)
                    {
                        snapshot[i] = (counters[i] + prevSum);
                        prevSum = snapshot[i];
                    }
                }
                else {
                    Array.Clear(snapshot, 0, maxSeconds + 1);
                }
                
                counterBase = nextCycle * maxSeconds;
                Array.Clear(counters, 0, maxSeconds+1);
                windowCounter = 0;
            }
        }
    

Log in to reply
 

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