Technical Interviews

• Understand the problem being asked
• Don’t forget to handle edge cases
• Expressing your answer is just as important as understanding the problem, and solving it!

## Problems with Stacks #

### Checking parenthesis #

Examples:

Input: ()
Output: true

Input: ()[]{}
Output: true

Input: ([)]
Output: false

Input: {[]}
Output: true

Input : {[]{()}}
Output : true

Input : [{}{}(]
Output :false


The logic here is to push a new item on to a stack when we notice an input with an opener, and pop when there is a closer.

# Python3 code to Check for balanced parentheses in an expression
open_list = ["[","{","("]
close_list = ["]","}",")"]

# Function to check parentheses
def check(myStr):
stack = []
for i in myStr:
if i in open_list:
stack.append(i)
elif i in close_list:
pos = close_list.index(i)
if ((len(stack) > 0) and
(open_list[pos] == stack[len(stack)-1])):
stack.pop()
else:
return "Unbalanced"
if len(stack) == 0:
return "Balanced"
else:
return "Unbalanced"


Sample code

string = "{[]{()}}"
print(string,"-", check(string))

string = "[{}{})(]"
print(string,"-", check(string))

string = "((()"
print(string,"-",check(string))


### Evaluate Postfix Notation #

Given a valid expression in reverse polish notation, evaluate it and return the result.

Input: ["2", "1", "+", "3", "*"]
Output: 9, because ((2 + 1) * 3) = 9

Input: ["4", "10", "5", "/", "+"]
Output: 6, because (4 + (10 / 5)) = 6


#### The algorithm #

• Create an empty stack and scan postfix expression from left to right
• If element is an operand, push it into the stack
• If the element is an operator 📦:
• pop twice to get A and B (calculate B 📦 A)
• push result back to the stack
• When expression is ended, the value in stack is the final answer

#### Example #

\[ $$3 1 + 9 *$$ \vspace{1in} 36

\begin{tikzpicture} \matrix[matrix of nodes, %draw, nodes in empty cells, nodes={minimum size=10mm}]{ % column sep=-\pgflinewidth Postfix char read in & Operands (stack) & Actions \\\
3 & 3 & \\\
1 & 3 1 & \\\
$+$ & 4 & Pop the top 2 operands and push the result \\\
9 & 4 9 & \\\
$*$ & 36 & Pop the top 2 operands and push the result \\\
}; The expression evalutes to 36. \end{tikzpicture}

\fi ]