I found this question in a interview blog. http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html Question No. 19
My understanding for "retrieve minimum in constant time" is, we should be able to find the minimum element in stack and to remove (pop) it in constant time. Correct me if I am wrong. My idea is to maintain a sorted linked list of items so that we can return the minimum and delete it from linked list in o(1) time. Push operation: Whenever a new items come, I will find the correct location for this new item in the sorted linked list and insert this item in linked list. Now I will take the address of this linked list item and push it on stack. Pop operation: I will take the linked list item address stored at stack[tos]. As I have address, I can delete the node from linked list as well. Retrieving minimum: Return the first item from the sorted linked list. o(1) But for popping this item address from stack, I need to reorganize the complete stack. It will have o(n) time and space complexity. Is there any way to improve it or other ways of solving it? --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
