Re: [algogeeks] Appropriate data structure
For using a stack in order to achieve O(n) time, we can modify push and pop as follows(assuming we want max): While pushing, compare the top of the stack with the element to be pushed(say x). If xtop, just push normally. Else, pop elements until topx. Keep an eye on the border cases as well. Thus top will always be containing the maximum, which can be retrieved obviously in O(1) time. Similar algo for pop can be formulated. regards. On Tue, Jul 17, 2012 at 9:19 AM, Tushar tushicom...@gmail.com wrote: can you please elaborate on usage of stack to do it in O(1)? -- 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/-/8jTvBVdzsmYJ. 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.
Re: [algogeeks] Appropriate data structure
steps: 1) make max heapify and min heapify for first k days 2)for the next day... remove first element from max heapify and min heapify then add new element to existing max heapify and min heapify . 3) Then return max and min in O(1)from max heapify and min heapify . PRAVEEN RAJ DELHI COLLEGE OF ENGINEERING -- 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.
Re: [algogeeks] Appropriate data structure
can you please elaborate on usage of stack to do it in O(1)? -- 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/-/8jTvBVdzsmYJ. 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.
Re: [algogeeks] Appropriate data structure
Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8J. 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.
Re: [algogeeks] Appropriate data structure
It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8J. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/peWhqjKLIH8J. 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.
Re: [algogeeks] Appropriate data structure
I think stack would solve the purpose. please comment. On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.com wrote: It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8Jhttps://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/peWhqjKLIH8J. 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.
Re: [algogeeks] Appropriate data structure
Oh ya sorry. I thought we have to retrieve kth min and max, in which case heap can be used. Here, we can either use stack or map. Map can be from a date(which increases by 1 daily) to a value, as only one value is received per day. Keeping in mind memory constraints, stack is better. Map is an otherwise safe solution. regards. On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar algorithm.i...@gmail.comwrote: I think stack would solve the purpose. please comment. On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.comwrote: It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8Jhttps://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/peWhqjKLIH8J. 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.
Re: [algogeeks] Appropriate data structure
I think by using min/max heap we can fetch the kth largest/smallest data from the heap. But here there is one more point how to ensure that the data is smallest in last kth day. Here you can use interval/segment(augmented version of heap tree) tree, where u can store the interval/segment on the basis of date and retrieve the same information. On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8J. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ypiCXt9_1BQJ. 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.
Re: [algogeeks] Appropriate data structure
agree with naveen On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar algorithm.i...@gmail.comwrote: I think stack would solve the purpose. please comment. On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.comwrote: It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8Jhttps://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/peWhqjKLIH8J. 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.
Re: [algogeeks] Appropriate data structure
Stack will do it... and min or max can be even retrieved in O(1) ... On Sun, Jul 15, 2012 at 6:36 PM, adarsh kumar algog...@gmail.com wrote: Oh ya sorry. I thought we have to retrieve kth min and max, in which case heap can be used. Here, we can either use stack or map. Map can be from a date(which increases by 1 daily) to a value, as only one value is received per day. Keeping in mind memory constraints, stack is better. Map is an otherwise safe solution. regards. On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar algorithm.i...@gmail.comwrote: I think stack would solve the purpose. please comment. On Sun, Jul 15, 2012 at 5:42 PM, enchantress elaenjoy...@gmail.comwrote: It says K days if you keep heap the order of values gets disturbed. How are last k values accessed then? On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote: Min or max heap accordingly. This will do the job in O(log n) time. On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar algorithm.i...@gmail.comwrote: 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/-/2AhV1Xn3jD8Jhttps://groups.google.com/d/msg/algogeeks/-/2AhV1Xn3jD8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- 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/-/peWhqjKLIH8J. 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. -- best wishes!! Vaibhav -- 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.
