implement a O(1) min function for Stack

Question

jh · Accepted Answer

have a data stack to store the integers and a min stack to store the min value until then.
When you pop check if the value popped is same as min, then pop from min stack as well

Srigopal Chitrapu · Answer

1. Create 2 stacks named RegularStack and MinStack.
2. RegularStack: Implement normal push(), pop() and top() functions. 
3. MinStack: Maintain the minimum element in RegularStack as its top.

    
1) Push: 
    While pushing an element into RegularStack, Compare this element with the top element in MinStack. 
    If it is smaller, then push that element into MinStack at the same time. 
    Else do nothing.
    
2) Pop:
    While popping an element out from RegularStack, Compare this element with the top element in MinStack. 
    If they are equal, we pop out the top element from MinStack at the same time. Otherwise, we do nothing.
    
3. Get:
    Peek element from MinStack and Return.

class StackOperations
{
    Stack RegularStack = new Stack();
    Stack MinStack = new Stack();
    StringBuilder StringBuilderObj = new StringBuilder(); 

    public void PushPopGetMinWithConstantTime()
    {
        Push(3);
        Push(4);
        Push(5);
        Push(1);
        Push(2);
        StringBuilderObj.Append("
Elements Pushed into Stack:
 3,   4,  5,  1,  2");
            
        int minElement = GetMinElement();
        StringBuilderObj.Append("

Min Element in Stack:	" + minElement.ToString());
        
        int poppedElement = Pop();
        poppedElement = Pop();
        StringBuilderObj.Append("

Elements 1,  2 popped out from Stack.	");

        StringBuilderObj.Append("

Remaining Elements in Stack:
 3,   4,  5");

        minElement = GetMinElement();
        StringBuilderObj.Append("

Min Element in Stack:	" + minElement.ToString());

        MessageBox.Show(StringBuilderObj.ToString());
    }

    public void Push(int elementToPush)
    {
        //Push element to RegularStack
        RegularStack.Push(elementToPush);

        //If the elementToPush is less than the currentMinElement in MinStack then insert elementToPush to MinStack
        //Else do nothing.
        int? currentMinElement = null;

        if (MinStack.Count > 0)
        {
            currentMinElement = MinStack.Peek();
        }

        if (currentMinElement == null || elementToPush < currentMinElement)
        {
            MinStack.Push(elementToPush);
        }
    }
    public int Pop()
    {
        if (RegularStack.Count == 0)
        {
            throw new Exception("No elements in stack to pop");
        }

        //Pop element from RegularStack.
        int elementPopped = RegularStack.Pop();

        //Get element from MinStack and check if it is same as elementPopped, then pop out it from the MinStack as well.
        int currentMinElement = MinStack.Peek();
        if (elementPopped == currentMinElement)
        {
            MinStack.Pop();
        }

        return elementPopped;

    }
    public int GetMinElement()
    {
        if (MinStack.Count == 0)
        {
            throw new Exception("No elements in stack to pop");
        }

        //Get element from MinStack and return.
        int currentMinElement = MinStack.Peek();
        return currentMinElement;
    }
}

v · Answer

update min element as part of push() and pop() methods

running · Answer

Implement stack using linked list with node having 3 fields(data,next,min). Every node keeps track of min node that is below it. So this way the top node always know the min value node.

Gaurav · Answer

#include

using namespace std;

struct Node{
	int _element;
	int _currentMinElement;
	Node *next;
	Node()
	{
		_element = 0;
		_currentMinElement = 0;
	}
};

class MyStack{
	Node *topNode;
	int _noOfElements;
public:
	void push(int elem);
	int pop();
	bool getCurrentMinElement(int &elem);
	bool top(int &elem);
	MyStack(){
		topNode = NULL;
		_noOfElements = 0;
	}
	~MyStack(){
		int cnt = 0;
		while(topNode)
		{
			pop();
		}
	}
};

void MyStack::push(int elem)
{
	Node *node = new Node();
	node->_element = elem;
	int x = 0;
	node->_currentMinElement = elem;
	if(getCurrentMinElement(x))
	{
		if(x _currentMinElement = x;
		}
	}
	node->next = topNode;
	topNode = node;
	_noOfElements++;
}

int MyStack::pop()
{
	if(!topNode && !_noOfElements)
		return -1;

	Node *deleteNode = topNode;
	int data = deleteNode->_element;
	topNode = topNode->next;
	delete deleteNode;
	_noOfElements--;
	return data;
}

bool MyStack::top(int &elem)
{
	if(!topNode && !_noOfElements)
		return false;

	elem = topNode->_element;
	return true;
}


bool MyStack::getCurrentMinElement(int &elem)
{
	if(!topNode && !_noOfElements)
		return false;

	elem = topNode->_currentMinElement;
	return true;
}

mliu · Answer

Implement a min heap as part of the Stack.

If asked for more detail, you can expand the answer by making insert and delete asynchronous from the Stack but the operations will always be kept in order.  Call to min will be blocked until all insert/delete is completed.

Anonimo · Answer

as part of the each element pushed on the stack, we also push what's the minimum until that element.
Pushing the minimum until that element is just min(newElement, minUntilLastElement).
Thus we always know in O(1) min for all elems in stack.

LinkedIn

Domanda di colloquio di LinkedIn

Risposte di colloquio

Aziende seguite

Ricerche di lavoro