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: ["2","1","+","3","*"]
Output: 9
The expression is evaluated as follows: ((2 + 1) * 3) = 9
Input: ["4","13","5","/","+"]
Output: 6
The expression is evaluated as follows: (4 + (13 / 5)) = 6
EDGE CASE
Input: ["2"]
Output: 2
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.
For Array problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use Stack to store numbers and help with the evaluation.
1. Create a Stack which will store the numbers.
2. When you come across an operator, pop the top two elements from the stack.
3. Create a switch case which will act based on the type of the operator.
4. For each switch case, perform their operations on the two variables and push the result into the stack again.
5. At the end of the traversal, the element at the top of the stack is the result.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def evalRPN(self, tokens):
# 1) Create a Stack which will store the numbers.
stack = []
for token in tokens:
if token not in "+-/*":
stack.append(int(token))
continue
# 2) When you come across an operator, pop the top two elements from the stack.
number_2 = stack.pop()
number_1 = stack.pop()
# 3) Create a switch case which will act based on the type of the operator.
# 4) For each switch case, perform their operations on the two variables and push the result into the stack again.
result = 0
if token == "+":
result = number_1 + number_2
elif token == "-":
result = number_1 - number_2
elif token == "*":
result = number_1 * number_2
else:
result = int(number_1 / number_2)
stack.append(result)
# 5) At the end of the traversal, the element at the top of the stack is the result.
return stack.pop()
class Solution {
public int evalRPN(String[] tokens) {
// 1) Create a Stack which will store the numbers.
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (!"+-*/".contains(token)) {
stack.push(Integer.valueOf(token));
continue;
}
// 2) When you come across an operator, pop the top two elements from the stack.
int number2 = stack.pop();
int number1 = stack.pop();
// 3) Create a switch case which will act based on the type of the operator.
// 4) For each switch case, perform their operations on the two variables and push the result into the stack again.
int result = 0;
switch (token) {
case "+":
result = number1 + number2;
break;
case "-":
result = number1 - number2;
break;
case "*":
result = number1 * number2;
break;
case "/":
result = number1 / number2;
break;
}
stack.push(result);
}
// 5) At the end of the traversal, the element at the top of the stack is the result.
return stack.pop();
}
}
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.
Assume N
represents the number of items in the array
O(N)
because we need to traverse all items in the arrayO(N)
because we may need to store all items in the array into a stack