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.
