Implement a hit counter that fits the following interface:

public interface HitCounter {
  // Registers a hit at the timestamp.
  public void hit(int timestamp);

  // Returns the number of hits within 5 minutes of the timestamp.
  public int getHits(int timestamp);
}

getHits is always going to be called with a timestamp at least as large as the largest timestamp you've seen so far. For this reason, a queue would be extremely inefficient.

The hits might come out of order. For example:

HitCounter hitCounter = new HitCounter();
hitCounter.hit(10);
hitCounter.hit(9);
hitCounter. getHits(100); // returns 2
hitCounter.hit(201);
hitCounter.hit(1);
hitCounter. getHits(400); // returns 2 (100 and 201)

Follow up: Make it threadsafe.