One function suffices for counting events in the last some amount of minutes. Pass minutes as argument.
-- Shuaib http://twitter.com/ShuaibKhan http://www.bytehood.com/ On 03-Jun-2011, at 5:02 PM, Shuaib <aries.shu...@gmail.com> wrote: > 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.
