Walmart Labs Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
@LoveCoding : What abt if we have space constraint then how to design
My Openion :- Implement a separate minStack that contain only min data like
i/p - 10 ->5->12->14->0->8->11
min Stack - 10->5->0
pop operation design like if is popped from Main stack then pop from minstack also else pop from main stack only
@satveer: Yes, maintaining another stack is a solution. But we need to be careful about duplicate elements. If the current value is equal to the top of the " minimum stack" then also we need to push the element in both the stacks, i.e. the "main stack" and the "minimum stack".
Or may be we may store the count of the elements in the "minimum stack" with the elements. In that way, we may save space.
To keep the minimum takes time!
When adding a new entry to the stack it is easy. But when removing - it is the hard nut.
To keep a heap - well, pop will remove the entry from the stack but heapify has a cost of O(log(N)) as far as I know. So pop is not O(1) then.
Did I miss something?
+1
I do not see a way to find min in O(1).
For example if we do pop() which removed min element from stack, now I want min(), so how do we find it in O(1) time?
struct StackNode
{
int data;
StackNode *min;
StackNode *prev;
StackNode(int data = INT_MAX, StackNode *ptr = NULL, StackNode *minPtr = NULL) : data(data),prev(ptr),min(minPtr) {}
};
void Push(int data,StackNode **headPtr)
{
if(*headPtr == NULL)
{
*headPtr = new StackNode(data,NULL,NULL);
(*headPtr)->min = *headPtr;
return;
}
else
{
StackNode *temp = new StackNode(data,*headPtr,NULL);
if((*headPtr)->min->data < data)
{
temp->min = (*headPtr)->min;
}
else
{
temp->min = temp;
}
(*headPtr) = temp;
}
}
void Pop(StackNode ** headPtr)
{
if(*headPtr == NULL)
{
printf("Stack is Empty");
}
else
{
StackNode *temp = *headPtr;
(*headPtr) = (*headPtr)->prev;
delete temp;
temp = NULL;
}
}
int Top(StackNode *headPtr)
{
if(headPtr == NULL)
{
printf("Stack is Empty");
}
else
{
printf("Data At Top = %d\n",headPtr);
return headPtr->data;
}
}
int FindMin(StackNode *headPtr)
{
if(headPtr == NULL)
{
printf(" \nStack is Empty\n");
return -1;
}
else
{
return headPtr->min->data;
}
}
Maintain another stack minStack to keep track of the min elements.
We need to be careful for duplicates.
Here is a complete program -:
#include<iostream>
#include<stack>
using namespace std;
stack<int> a;
stack<int> minStack;
void insert(int x);
int remove();
void display();
int minimum();
int main()
{
int ch;
int x;
do
{
cout<<"Main Menu\n1 Push\n2 Pop\n3 Find Minimum\n4 Display\n5 Exit\nEnter your choice: ";
cin>>ch;
switch(ch)
{
case 1: cout<<"Enter element to be pushed: ";
cin>>x;
insert(x);
break;
case 2:cout<<"Element popped: "<<remove()<<endl;
break;
case 3:cout<<"Minimum element in the stack: "<<minimum()<<endl;
break;
case 4: display();
break;
case 5: exit(0);
break;
default: cout<<"No such option!!!"<<endl;
break;
}
}while(ch!=5);
return 0;
}
void insert(int x)
{
a.push(x);
if(minStack.empty() || x<=minStack.top())
{
minStack.push(x);
}
}
void insert(int x)
{
a.push(x);
if(minStack.empty() || x<=minStack.top())
{
minStack.push(x);
}
}
int remove()
{
if(a.empty())
{
cout<<"Stack underflow!!!";
return -9999;
}
int temp=a.top();
a.pop();
if(temp==minStack.top())
{
minStack.pop();
}
return temp;
}
void display()
{
stack<int> temp=a;
while(!temp.empty())
{
cout<<temp.top()<<" ";
temp.pop();
}
cout<<endl;
}
int minimum()
{
if(minStack.empty())
{
cout<<"Stack underflow!!!"<<endl;
return -9999;
}
else
{
return minStack.top();
}
}
class MinStack {
private def data = []
private def minData = []
def findMin(){
checkEmpty()
return minData[minData.size()-1]
}
void push(val){
data += val
if( minData.isEmpty() ){
minData.push(val)
}
else if( minData[minData.size()-1] > val ){
minData.push(val)
}
}
def pop(){
checkEmpty();
def val = data.pop()
if( val == minData[minData.size()-1] ){
minData.pop()
}
return val
}
private void checkEmpty(){
if( data.isEmpty() ){
throw new IllegalStateException("stack is empty")
}
}
}
You can accomplish O(1) time complexity, by using extra space to keep track of the minimum, during push and pop operations.
Method 1:
Push the minimum so far and the new element in the stack as a pair, when you add the element to the stack. This will require double the space size of the stack, because for each element, you also save the minimum. Therefore, the space complexity is Big_Theta(n)
Method 2:
Keep another stack and push the min values along with the count of the min as a pair to the let's say, min_stack. For instance, when you push the element to the stack, if it's the new minimum, then push it to the min stack and set the count 1, if the new element is equal to the min value at the top of the min_stack, then increment the count.
In the second method, the implementation is a little bit more complex compared to the 1st method because of the cases when you do push and pop on the main stack. Heuristically, the additional space will be reduced compared to method 1, but in the worst case, where each element pushed is less then the previous element, it is still Big_Theta(n)
public class MinList<T extends Comparable> {
public MinList() {
super();
}
public MinList(T data) {
this.setData(data);
}
private MinList<T> next;
private T min;
private T data;
private MinList<T> head;
public static void main(String[] args) {
MinList<Integer> minList = new MinList<Integer>();
int[] a = {10,5,20,6,4,30,1};
for(int i:a) {
minList.push(i);
}
System.out.println(minList.getMinimum());
System.out.println(minList.pop());
System.out.println(minList.pop());
System.out.println(minList.getMinimum());
}
public void push(T data) {
MinList<T> head = this.getHead();
MinList<T> item = new MinList<T>(data);
if (this.getHead() == null) {
this.setHead(item);
item.setMin(item.getData());
} else {
item.setNext(this.getHead());
this.setHead(item);
if(item.getData().compareTo(item.getNext().getMin()) < 0) {
item.setMin(item.getData());
}
else {
item.setMin(item.getNext().getMin());
}
}
}
public T pop() {
MinList<T> item = this.getHead();
this.setHead(item.getNext());
item.setNext(null);
return item.getData();
}
public T getMinimum() {
return this.getHead()!=null?this.getHead().getMin():null;
}
public void setNext(MinList<T> next) {
this.next = next;
}
public MinList<T> getNext() {
return next;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setHead(MinList<T> head) {
this.head = head;
}
public MinList<T> getHead() {
return head;
}
public void setMin(T min) {
this.min = min;
}
public T getMin() {
return min;
}
public String toString() {
return this.getData()!=null?this.getData().toString():null;
}
}
It depends on how far we would like to go on "Min Value". Let's assume we would like to know the min value at all time, i.e., after the deletion as well. We can maintain a min-heap of the entire dataset in addition to the stack. In contrast, if we would like know the kth smallest, we can maintain a max-heap of size k of the entire dataset. Pseudo code is something like this:
for(i=0;i<k;i++)
heap[i]=a[i];
buildMaxHeap(heap,k);
for(i=k;i<n;i++)
{
if(a[i]<heap[0])
{
heap[0]=a[i];
MaxHeapify(heap,0);
}
}
hence the min value is always heap[0].
We should remove the deleted values from the heap upon their removal from the stack.
Lately I've been spending some time on designs. Here's a sample generic implementation, that develops upon standard Stack design:
/*
Base Stack class
*/
#define DEFAULTSIZE 10
template<class T>
class Stack{
protected:
T *elems;
int top;
int max;
public:
Stack(int size = DEFAULTSIZE):max(size), top(-1){
elems = new T[max];
}
~Stack(){
delete elems;
}
virtual void push(const T& val);
virtual void pop();
bool isEmpty();
bool isFull();
const T& getTop();
};
template<class T>
bool Stack<T>::isEmpty(){
return top < 0;
}
template<class T>
bool Stack<T>::isFull(){
return (top == (max-1));
}
template<class T>
void Stack<T>::push(const T& val){
if(isFull())
return;
elems[++top] = val;
}
template<class T>
const T& Stack<T>::getTop(){
int val;
if(isEmpty())
return val;
return elems[top];
}
template<class T>
void Stack<T>::pop(){
if(isEmpty())
return;
--top;
}
/*
Derived MinStack class
adding desired extra constraints
*/
template<class T>
class MinStack:public Stack<T>{
T * minElems;
int minTopIdx;
public:
MinStack(int size = DEFAULTSIZE):Stack<T>(size), minTopIdx(-1){
minElems = new T[this->max];
}
~MinStack(){
delete minElems;
~Stack<T>();
}
virtual void push(const T& val);
virtual void pop();
const T& getMin();
};
template<class T>
void MinStack<T>::push(const T& val){
if(this->isFull())
return;
T minVal = (this->isEmpty())?val:getMin();
if(minVal >= val){
//push onto both stacks
minElems[++minTopIdx] = val;
}
this->elems[++(this->top)] = val;
}
template<class T>
void MinStack<T>::pop(){
if(this->isEmpty())
return;
if(this->getTop() == getMin()){
--minTopIdx;
}
--this->top;
}
template<class T>
const T& MinStack<T>::getMin(){
T dummy;
if(this->isEmpty())
return dummy;
return minElems[minTopIdx];
}
Hope it helps.
Further ideas: :)
Rather than having MinStack, derive Stack with a generic constraint.
Have an extra field in stack that tracks the min so far.
- loveCoding August 13, 2013