On Wednesday, July 18, 2012 4:26:11 AM UTC+8, Navin Kumar wrote: > > @Dave sir, > K is known in advance. Many people including me think stack as an > appropriate data structure but still i am not satisfied with this answer. > > In case K is not known in advance : according to your solution when a new > item is inserted next larger and next smallest item is searched.Isn't it > cause much overhead?? can we think a better data structure to optimize this > ? > > On Tue, Jul 17, 2012 at 10:52 PM, Dave <[email protected]> wrote: > >> @All: We seem to have different understandings of the problem. So Navin, >> as original poster, answer this question: Is k known in advance, or is it >> given in the request for the min and max elements. I assumed the latter, so >> that one request could ask for the max and min of the last 5 days and >> another could ask for the max and min for the last 100 days. Others seem to >> assume that k is known as the data are collected. >> >> 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/-/c58RGUBQobUJ. >> >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > For the purpose of finding the max element:
Keep an input-restricted queue with elements in non-strict descending order. Whenever a new element, says x, comes, remove the head if it is antiquated (not reside in the last k positions) and keep removing the last until it is greater then x. Retrieve the last element to get the max. Ditto for the min element. -- 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/-/7RKV57H0ppAJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
