CareerCup

To count # of requests
Maintain a circular queue<int> of size 3600*(# sample per second). That is, if you are sampling every millisecond then (# of sample per second is 1000)
Now, if you request last 1 hr then sum all elements in the queue,
if you request last 1 min, then sum top 60*1000 elements
if you request last 1 sec, then sum top 1000 elements

the interface must be something as below , each event must have the capability of reporting itself , on occurrence . The Event class will have something like this interface

class Event
{
private:
int code ;
public :
Event(int code);
abstract notify();// do the purpose of the event and call the register method of the Register class
}

class Register
{
Register(int fno) ;
RegisterEvent(int code) ; // register this event with number "code"
private:
int lasthr ;// the number of events in the lasthour
int lastmin ;// the number of events in the lastmin , updated with every call to RegisterEvent
time_t time1 , time2 ;// to calculate the time
int alloc_new_file(); // the new file is allocated , which gives the new file , if the new file is overidden ;
}
many other choices are there for handling the overflow problem , but this seems to be the fastest

The key point here is about how to store the events and report them. Considering the storage space and reporting method, you do not need to store all events but dynamically aggregate them for saving the space.

Assuming we only need the two counters (last hour\minute) here is my idea:
keep a buffer of pairs in the main memory <start time, secondery memory address>. Keep aside the start and end of this buffer. Every time a new event is entered: iterrate from the start, deallocate the memory of an event which is older than 1 hour and decrement the last-hour-events by one. enter your new event at the end and increment the counter by one.

Corrections are welcome.

class Register {
  private:
    int counters[3600];

  public:

    Register() {
      for(int i = 0; i < 3600; ++i) counters[i] = 0;
    }

    void add(const Event& e) {
      long time = e.timestamp; /* In Seconds */
      int bucket = time % 3600;
      counters[bucket]++;
    }

    long getLastHour() {
      long sum = 0;
      for(int i=0; i < 3600; ++i) sum += counters[i];
      return sum;
    }

    long getLastMinute() {
      long now = time(NULL);
      long sum = 0;
      for(int i = now; i > now - 60; --i) {
        sum += counters[i%3600];
      }
      return sum;
    } 
};

we can use splay tree for this. In this we can keep adding the new nodes to the top.