Stack: LIFO and Its Applications
A stack (Last In, First Out) is the go-to structure when you need to process or undo in reverse order: function call stack, expression evaluation, DFS, matching brackets, and “undo” operations. Key insight: whenever you see “the most recent unmatched X” or “process in reverse,” think stack. Python: use a list (append/pop). Java: Deque as stack (ArrayDeque). Do NOT use java.util.Stack — it is synchronized and slow.
Valid Parentheses (LC 20)
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for c in s:
if c in mapping:
top = stack.pop() if stack else '#'
if mapping[c] != top:
return False
else:
stack.append(c)
return not stackEvaluate Reverse Polish Notation (LC 150)
def eval_rpn(tokens: list[str]) -> int:
stack = []
ops = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b) # truncate toward zero
}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]Min Stack (LC 155) — O(1) getMin
class MinStack:
def __init__(self):
self.stack = [] # (value, current_min) pairs
def push(self, val: int) -> None:
current_min = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, current_min))
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]LRU Cache (LC 146) — O(1) get and put
Use a doubly linked list (for O(1) insert and remove) combined with a hashmap (for O(1) lookup). Most-recently-used at the tail; least-recently-used at the head. On get: move to tail. On put: insert at tail; if over capacity, remove head.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = OrderedDict() # maintains insertion order
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # remove LRU (first item)Queue: BFS and Design
# Implement Queue using Two Stacks (LC 232)
class MyQueue:
def __init__(self):
self.inbox = [] # for push
self.outbox = [] # for pop/peek
def push(self, x: int) -> None:
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self) -> int:
self._transfer()
return self.outbox.pop()
def peek(self) -> int:
self._transfer()
return self.outbox[-1]
def empty(self) -> bool:
return not self.inbox and not self.outboxAmortized O(1) per operation: each element is pushed to inbox once, transferred to outbox once, and popped from outbox once — 3 operations total. The transfer only happens when outbox is empty.
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Coinbase Interview Prep