Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

A practice interview question:

How would you design a stack which, in addition to push and pop, also has a function getMin which returns the minimum element? Push, pop and min should all operate in O(1) time.

class stackWithMin
{
private:
    std::vector<int> stack;
    std::vector<int> minLoc;
    int min, current, minCurrent;

public:
    stackWithMin()
    {
        min = NULL;
        current = 0;
        minCurrent = 0;
    }

    void print()
    {
        std::cout<<"Min: "<<min<<" --- ";

        for (int i=0;i<stack.size();i++)
        {
            std::cout<<""<<stack.at(i)<<", ";
        }
        std::cout<<""<<std::endl;
    }

    void push(int num)
    {
        stack.push_back(num);

        if(num<=min || current == 0)
        {
            minLoc.push_back(current);
            minCurrent++;
            min = num;
        }
        current++;
        print();
    }

    void pop()
    {
        if(current==0)
        {
            std::cout<<"Stack is empty"<<std::endl;
            return;
        }

        // Check if the number to be popped is the current lowests
        if(minLoc.at(minCurrent-1)==current-1)
        {
            if(minCurrent>1)
            {
                int loc = minLoc.at(--minCurrent-1);
                minLoc.pop_back();
                min = stack.at(loc);
            }
            // No more elements
            else
            {
                min = NULL;
            }
        }

        current--;
        stack.pop_back();
        print();
        return;
    }

    int getMin(){return min;}

};
share|improve this question
1  
Were you told to include print statements in all of the functions? Ideally, only print() should print something. –  Jamal 2 days ago
    
After thinking about it for a while I was convinced it is not possible. Guess I would have failed to get the job. –  nwp yesterday

2 Answers 2

Here are some things that may help you improve your code:

Simplify the algorithm

Although it would take more space to store, a simpler algorithm would be to simply use minLoc as the current minimum. If you did so, then getMin() would simply be return minLoc.back();

Eliminate redundant variables

Even if you don't care for that particular algorithm, you can remove the variables min, current and minCurrent and also simplify the code:

void push(int num)
{
    stack.push_back(num);
    if (minLoc.size() == 0 || num < stack[minLoc.back()]) 
        minLoc.push_back(stack.size()-1);
    print();
}

void pop()
{
    // Check if the number to be popped is the current lowest
    if(minLoc.size() && minLoc.back() == stack.size()-1)
        minLoc.pop_back();
    stack.pop_back();
    print();
}

int getMin() const {
    return minLoc.size() ? stack[minLoc.back()] : 0;
}

Use const where possible

The getMin function doesn't (and shouldn't) modify the underlying stack, so it should be declared const. The same is true for the print function.

Avoid using index variables

Rather than using an index variable i in the print routine and then calling at() for each iteration, use iterators instead. For example, you could use this:

std::copy(stack.cbegin(), stack.cend(), 
          std::ostream_iterator<int>(std::cout, ", "));

Omit empty strings

The current code for print includes this line:

std::cout<<""<<stack.at(i)<<", ";

There's no need for the empty string in that line.

Use whitespace to improve readability

To take the previously quoted line as an example, rewriting it with more whitespace makes it easier to read:

std::cout << stack.at(i) << ", ";

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Take care with signed versus unsigned

The code includes this line in the print function:

for (int i=0;i<stack.size();i++)

However, stack.size() is unsigned and i is signed. For consistency, it would be better to declare i as std::size_t which is the type returned by size().

Consider the user of the code

The std::vector::pop_back() returns void but provides a member function back() to allow a user of the code to access the last member before removing it from the vector. You might consider either returning the popped value in your implementation of pop or implementing a back function such as the one std::vector supplies.

share|improve this answer
    
Why is 0 the minimum of an empty stack? Also there is a pretty good reason why pop_back does not return the object it popped. –  nwp yesterday
    
@nwp: 0 is an arbitrary choice that appears to have been the intent of the original code. As for the other issue, in this code, there is no way to access any members of the stack except via print. I consider that a design flaw for a practical design. –  Edward yesterday

You wrote min = NULL; in two places. Any compiler would complain about that, if you compile with warnings enabled. (You do compile with warnings enabled, I hope?)

Your three instance variables min, current, and minCurrent seem to be redundant. current and minCurrent appear to be just current.size() and minLoc.size(), respectively. min is just current[minLoc.back()].

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.