In this article, let's tackle the leetcode Design Hit Counter.

The problem is to design a hit counter, which counts the number of hits received in the past 300 seconds. The initial interface looks like below.

class HitCounter {
    constructor() {

    }

    hit(timestamp: number): void {

    }

    getHits(timestamp: number): number {

    }
}

So method hit is called with a timestamp, we need to store this information somehow and return the hits count when the method getHits is called.

My first solution is very naive, which only uses an array to store all the hits and drop the old ones when the method getHits gets called.

class HitCounter {
  private log: number[];
  constructor() {
    this.log = [];
  }

  hit(timestamp: number): void {
    this.log.push(timestamp);
  }

  getHits(timestamp: number): number {
    let i = 0;
    while (i < this.log.length) {
      if (timestamp - this.log[i] < 300) break;
      i++;
    }
    this.log = this.log.slice(i);
    return this.log.length;
  }
}

As you can see, inside the method getHits, I use a loop from the start. This makes the time complexity as O(N).

We can use the binary search method to optimize it and reduce the time complexity to O(log(N)).

class HitCounter {
  private log: number[];
  constructor() {
    this.log = [];
  }

  hit(timestamp: number): void {
    this.log.push(timestamp);
  }

  getHits(timestamp: number): number {
    const i = binarySearch(this.log, 0, this.log.length - 1, timestamp - 300 + 1);
    this.log = this.log.slice(i);
    return this.log.length;
  }
}

function binarySearch(
  arr: number[],
  start: number,
  end: number,
  offset: number
): number {
  if (start > end) {
    return start;
  }
  const mid = Math.floor((end - start) / 2) + start;
  if (arr[mid] >= offset) {
    return binarySearch(arr, start, mid - 1, offset);
  } else {
    return binarySearch(arr, mid + 1, end, offset);
  }
}

I was satisfied with this solution but this problem comes with a follow-up question: What if the number of hits per second could be huge? Does your design scale?

The answer is: Yes. If we have many hits, the memory could blow up.

The handle this case, we need to make use of one condition of this problem: the 300 seconds. We only need to store hits 300 seconds before. So we don't need an infinite array, we can use an array with a size of 300. Then we also need to consider that the hits may have the timestamp, so the real number of elements may probably exceed 300. We could solve this by grouping together the hits with the same timestamp.

With this idea, we first initialize an array with a length of 300 and use it like a queue. But in this way, we may end up with many enqueue and dequeue operations. To further optimize this part, we could make use of the idea of circular buffers. So this is how it works. When a new hit comes, we calculate its modulo value as the key. If the key is already taken, we compare their timestamp. If they are equal, which means the same timestamp, so we just add the hits count. If not, then we can just rewrite the key value. As you can see, in this way, we don't need to do operations like adding or removing elements of the array. What we do is just index access and the time complexity is reduced into O(1).

class HitCounter {
  // [[timestamp, hits]]
  private log = Array.from({ length: 300 }, () => [0,0]);
  constructor() {}

  hit(timestamp: number): void {
    const key = timestamp % 300;
    if (this.log[key][0] === timestamp) {
      this.log[key][1] += 1;
    } else {
      this.log[key] = [timestamp, 1]
    }
  }

  getHits(timestamp: number): number {
    return this.log.reduce(
      (accu, cur) => (timestamp - cur[0] < 300 ? accu + cur[1] : accu),
      0
    );
  }
}