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?
Run through a set of example cases:
HAPPY CASE
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
EDGE CASE
Input: pushed = [0], popped = [0]
Output: true
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: For each value, push it to the stack. Then, pop values from the stack if they are the next values to pop. At the end, we check if we have popped all the values successfully.
1. use an actual stack to verify the input
2. have a pointer index for each array to keep track of our operations
3. if the current val in pushed does not match that of popped, push that val
4. else if they do match, then pop
5. if after popping, the popped val does not match, then this is an incorrect popped arr and return false
6. after going through both the pushed arr with no issues, we should check our stack
7. start popping each val from the stack and compare it to the remaining values of the popped array.
8. if there are no mismatched results, success!
โ ๏ธ Common Mistakes
Implement the code to solve the algorithm.
class Solution(object):
# Using a stack, keep on adding the elements looping the "pushed" list
# Maintain an index var to traverse "popped" list
# When the top element of stack equals the popped[index] value, move down the stack to pop elements
# with same value as popped[index], incrementing index in each iteration
# return True if matches
def validateStackSequences(self, pushed, popped):
j = 0
stack = []
for x in pushed:
stack.append(x)
while stack and j < len(popped) and stack[-1] == popped[j]:
stack.pop()
j += 1
return j == len(popped)
public boolean validateStackSequences(int[] pushed, int[] popped) {
int n = pushed.length;
int i = 0;
Stack myStack = new Stack<>();
// push each int num in pushed arr
for (int x : pushed) {
myStack.push(x);
// if stack has elements
// and we have not iterated thru all popped nums
// and the top of the stack matches the current popped num
while (!myStack.isEmpty() && i < n && myStack.peek() == popped[i]) {
// pop, increment index of popped
myStack.pop();
i++;
}
}
// if i equals n, then we popped successfully all nums in popped arr
// else we could not pop everything
return i == n;
}
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.