0ms Go O(1) Hit, O(log(N)) GetHits, Binary Search


  • 0
    A
    
    type bucket struct {
        ts, sum int
    }
    
    type HitCounter struct {
        bkts []bucket
    }
    
    const (
        maxTime = 5 * 60
    )
    
    func Constructor() HitCounter {
        return HitCounter{ bkts: make([]bucket, 1) }
    }
    
    func (this *HitCounter) Hit(timestamp int)  {
        last := len(this.bkts)-1
        if this.bkts[last].ts < timestamp { // New bucket time
            this.bkts = append(this.bkts, bucket{ts:timestamp, sum: 1 + this.bkts[last].sum}) // Carry the sum forward
            return
        }
        this.bkts[last].sum++ // Old bucket, just add
    }
    
    func (this *HitCounter) GetHits(timestamp int) int {
        var sub int
        cutOff := timestamp - maxTime
        earliest := sort.Search(len(this.bkts), func(i int) bool {
            return this.bkts[i].ts > cutOff
        })
        if earliest >= 1 { // earliest is the lowest bucket that is IN the range, so we subtract the sum from the previous
            sub = this.bkts[earliest - 1].sum
            defer func(){ this.bkts = this.bkts[earliest-1:] }() // Cleanup, but leave a bucket for correctness
        }
        return this.bkts[len(this.bkts)-1].sum - sub    
    }
    
    

Log in to reply
 

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