Author Archives: Admin

Building a Stack with a getMax() function

Suppose you had a Stack class. Write a new class MaxStack which, in addition to push() and pop(), has a method getMax() which returns the largest item in the stack. Use your existing Stack class to store the stack’s contents.

Don’t just use pop() to “dig” through your stack to find the max—do something that lets you return the max in constant time.

Solution

We could have an instance variable where we hold the max, but there’s a problem—when we pop that item from our stack it’s no longer the max. Now we have to “dig” through our stack to find the new max. Ideally we’d keep track of the current max as well as what the new max will be when that max is popped.

The trick is to have two instances of Stack inside our MaxStack. One holds the actual stack contents, while the other (call it maxesStack) holds the maxes. Whenever we push() an item, if it’s larger than the top item in maxesStack, we also push it to maxesStack. Whenever we pop() an item, if it’s the same as the top item in maxesStack(), we also pop() it from maxesStack.

So at any given point we can get the overall max in constant time be peeking at the top item in maxesStack.

Reverse a String

A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is “the house is blue”, the return value would be “blue is house the”. the words are reversed, but the letters are still in order (within the word).

Continue reading