Combined Patterns

The most impressive interview problems combine linked lists and stacks with hash maps. These problems test your ability to design data structures with multiple O(1) operations — a skill that separates senior candidates from junior ones.

Problem 1: LRU Cache (LC 146)

Problem: Design a data structure that supports get(key) and put(key, value) in O(1) time. When the cache reaches capacity, evict the least recently used item.

# LRU Cache with capacity = 3
#
# Architecture: HashMap + Doubly Linked List
#
#   HashMap: key -> DListNode
#
#   Doubly Linked List (most recent at tail):
#     HEAD <-> [A] <-> [B] <-> [C] <-> TAIL
#     (LRU)                    (MRU)
#
# Operations:
#   get(key):  Find node via map, move to tail (MRU), return value
#   put(key):  If exists: update + move to tail
#              If new + full: evict HEAD.next (LRU), add at tail
#              If new + space: add at tail
#
# Example with capacity=2:
#   put(1,1): list=[1]           map={1:node1}
#   put(2,2): list=[1,2]         map={1:node1, 2:node2}
#   get(1):   list=[2,1]         return 1 (move 1 to MRU)
#   put(3,3): evict 2 (LRU)     list=[1,3]  map={1:node1, 3:node3}
#   get(2):   return -1 (evicted)

class DListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    """LRU Cache using HashMap + Doubly Linked List.

    - HashMap gives O(1) lookup by key
    - Doubly linked list gives O(1) insertion/removal
    - Head.next = least recently used
    - Tail.prev = most recently used

    get: O(1)  |  put: O(1)  |  Space: O(capacity)
    """
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> DListNode

        # Sentinel nodes (avoid null checks)
        self.head = DListNode()
        self.tail = DListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Remove a node from the doubly linked list."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):
        """Add a node right before the tail (most recent)."""
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        if key not in self.cache:
            return -1

        node = self.cache[key]
        # Move to tail (mark as most recently used)
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key, value):
        if key in self.cache:
            # Update existing node
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_tail(node)
        else:
            if len(self.cache) >= self.capacity:
                # Evict LRU (node right after head)
                lru = self.head.next
                self._remove(lru)
                del self.cache[lru.key]

            # Add new node
            node = DListNode(key, value)
            self.cache[key] = node
            self._add_to_tail(node)

Problem 2: Browser History (LC 1472)

Problem: Implement a browser history with visit, back, and forward operations.

# Browser History using Doubly Linked List
#
# visit("a"):  [a]            curr = a
# visit("b"):  [a] <-> [b]    curr = b
# visit("c"):  [a] <-> [b] <-> [c]    curr = c
# back(1):     curr = b       (move left 1 step)
# back(1):     curr = a       (move left 1 step)
# forward(1):  curr = b       (move right 1 step)
# visit("d"):  [a] <-> [b] <-> [d]    curr = d
#              (forward history after b is cleared!)

class BrowserHistory:
    """Browser history with O(1) visit, O(steps) back/forward.

    Uses a doubly linked list where:
    - visit: append after current, remove forward history
    - back: move current pointer left
    - forward: move current pointer right

    visit: O(1)  |  back/forward: O(min(steps, history length))
    Space: O(n) total pages visited
    """
    def __init__(self, homepage):
        self.curr = DListNode(val=homepage)

    def visit(self, url):
        # Create new node after current
        node = DListNode(val=url)
        self.curr.next = node
        node.prev = self.curr
        # Forward history is discarded (node.next = None)
        self.curr = node

    def back(self, steps):
        while steps > 0 and self.curr.prev:
            self.curr = self.curr.prev
            steps -= 1
        return self.curr.val

    def forward(self, steps):
        while steps > 0 and self.curr.next:
            self.curr = self.curr.next
            steps -= 1
        return self.curr.val

Problem 3: Undo/Redo System

Problem: Design a text editor that supports typing characters, undo (remove last action), and redo (restore last undo). This is a classic system design + data structure problem.

