Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Input
["MinStack","push","push","push","top","pop","getMin","pop","getMin","pop","push","top","getMin","push","top","getMin","pop","getMin"]
[[],[2147483646],[2147483646],[2147483647],[],[],[],[],[],[],[2147483647],[],[],[-2147483648],[],[],[],[]]
Output
[null,null,null,null,2147483647,null,2147483646,null,2147483646,null,null,2147483647,2147483647,null,-2147483648,-2147483648,null,2147483647]
HARDER CASE
Input:
["MinStack","push","push","push","push","getMin","pop","top","getMin"]
[[],[1],[-1],[2],[-8],[],[],[],[]]
Output:
[null,null,null,null,null,-8,null,2,-1]
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: When pushing a new value to the stack, check if the current minimum has to be updated. Push both the new value and the current minimum to the same (or parallel) stack(s). When popping a value from the stack, we can also pop a record of the current minimum at that level, and the new top of the stack(s) will have a record of the previous minimum based on all the values below it.
MinStack(): set up a stack that can store two numbers together or two stacks that can each store a number in parallel
push(value): Append value and current minimum to stack(s)
pop(): remove value and current minimum from the top of stack(s)
top(): return value from the top of stack
getMin(): return current minimum from the top of stack
โ ๏ธ Common Mistakes
Implement the code to solve the algorithm.
class MinStack:
def __init__(self):
self.stack = [ (None, float('inf')) ]
def push(self, val: int) -> None:
self.stack.append( (val, min(val, self.getMin())) )
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
class MinStack {
Stack<Integer> mins = new Stack<Integer>();
Stack<Integer> stack = new Stack<Integer>();
public void push(int val) {
stack.push(val);
if (mins.empty() || val < mins.peek()) {
mins.push(val);
} else{
mins.push(mins.peek());
}
}
public void pop() {
stack.pop();
mins.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return mins.peek();
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Let n be the total number of operations performed.