It all depends on the definition of no *extra space.*For me the question was ambigous....
On Mon, Aug 22, 2011 at 12:27 AM, Amol Sharma <[email protected]>wrote: > i'll go with the first option...since no extra space is allowed.... > > this ques was asked by amazon in written in our college.....don't know the > correct answer...it all depends on what > "Most efficient data structure" is............i.e what option they do > frequently min or push or pop.... > > btw....what's the right answer?? > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> > > > > > > On Sun, Aug 21, 2011 at 11:07 PM, dilip makwana > <[email protected]>wrote: > >> If we can have additional O(n) space than all operations wil take O(1) >> ..additional MinStack implementation.. >> >> But if we are not allowed O(n) space then at the cost of GetMinimum to >> become O(1) we have to sacrifice for push and pop to be O(n)..{this is not >> mentioned in option} >> >> So most efficient will be O(1) time for each >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> 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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
