Using a data structure such as a queue to manage poping out no more needed records, and adding new ones to the front will reduce the shifting carried out in a simple array based approach. For time difference, store each event's timestamp as epoch time. That requires only one variable and difference calculation would be lot easier. Rest seems ok.
-- Shuaib http://twitter.com/ShuaibKhan http://www.bytehood.com/ On 03-Jun-2011, at 4:34 PM, ankit sambyal <ankitsamb...@gmail.com> wrote: > Here is the algo by which I would have approach it : > > int array[MAX_SIZE]; > int top; //global variable which holds the index of the top of the array > struct Event > { > int event_code; > int hours; > int mins; > int seconds; //to hold the time at which the evemt occured > }; > void recordEvent(Event e) > { > if(top<MAX_SIZE - 1) > { > Add event to the top of the array > top++; > } > else > { > remove 100 elements from the bottom of array by shifting > the elements of the array down by 100 times > Change the top accordingly > Now add the event to the top of the array > top++; > } > } > > > int numEventsInLast1min() > { > int count=0,i=top; > while(1) > { > Calculate the difference in the present time and the time of > the event which is at the top of the array > if(difference <= 1 min) > count++; > else > break; > } > return count; > } > > > int numEventsInLast1hour() > { > int count=0,i=top; > while(1) > { > Calculate the difference in the present time and the time of > the event which is at the top of the array > if(difference <= 1 hour) > count++; > else > break; > } > return count;} > > > The amortized cost of recording an event is O(1). But it may take a > lot of time for some events because of shifting. Any clarifications > required, please comment... > > > Ankit Sambyal > BITS Pilani > > > > > > > > On Fri, Jun 3, 2011 at 2:06 AM, Nate <nate.archibal...@gmail.com> wrote: >> Question: Design a component that implements the following >> functionality.. >> 1) Record an Event (For the sake of simplicity, treat the Event as an >> integer code) >> 2) Return the number of Events recorded in the last one minute. >> 3) Return the number of Events recorded in the last one hour. >> i.e implement the following interface >> - Design the interface first >> - Give the implementation detail. >> <<>> >> Open ended question: >> What if there isn't enough storage available to store each individual >> event ? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
