Stack and Queue Interview Problems: Patterns That Actually Get You Hired

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class BracketValidator {

    // Map every closing bracket to its expected opening bracket
    private static final Map<Character, Character> MATCHING_OPEN = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

    public static boolean isValid(String expression) {
        // Deque used as a stack — ArrayDeque is faster than Stack class in Java
        Deque<Character> openBracketStack = new ArrayDeque<>();

        for (char token : expression.toCharArray()) {
            if (MATCHING_OPEN.containsValue(token)) {
                // It's an opening bracket — push it onto the stack
                openBracketStack.push(token);
            } else if (MATCHING_OPEN.containsKey(token)) {
                // It's a closing bracket — check if it matches the most recent open
                if (openBracketStack.isEmpty()) {
                    // Nothing to match against — invalid
                    return false;
                }
                char mostRecentOpen = openBracketStack.pop();
                if (mostRecentOpen != MATCHING_OPEN.get(token)) {
                    // Mismatch — e.g. '[)' is not valid
                    return false;
                }
            }
            // Non-bracket characters (digits, operators) are ignored
        }

        // If the stack isn't empty, we have unclosed brackets
        return openBracketStack.isEmpty();
    }

    public static void main(String[] args) {
        String[] testCases = {
            "({[]})",       // valid — fully nested
            "([)]",         // invalid — wrong closing order
            "{[}",          // invalid — unclosed bracket
            "",             // edge case — empty string is valid
            "((({{{[[[",    // invalid — all opens, no closes
            "2*(3+[4-1])"   // valid — mixed with non-bracket chars
        };

        for (String test : testCases) {
            System.out.printf("%-20s => %s%n", 
                test.isEmpty() ? "(empty)" : test, 
                isValid(test) ? "VALID" : "INVALID"
            );
        }
    }
}

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class DailyTemperatures {

    /**
     * For each day, returns the number of days until a warmer temperature.
     * Returns 0 if no warmer day exists after it.
     *
     * Strategy: monotonic decreasing stack of indices.
     * We keep indices of days we haven't found a warmer day for yet.
     * When we find a warmer day, we resolve all pending cooler days.
     */
    public static int[] daysUntilWarmer(int[] temperatures) {
        int[] waitDays = new int[temperatures.length]; // default 0 = no warmer day found
        // Stack holds indices of days still waiting for a warmer day
        Deque<Integer> pendingDayIndices = new ArrayDeque<>();

        for (int today = 0; today < temperatures.length; today++) {
            // While today is warmer than the day at the top of the stack...
            while (!pendingDayIndices.isEmpty() &&
                   temperatures[today] > temperatures[pendingDayIndices.peek()]) {

                int coldDayIndex = pendingDayIndices.pop();
                // The wait is the difference in indices
                waitDays[coldDayIndex] = today - coldDayIndex;
            }
            // Push today's index — we don't have a warmer day for it yet
            pendingDayIndices.push(today);
        }
        // Any index still in the stack has no future warmer day — stays 0
        return waitDays;
    }

    public static void main(String[] args) {
        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] result = daysUntilWarmer(temperatures);

        System.out.println("Temperatures: " + Arrays.toString(temperatures));
        System.out.println("Days to wait: " + Arrays.toString(result));
        System.out.println();

        // Walk through to make it human-readable
        for (int i = 0; i < temperatures.length; i++) {
            if (result[i] == 0) {
                System.out.printf("Day %d (%d°): No warmer day ahead%n", i, temperatures[i]);
            } else {
                System.out.printf("Day %d (%d°): Wait %d day(s) for %d°%n",
                    i, temperatures[i], result[i], temperatures[i + result[i]]);
            }
        }
    }
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelOrder {

    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * Returns nodes grouped by their level in the tree.
     * Level 0 = root, Level 1 = root's children, etc.
     *
     * This is one of the most common tree interview problems — 
     * and the queue is what makes it work.
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> allLevels = new ArrayList<>();
        if (root == null) return allLevels;

        Queue<TreeNode> processingQueue = new ArrayDeque<>();
        processingQueue.offer(root); // Start with just the root

        while (!processingQueue.isEmpty()) {
            // KEY INSIGHT: capture the queue size BEFORE processing.
            // This tells us exactly how many nodes belong to the current level.
            int nodesOnThisLevel = processingQueue.size();
            List<Integer> currentLevelValues = new ArrayList<>();

            for (int i = 0; i < nodesOnThisLevel; i++) {
                TreeNode currentNode = processingQueue.poll();
                currentLevelValues.add(currentNode.value);

                // Enqueue children for the NEXT level
                if (currentNode.left != null) {
                    processingQueue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    processingQueue.offer(currentNode.right);
                }
            }
            allLevels.add(currentLevelValues);
        }
        return allLevels;
    }

    public static void main(String[] args) {
        /*
         * Building this tree:
         *         3
         *        / \
         *       9   20
         *          /  \
         *         15   7
         */
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> levels = levelOrder(root);

        System.out.println("Level-order traversal:");
        for (int level = 0; level < levels.size(); level++) {
            System.out.printf("Level %d: %s%n", level, levels.get(level));
        }

        System.out.println("\nFull result: " + levels);
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Implements a FIFO Queue using only two LIFO Stacks.
 * 
 * Core idea: reversing a stack twice restores original order,
 * but reversing once gives you FIFO from LIFO.
 */
public class QueueUsingTwoStacks {

    // New elements always land here first
    private final Deque<Integer> inboxStack = new ArrayDeque<>();
    // Elements come here (reversed) when we need to dequeue
    private final Deque<Integer> outboxStack = new ArrayDeque<>();

    /** O(1) — always push to inbox */
    public void enqueue(int value) {
        inboxStack.push(value);
    }

    /**
     * Amortized O(1) — outbox refill only happens when outbox is empty.
     * Each element moves from inbox to outbox at most ONCE total.
     */
    public int dequeue() {
        if (outboxStack.isEmpty()) {
            refillOutbox();
        }
        if (outboxStack.isEmpty()) {
            throw new RuntimeException("Queue is empty — cannot dequeue");
        }
        return outboxStack.pop();
    }

    /** O(1) amortized — same lazy refill logic */
    public int peek() {
        if (outboxStack.isEmpty()) {
            refillOutbox();
        }
        if (outboxStack.isEmpty()) {
            throw new RuntimeException("Queue is empty — cannot peek");
        }
        return outboxStack.peek();
    }

    public boolean isEmpty() {
        return inboxStack.isEmpty() && outboxStack.isEmpty();
    }

    /**
     * Pour everything from inbox into outbox.
     * Popping from inbox and pushing to outbox reverses the order,
     * converting LIFO (stack) order into FIFO (queue) order.
     */
    private void refillOutbox() {
        while (!inboxStack.isEmpty()) {
            outboxStack.push(inboxStack.pop());
        }
    }

    public static void main(String[] args) {
        QueueUsingTwoStacks queue = new QueueUsingTwoStacks();

        // Enqueue three items
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println("Peek (should be 10): " + queue.peek());
        System.out.println("Dequeue (should be 10): " + queue.dequeue());
        System.out.println("Dequeue (should be 20): " + queue.dequeue());

        // Enqueue more after partial drain — tests the mixed state
        queue.enqueue(40);
        queue.enqueue(50);

        System.out.println("Dequeue (should be 30): " + queue.dequeue());
        System.out.println("Dequeue (should be 40): " + queue.dequeue());
        System.out.println("Dequeue (should be 50): " + queue.dequeue());
        System.out.println("Is empty (should be true): " + queue.isEmpty());
    }
}