@Navin: I would use a linked list containing the value and date, with extra pointers to the next larger element and the next smaller element. New items are inserted at the head of the list. Then the next larger pointer is updated by searching the list of next larger pointers, beginning with the original head's next larger pointer, for the first element larger than the current element; if no larger element is found, set the next larger pointer to null. The next smaller pointer is updated similarly. When a request is made, the list formed by the next larger pointers, starting with the head node, is searched for the last item whose date differs from the current date by < k, and similarly the list formed by the next smaller pointers. Dave
On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote: > A set of integer values are being received (1 per day). Store these values > and at any given time, retrieve the min and max value over the last k days. > What data structures would you use for storing and retrieving ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/57HnzcO4goUJ. 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.
