brother try this
push(x)
{
if stack.empty()
{
stack.push(x);
stack.push(x);
}
else
{
if x > stack.top()
{
min = stack.top()
stack.push(x)
stack.push(min)
}
else
{
stack.push(x)
stack.push(x)
}
}
}
pop()
{
stack.pop()
return stack.pop()
}
min()
{
return stack.top()
}
On Wed, Oct 7, 2009 at 2:01 AM, Manisha <[email protected]> wrote:
>
> 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 [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
-~----------~----~----~----~------~----~------~--~---
