Interview Question

Software Development Engineer Interview(Student Candidate) Madison, WI

use stack to pop out the max num under O(1)

Answer

Interview Answer

2 Answers

0

my way is too complex...
Good answer would be using Class or 2 stacks, and keep record the current max

Interview Candidate on Feb 24, 2012
0

Using c++ and 2stack
#include <iostream>
#include <stack>

std::stack<int> S;

void addToStack(int value)
{
    std::stack<int> T;

    while(!S.empty() && (S.top() > value)) {
        int V = S.top();
        T.push(V);
        S.pop();
    }
    S.push(value);
    while(!T.empty())
    {
        S.push(T.top());
        T.pop();
    }

}

int getMaxValue()
{
    int value = S.top();
    S.pop();
    return value;
}

int main()
{
    addToStack(17);
    addToStack(15);
    addToStack(4);
    addToStack(16);
    addToStack(1);

    int max = getMaxValue();
    std::cout << max << std::endl;
}

Anonymous on Nov 12, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.