Stacks and Queues Questions

Implementation and usage of stack and queue data structures. Problems involving balanced parentheses, expression evaluation, queue operations, or sliding window maximums. Understanding when to use each structure and their time/space trade-offs.

MediumTechnical

68 practiced

Implement an LRUCache class in Java with a constructor taking capacity and methods get(key) and put(key,value) with O(1) expected time. Do not use LinkedHashMap built-in LRU; implement using a hashmap plus a doubly linked list. Provide code skeleton and explain eviction policy and complexity.

Sample Answer

Approach: Use a HashMap<Key, Node> for O(1) access and a custom doubly-linked list to track recentness. Head = most-recent, tail = least-recent. On get/put we move accessed node to head. When capacity exceeded, remove tail node and its map entry.

java

public class LRUCache {
    private class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v){ key=k; val=v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail; // dummy sentinels

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        remove(n);
        insertToHead(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {
            n.val = value;
            remove(n);
            insertToHead(n);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node newNode = new Node(key, value);
        insertToHead(newNode);
        map.put(key, newNode);
    }

    // unlink node from list
    private void remove(Node n){
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    // insert right after head
    private void insertToHead(Node n){
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}

Eviction policy: Least Recently Used — the tail.prev node is evicted when capacity exceeded. Complexity: get and put are O(1) time (HashMap lookup + constant list ops). Space: O(capacity) for map + nodes. Edge cases: capacity <= 0 (should be handled by caller or validate in constructor), updating existing key, duplicates, and concurrency (not thread-safe — synchronize externally or use concurrent structures if needed).

MediumTechnical

105 practiced

Implement shortest_path_grid(grid, start, target) in Python using BFS with a queue. The grid is a 2D matrix where 0 = free cell and 1 = obstacle. Return the shortest path length or -1 if unreachable using 4-directional moves. Include boundary checks, visited handling, and sample inputs.

Sample Answer

To find the shortest path on a 2D grid with 4-directional moves, use BFS from start; BFS guarantees shortest path length in an unweighted grid. Track visited cells and boundary/obstacle checks. Return distance when target is reached or -1 if queue exhausts.

python

from collections import deque

def shortest_path_grid(grid, start, target):
    """
    grid: List[List[int]] where 0=free, 1=obstacle
    start, target: (r, c) tuples
    Returns shortest path length (number of steps) or -1 if unreachable
    """
    if not grid or not grid[0]:
        return -1

    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    tr, tc = target

    # Validate start/target
    def valid_cell(r, c):
        return 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0

    if not valid_cell(sr, sc) or not valid_cell(tr, tc):
        return -1
    if (sr, sc) == (tr, tc):
        return 0

    q = deque()
    q.append((sr, sc, 0))  # row, col, distance
    visited = [[False]*cols for _ in range(rows)]
    visited[sr][sc] = True

    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    while q:
        r, c, d = q.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] == 0:
                if (nr, nc) == (tr, tc):
                    return d + 1
                visited[nr][nc] = True
                q.append((nr, nc, d + 1))
    return -1

Key points:- BFS ensures shortest path in O(rows*cols) time.- Space O(rows*cols) for visited and queue.- Handles boundaries, obstacles, start==target.

Sample calls:

python

g = [
 [0,0,1],
 [0,0,0],
 [1,0,0]
]
print(shortest_path_grid(g, (0,0), (2,2)))  # Output: 4
print(shortest_path_grid(g, (0,0), (0,2)))  # Output: -1

HardTechnical

71 practiced

Design a full-featured expression evaluator that supports variables, function calls, operator precedence, and safe evaluation under a constrained call stack size. Describe parsing strategy (tokenizer, shunting-yard or Pratt parser), AST construction, and evaluation model that avoids deep recursion if stack space is limited.

Sample Answer

High-level approach- Tokenize input into identifiers, numbers, strings, parens, commas, and operators (with precedence/associativity).- Use the shunting-yard algorithm to produce Reverse Polish Notation (RPN) or a Pratt parser to directly build an AST. I recommend shunting‑yard→RPN for easier iterative evaluation and explicit call/arg handling.- Evaluate RPN with your own evaluation stack (heap-allocated), avoiding native recursion. For function calls, evaluate args first, then push a Call frame to an explicit VM stack; implement a trampoline or small bytecode for complex functions to bound native call depth.

Tokenizer + Shunting‑Yard (summary)- Tokenizer yields (type, value, pos). Handle unary vs binary operators by context.- Shunting‑yard: output queue + operator stack. On identifier followed by '(' treat as function token; commas pop until '('.

AST vs RPN- RPN is simpler for iterative execution; it flattens expression so you don't need recursive AST traversal. If you need AST (for optimizations), build nodes but evaluate them by compiling to RPN/bytecode.

Evaluation model (no deep recursion)- Use an explicit evaluation stack (list) and an explicit call stack (frames) stored on the heap.- Each frame: instruction pointer into RPN/bytecode, locals map, return slot.- Main loop: while frames non-empty: - Fetch next opcode/token; for literal/var/operator apply to evaluation stack. - For function call: create new frame with function bytecode/RPN and evaluated args in locals; push frame; continue loop. - For return: pop frame, push return value onto caller eval stack.- This turns recursion into heap-managed frames and avoids native recursion limits.- For very deep expression trees (e.g., left-deep nested operators), RPN evaluation uses O(depth) heap memory rather than native stack.

Example: evaluate using RPN (Python-like)

python

# tokens already converted to RPN list e.g. [3, 4, '+', 'x', '*', ('call','f',2)]
def eval_rpn(rpn, env, functions):
    eval_stack = []
    frames = [Frame(rpn, env)]
    while frames:
        frame = frames[-1]
        if frame.ip >= len(frame.code):
            # implicit return top of eval_stack
            retval = frame.eval_stack.pop() if frame.eval_stack else None
            frames.pop()
            if frames:
                frames[-1].eval_stack.append(retval)
            continue
        instr = frame.code[frame.ip]; frame.ip += 1
        if isinstance(instr, (int,float,str)):
            frame.eval_stack.append(instr)
        elif instr == 'var':
            frame.eval_stack.append(frame.locals[instr.name])
        elif instr in ('+','-','*','/'):
            b = frame.eval_stack.pop(); a = frame.eval_stack.pop()
            frame.eval_stack.append(apply_op(instr,a,b))
        elif isinstance(instr, tuple) and instr[0]=='call':
            _, fname, argc = instr
            args = [frame.eval_stack.pop() for _ in range(argc)][::-1]
            fn = functions[fname]
            frames.append(Frame(fn.code, dict(zip(fn.params, args))))

Trade-offs and extensions- RPN + VM: simple, iterative, easy to bound memory. Slightly less flexible for some AST optimizations.- Pratt parser: better for complex precedence/extensibility; still compile to bytecode/RPN to evaluate iteratively.- For safety: enforce max heap frames, timeout, sandboxed function table (no arbitrary host calls), and limit recursion by rejecting code that would create >N frames.

Complexity and robustness- Parsing: O(n) time, O(n) space.- Evaluation: O(n) time, O(d) space where d is expression depth (heap frames + eval stack).- Edge cases: unary operators, short-circuit (compile &&/|| to control-flow bytecodes), variadic functions, error reporting with source positions.

This design gives full features (variables, calls, precedence) while ensuring evaluation uses heap-managed stacks and a trampoline-like VM loop to avoid native stack overflow.

MediumTechnical

62 practiced

Design and implement a MinStack in Python that supports push(x), pop(), top(), and getMin() each in O(1) time. Provide two approaches: auxiliary stack of minimums and value encoding trick. Explain space complexity and handling of duplicates.

Sample Answer

To solve this, we need O(1) push/pop/top/getMin. Two common approaches:

Approach 1 — Auxiliary stack of minimums1. Maintain main stack for values and a min_stack that stores current minima. On push(x) push x to main; push x to min_stack if min_stack is empty or x <= min_stack[-1]. On pop(), pop main; if popped == min_stack[-1], pop min_stack. top() is main[-1]. getMin() is min_stack[-1].

python

class MinStackAux:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if not self.stack:
            raise IndexError("pop from empty stack")
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        if not self.stack:
            raise IndexError("top from empty stack")
        return self.stack[-1]

    def getMin(self) -> int:
        if not self.min_stack:
            raise IndexError("min from empty stack")
        return self.min_stack[-1]

Key points:- Time: O(1) each operation.- Space: O(n) worst-case; min_stack may hold up to n elements.- Duplicates: Using <= on push and equality on pop preserves duplicates (multiple equal minima stored).

Approach 2 — Value encoding trick (store deltas)2. Store only encoded values so min can be tracked in one stack and one variable current_min. On push(x):- If stack empty: push x, set current_min = x.- Else if x >= current_min: push x.- Else (x < current_min): push 2*x - current_min (an encoded value) and set current_min = x.On pop(): if popped >= current_min -> normal pop; else popped is encoded, recover previous_min = 2*current_min - popped, set current_min = previous_min.top(): if top >= current_min return top, else return current_min.

python

class MinStackEncoded:
    def __init__(self):
        self.stack = []
        self.min_val = None

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(x)
            self.min_val = x
        elif x >= self.min_val:
            self.stack.append(x)
        else:
            # store encoded value and update min
            self.stack.append(2*x - self.min_val)
            self.min_val = x

    def pop(self) -> None:
        if not self.stack:
            raise IndexError("pop from empty stack")
        top = self.stack.pop()
        if top < self.min_val:
            # encoded: recover previous min
            self.min_val = 2*self.min_val - top
        if not self.stack:
            # stack empty -> reset min_val
            self.min_val = None

    def top(self) -> int:
        if not self.stack:
            raise IndexError("top from empty stack")
        top = self.stack[-1]
        return top if top >= self.min_val else self.min_val

    def getMin(self) -> int:
        if self.min_val is None:
            raise IndexError("min from empty stack")
        return self.min_val

Key points and trade-offs:- Time: O(1) each.- Space: O(n) for encoded approach but only one stack used; auxiliary approach uses up to 2n storage worst-case.- Duplicates: Encoded trick handles duplicates implicitly (values >= min are stored normally). When pushing a new smaller value equal to current_min, encoding uses the <= or < logic—use strict < to avoid unnecessary encoding when equal; both methods should carefully handle equality to preserve correct pop behavior.- Edge cases: empty operations should raise errors; ensure resetting min when stack becomes empty.

Which to choose:- Auxiliary stack: simpler, clearer, easier to maintain and reason about.- Encoded trick: saves memory in some cases (only one stack), but is trickier and more error-prone; use only when memory constant factors matter.

HardTechnical

70 practiced

Given a histogram as an array of heights, implement largest_rectangle_area(heights) in Python using a stack to compute the largest rectangle area in O(n) time. Provide explanation of the monotonic stack strategy, sentinel usage, and proof sketch for correctness.

Sample Answer

To solve this in O(n) we use a monotonic increasing stack of indices. The stack stores bar indices with strictly increasing heights. When a lower height appears, we pop taller bars and compute areas where the popped bar is the smallest bar spanning between the previous stack top and current index. Adding sentinel zeros at both ends simplifies boundaries.

python

def largest_rectangle_area(heights):
    """
    Monotonic stack solution with sentinels.
    Time: O(n), Space: O(n)
    """
    # Add sentinels to avoid empty-stack checks
    h = [0] + heights + [0]
    stack = [0]  # store indices, h[stack[-1]] is increasing
    max_area = 0

    for i in range(1, len(h)):
        # Maintain increasing heights in stack
        while h[i] < h[stack[-1]]:
            height = h[stack.pop()]
            left = stack[-1]  # index of previous smaller height
            width = i - left - 1
            area = height * width
            if area > max_area:
                max_area = area
        stack.append(i)

    return max_area

Key ideas:- Monotonic increasing stack ensures when popping index j, its maximal span is (prev_smaller_index+1 .. next_smaller_index-1). Width = right_index - left_index - 1.- Sentinels (leading and trailing 0) guarantee every bar will be popped and simplify edge checks.

Proof sketch (correctness):- Invariant: stack holds indices of strictly increasing heights; their spans to the right are not yet determined.- When encountering h[i] < h[top], any index on top cannot extend to i, so popping computes exact maximal width because left boundary is the previous smaller index (now stack[-1]) and right boundary is i (first smaller to right). Each bar is pushed/popped once → O(n).

Edge cases:- Empty input -> returns 0- All equal heights -> handled correctly- Large input -> O(n) time, O(n) extra for stack/sentinels.

Unlock Full Question Bank

Get access to hundreds of Stacks and Queues interview questions and detailed answers.

Join thousands of developers preparing for their dream job.