# Undo/Redo using Two Stacks
#
# undo_stack: stores actions (LIFO for undoing)
# redo_stack: stores undone actions (LIFO for redoing)
#
# type("H"):  text="H"    undo=[H]         redo=[]
# type("i"):  text="Hi"   undo=[H, i]      redo=[]
# type("!"):  text="Hi!"  undo=[H, i, !]   redo=[]
# undo():     text="Hi"   undo=[H, i]      redo=[!]
# undo():     text="H"    undo=[H]         redo=[!, i]
# redo():     text="Hi"   undo=[H, i]      redo=[!]
# type("?"):  text="Hi?"  undo=[H, i, ?]   redo=[]
#                          (redo cleared on new action!)

class TextEditor:
    """Text editor with undo/redo using two stacks.

    Invariants:
    - undo_stack: history of all actions
    - redo_stack: undone actions available for redo
    - Any new action clears the redo stack

    All operations: O(1) time
    Space: O(n) total operations
    """
    def __init__(self):
        self.text = []
        self.undo_stack = []
        self.redo_stack = []

    def type_char(self, char):
        """Type a character. Clears redo history."""
        self.text.append(char)
        self.undo_stack.append(('add', char))
        self.redo_stack.clear()  # new action invalidates redo

    def delete(self):
        """Delete last character. Clears redo history."""
        if self.text:
            char = self.text.pop()
            self.undo_stack.append(('delete', char))
            self.redo_stack.clear()

    def undo(self):
        """Undo the last action."""
        if not self.undo_stack:
            return

        action, char = self.undo_stack.pop()

        if action == 'add':
            self.text.pop()          # reverse of add = remove
        elif action == 'delete':
            self.text.append(char)   # reverse of delete = add

        self.redo_stack.append((action, char))

    def redo(self):
        """Redo the last undone action."""
        if not self.redo_stack:
            return

        action, char = self.redo_stack.pop()

        if action == 'add':
            self.text.append(char)   # redo add
        elif action == 'delete':
            self.text.pop()          # redo delete

        self.undo_stack.append((action, char))

    def get_text(self):
        return ''.join(self.text)

Problem 4: Basic Calculator (LC 224)

Problem: Implement a basic calculator to evaluate a string expression with +, -, (, and ).

# Input: "(1+(4+5+2)-3)+(6+8)"
# Output: 23
#
# Strategy: Use a stack to handle parentheses.
# When we see '(', save current result and sign on stack.
# When we see ')', pop and combine.
#
# Trace for "1 + (2 - (3 + 4))":
#   '1':  num=1
#   '+':  result=1, sign=+1
#   '(':  push (result=1, sign=+1), reset result=0, sign=+1
#   '2':  num=2
#   '-':  result=2, sign=-1
#   '(':  push (result=2, sign=-1), reset result=0, sign=+1
#   '3':  num=3
#   '+':  result=3, sign=+1
#   '4':  num=4, result=3+4=7
#   ')':  pop (prev_result=2, prev_sign=-1)
#         result = 2 + (-1)*7 = -5
#   ')':  pop (prev_result=1, prev_sign=+1)
#         result = 1 + (+1)*(-5) = -4
#   Answer: -4

def calculate(s):
    """Basic calculator with + - ( ) using a stack.

    Process character by character:
    - Digits: build multi-digit numbers
    - +/-: apply previous number, update sign
    - (: save state (result, sign) to stack
    - ): pop state and combine

    Time:  O(n) - single pass through string
    Space: O(n) - stack depth for nested parentheses
    """
    stack = []
    result = 0
    num = 0
    sign = 1  # +1 or -1

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)

        elif char == '+':
            result += sign * num
            num = 0
            sign = 1

        elif char == '-':
            result += sign * num
            num = 0
            sign = -1

        elif char == '(':
            # Save current state
            stack.append(result)
            stack.append(sign)
            # Reset for sub-expression
            result = 0
            sign = 1

        elif char == ')':
            result += sign * num
            num = 0
            # Pop sign and previous result
            result *= stack.pop()   # sign before '('
            result += stack.pop()   # result before '('

    # Don't forget the last number
    result += sign * num
    return result

Complexity Summary