It is Monday evening. Yesterday, with the help of my wife we cleaned a spot in my home office and put together the 4K monitor and computer. Later I set up the computer. The monitor is impressive. The only this missing for today is to connect the Azure Kinect DK and start experimenting.
Today I solved (at least I think) the 3.2 question Stack Min from the book “Cracking the Coding Interview”. The question follows: “How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element. As I am reading the question I want to state that when I was solving the problem, I agreed with the imaginary interviewer that min function would return the min value. We could also have the solution return the minimum element (the actual node), but we decided that that was not the scope of the question.
After the two hour notification came up, I was so fried that I decided to call it 
a day. Today is Tuesday and the clock is ticking. I plan on finishing this blog entry and then tackling the first question from the next chapter in the book. Let’s see how it goes.
By the way, I took a look at the answer for this question and it is different. The answer uses two stacks. I suggest that if you are interested in solving challenges that you get a copy of “Cracking the Coding Interview” and move in the book in order. I am hopping from chapter to chapter. When done I will address the next two questions from each chapter. I will repeat until I have solved all the problems.
Let’s first take a look at the screen capture of the Eclipse IDE.
main <<< stack.min: 1 main <<< stack.pop: 1 main <<< stack.min: 2 main <<< stack.pop: 2 main <<< stack.min: 3 main <<< stack.pop: 3 main <<< stack.min: 4 main <<< stack.pop: 4 main <<< stack.min: 5 main <<< stack.pop: 5 main <<< stack.min: 6 main <<< stack.pop: 6 main <<< stack.min: 7 main <<< stack.pop: 7
Apparently we pushed some values into a stack. After doing so we are pulling them until the stack is empty. On each pass we first get the min value in the stack and then pop the top. The values appear to have been pushed in descending order starting with 7 and ending with 1.
/*
* Test scaffolding.
*/
public static void main(String[] args) throws Exception {
// **** instantiate a stack ****
MyStack stack = new MyStack();
// **** push some values into the stack ****
for (int i = 7; i > 0; i--) {
// for (int i = 0; i < 7; i++) {
stack.push(i);
}
// **** pop all values from the stack ****
while (!stack.isEmpty()) {
System.out.println("main <<< stack.min: " + stack.min());
System.out.println("main <<< stack.pop: " + stack.pop());
System.out.println();
}
}
The first this we do is to instantiate our stack. Once that is done we loop inserting values. I experimented with two loops. One starts pushing 7 followed by the rest of the integers and stopping with 1. That is what we figured out by looking at the output.
Once that is done we loop until the stack is empty. On each pass we fist get the current min and display it, followed by popping the top of the stack.
/*
*
*/
public static class Node {
// **** class members ****
public int val;
public int min;
public Node next;
/*
* Constructor
*/
public Node(int val, int min) {
this.val = val;
this.min = min;
this.next = null;
}
}
The Node class contains three members. Of interest is the one labeled min. The variables are followed by the Node constructor.
// **** top of stack ****
private Node top = null;
// **** min value in stack ****
private int minVal = Integer.MAX_VALUE;
/*
* Constructor
*/
public MyStack() {
this.top = null;
}
/*
* Push the value into the stack.
*/
public void push(int val) {
// **** check and set the min val ****
if (val < minVal) {
minVal = val;
}
// **** allocate a node ****
Node node = new Node(val, minVal);
// **** set the next field in the node ****
node.next = top;
// **** push the node into the stack ****
top = node;
}
/*
* Pop the value from the stack.
*/
public int pop() throws Exception {
// **** check if stack is empty ****
if (top == null)
throw new Exception("pop <<< stack is empty");
// **** point to top node in the stack ****
Node node = top;
// **** update the top of the stack ****
top = top.next;
// **** return the value popped from the stack ****
return node.val;
}
/*
* Min
*/
public int min() throws Exception {
// **** check if stack is empty ****
if (top == null)
throw new Exception("min <<< stack is empty");
// **** return the min value in the stack ****
return top.min;
}
/*
* Check if the stack is empty
*/
public boolean isEmpty() {
return top == null;
}
We start by defining the top of the stack which for starters is set to null to indicate the stack is empty. The minVal is used to keep track of the min value each time a new value is pushed into the stack.
The push, pop, min and isEmpty methods follow. Of interest are the push and min methods.
When we push we first check if the specified value is less than the current min value. If so, we replaced the minVal. We then allocate a nose with the val and minVal values, set the next to the current top and then set the top to the node.
As we continue pushing, the first condition will update the current min and will be placed in the node.
The min method first checks if the stack is not empty. If empty throws an exception. It then returns the min in the top element. This is accomplished in O(1) time.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa