Software Engineer Survival Diary

Max Stack problem and solution

Practical Data Structure in Action

source: etsy.com

In the previous article, I talked about HacktoberFest this year. Today I would like to talk about some popular coding interview questions. And at the same time a little walkthrough on the data structure topic. Let’s get started.

Max stack problem is something that can test a candidate’s logical thinking on data structure and big O concepts when hiring some developer role. Here’s the question statement:

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object.

void push(int x) Pushes element x onto the stack.

int pop() Removes the element on top of the stack and returns it.

int top() Gets the element on the top of the stack without removing it.

int peekMax() Retrieves the maximum element in the stack without removing it.

int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

The requirement is important, here it requires us to have O(log N) for each other call, including the popMax. Therefore, a traditional solution like using a stack to store will not work, since the popMax operation would require O(N) time. Link

Re-visiting Data Structure:

source: mygreatlearning.com

If it is to implement a Stack, one can do it with one of the linear data structures, such as Array or LinkedList. However, for this case we also need to fulfill pop/peek the max ( the value) from the stack, somehow additional thoughts must be considered. When it comes to getting the Max out of some items, you can go for non-linear data structures, and some kinds of tree data structures are the proper way to go. To quickly answer this question I will suggest having 2 data structures in my class, one is for normal stack operations (e.g. push/pop with its natural order), and one is for the max operations (peekMax, popMax with respect to the values). I would implement each using a balanced tree data structure, such as the TreeSet offered by Java Collection. A balanced tree is perfect for keeping all elements sorted in some specified order dynamically. So, now one is for Order and one is for Values.

Algorithm

As discussed, we need to maintain two balanced trees: one is in pushing order (orderTree), and another is sorted by values (valueTree).

To implementpush , we need to push the element into both two balanced trees, orderTree and valueTree

To implementtop and peekMax, we only need to return the last element value of orderTree for top query, and the last element value of valueTree for peekMax, since orderTree and valueTree are sorted by the order and values.

To implementpop and popMax, we call the TreeSet’s remove method, which is a find and remove method of performace O(log N), for the returned element in both two balanced trees. For pop, we first remove the last element in orderTree, and then remove the element in valueTree. Whereas for popMax, we first remove the last element in valueTree, and then remove the element in orderTree.

Conclusion

I hope my article helps you in more thinking about data structure design. If you like this article, please subscribe and follow my medium as it will help grow to reach a broader scope of audience. Thanks.