Data Structures Interview Questions and Answers

Answer

Big O is an upper bound, Omega is a lower bound and Theta is a tight bound that sandwiches the function from both sides. Formally f(n) is O(g(n)) if there exist constants c and n0 such that f(n) <= c*g(n) for all n >= n0. So an algorithm that is Theta(n log n) is also correctly described as O(n^2), because O is only a ceiling, and this is why interviewers say Big O statements are technically loose.

In practice the industry uses O to mean the tight worst case, and you should say the tight bound out loud: linear search is O(n) worst case, Omega(1) best case, and there is no single Theta because best and worst differ. Deriving a nested loop is a counting exercise, not a pattern match. If the inner loop runs a fixed n times for every outer iteration you get n*n, which is O(n^2).

If the inner loop starts at i you get n + (n-1) + ... + 1 = n(n+1)/2, still O(n^2) after dropping constants. If the inner variable multiplies by 2 each step the inner loop runs log n times, giving O(n log n). Space complexity is counted separately as auxiliary space: the extra memory you allocate beyond the input, and recursion counts because every frame sits on the call stack, so recursive binary search is O(log n) space while the iterative version is O(1). The follow up is almost always about the difference between average and worst case, so be ready to explain why quicksort is O(n log n) expected but O(n^2) worst case.

// O(n^2): inner loop runs n, n-1, ..., 1 times = n(n+1)/2
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        sum += a[j];
    }
}

// O(n log n): inner counter doubles each step
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        work();
    }
}

// Time O(log n), auxiliary space O(1)
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Answer

A Java ArrayList or a Python list is a contiguous array behind a size counter. Appending is a single write until the backing array is full, at which point the structure allocates a larger array, copies every existing element across and then writes. That copy is O(n), so the worst case cost of a single add is genuinely O(n).

Amortised analysis asks a different question: what is the average cost per operation over a long sequence, guaranteed and not probabilistic. The proof is the geometric series. If capacity doubles, then over n appends the resizes happen at capacities 1, 2, 4, 8 and so on up to n, and the total copy work is 1 + 2 + 4 + ... + n which is less than 2n.

Add the n cheap writes and total work for n appends is under 3n, so the amortised cost per append is O(1). The growth factor is what makes this work. If the array grew by a constant 10 slots instead of doubling, resizes would happen n/10 times and copy work would be 10 + 20 + 30 + ... which is Theta(n^2) total, meaning Theta(n) amortised per append.

Java grows by roughly 1.5x, Python by about 1.125x plus a constant, both geometric, both amortised O(1). The practical consequence, and the reason interviewers ask, is latency: if you are appending inside a request handler, one unlucky call pays the full copy. When you know the final size, pre size the structure with new ArrayList<>(expectedSize) so no resize ever happens. Expect a follow up on amortised versus average case: amortised is a worst case guarantee over a sequence, average case is an expectation over random inputs.

// Doubling: total copy cost over n appends
// 1 + 2 + 4 + ... + n < 2n  =>  O(1) amortised per add
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) list.add(i);   // O(n) total

// Constant growth would be O(n^2) total:
// 10 + 20 + 30 + ... + n = Theta(n^2)

// Avoid the resize entirely when size is known
List<Integer> sized = new ArrayList<>(n);  // no copy ever

// Worst case for ONE call is still O(n)
// p99 latency spikes come from exactly this copy

Answer

Every recursive call pushes a stack frame holding the return address, the parameters and the local variables. The JVM default thread stack is around 512KB to 1MB, which in practice means roughly 10,000 to 20,000 frames of a simple method before a StackOverflowError, and CPython caps recursion at 1000 by default with a RecursionError. So recursion depth, not the total number of calls, is what kills you.

A recursive traversal of a balanced tree with a million nodes is fine because depth is about 20, but the same traversal on a degenerate tree that is really a linked list of a million nodes blows the stack. That is the exact scenario interviewers construct: they hand you a skewed tree or a linked list of 10^5 nodes and ask whether your recursive solution survives. Convert to iteration when the recursion depth is O(n) on the input size, when the recursion is a simple tail call (Java and Python do not optimise tail calls, so you get no free ride), or when you need to bound memory tightly.

The mechanical conversion is to keep an explicit stack, which is exactly what iterative inorder traversal and iterative DFS do, and it moves the memory from the call stack to the heap where you have far more room. Keep recursion when it maps to the problem shape and depth is logarithmic, because divide and conquer on trees and balanced structures is dramatically clearer recursive. The follow up is usually memoisation: naive recursive Fibonacci is O(2^n) because of repeated subproblems, and adding a cache makes it O(n) time and O(n) space, which is the bridge into dynamic programming.

// Recursive: O(n) stack depth on a skewed tree, can overflow
int sumRec(Node node) {
    if (node == null) return 0;
    return node.val + sumRec(node.left) + sumRec(node.right);
}

// Iterative with an explicit stack: heap memory, no overflow
int sumIter(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    int sum = 0;
    while (!stack.isEmpty()) {
        Node n = stack.pop();
        sum += n.val;
        if (n.right != null) stack.push(n.right);
        if (n.left != null) stack.push(n.left);
    }
    return sum;   // O(n) time, O(h) heap space
}

Answer

There is a five step protocol that Indian product company interviewers are explicitly scoring, and following it visibly is worth more than arriving at the optimal solution silently. Step one, clarify. Restate the problem in your own words and ask about constraints: what is the size of n, are values negative, can the array be empty, are duplicates allowed, is the input sorted, is it ASCII or Unicode.

Constraints are the biggest hint available: n up to 10^5 rules out O(n^2), n up to 20 usually means bitmask or exponential search is intended. Step two, state a brute force with its complexity, out loud, before writing anything. Saying "the obvious approach is nested loops, O(n^2) time and O(1) space, let me see if I can do better" proves you understand the problem and buys you thinking time.

Step three, optimise by naming the technique and the reason: a hashmap to trade space for lookup, two pointers because the array is sorted, a sliding window because we want a contiguous range, a heap because we need the top k. Step four, code it cleanly with real variable names, then dry run on a small concrete example, tracing the values aloud. This catches most off by one errors before the interviewer does.

Step five, enumerate edge cases yourself: empty input, one element, all elements identical, overflow on integer sums, and negative numbers. Finish by restating final time and space complexity. Candidates who jump straight to code and go silent for ten minutes get rejected even when the code compiles, because the panel cannot assess reasoning it did not hear.

Answer

On paper a linked list inserts in O(1) and an array inserts in O(n) because of the shift, while an array indexes in O(1) and a linked list indexes in O(n). Most candidates stop there and lose the question. The part interviewers actually want is cache locality.

An array is one contiguous block, so when the CPU loads a[0] it pulls an entire 64 byte cache line, which is 16 ints, meaning the next 15 accesses are free. A linked list node is a separate heap allocation with a pointer to the next node, so a traversal is a chain of dependent pointer dereferences to scattered addresses. Each one is likely a cache miss costing roughly 100 nanoseconds against about 1 nanosecond for an L1 hit, and the CPU cannot prefetch because it does not know the next address until the current load completes.

That is a 50x to 100x constant factor that Big O simply does not model. There is a second cost: in Java a LinkedList node stores a value reference plus next and previous pointers, roughly 40 bytes of overhead per element against 4 bytes for an int in an array. The practical result is that for n in the thousands, inserting into the middle of an ArrayList by memmove is usually faster than walking a LinkedList to the same position, because the O(1) insert is preceded by an O(n) traversal to find the spot.

Linked lists genuinely win when you already hold a reference to the node, which is why an LRU cache uses a doubly linked list plus a hashmap, and when you need stable references or O(1) splicing. Otherwise use an array backed structure.

// Array: contiguous, one cache line = 16 ints prefetched
int[] a = new int[n];
int x = a[i];              // O(1), L1 hit ~1ns

// LinkedList: pointer chase, likely cache miss per node
// each node ~40 bytes overhead vs 4 bytes for an int
Node cur = head;
while (cur != null) cur = cur.next;   // O(n) misses

// Insert at middle of ArrayList: O(n) memmove, but
// System.arraycopy is a vectorised block move
list.add(index, value);

// Insert into LinkedList still costs O(n) to FIND the node
// The O(1) splice only helps if you already hold the node

Answer

Strings are immutable in both Java and Python. Every concatenation allocates a brand new string and copies both operands into it, so the old object is discarded. Inside a loop that builds a string of final length n, iteration i copies i characters, and the total work is 1 + 2 + 3 + ... + n = n(n+1)/2, which is O(n^2) time and also produces O(n) garbage objects for the collector.

For n = 100000 this is roughly five billion character copies and will time out on any online assessment, which is exactly why this question appears in hidden test cases. StringBuilder solves it by holding a mutable char array with spare capacity, exactly like an ArrayList. Appending writes into the free space in O(1) amortised, and when capacity runs out the array doubles, giving the same geometric argument: O(n) total for n appends, with one final copy in toString.

Python's equivalent idiom is to collect pieces in a list and call "".join(parts), which computes the total length once, allocates a single buffer and copies each piece exactly once, again O(n). CPython has a refcount based optimisation that can sometimes extend a string in place when the variable holds the only reference, but it is an implementation detail that disappears on PyPy or when a second reference exists, so never rely on it. Two follow ups are common.

First, why is immutability worth this pain: strings can be shared safely across threads, cached hash codes stay valid, and Java can intern literals in the string pool. Second, StringBuilder versus StringBuffer: StringBuffer is synchronised and slower, and single threaded code should always use StringBuilder.

// O(n^2): allocates and copies on every iteration
String s = "";
for (int i = 0; i < n; i++) s += words[i];

// O(n): amortised append into a mutable char array
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(words[i]);
String result = sb.toString();

# Python, same quadratic trap
s = ""
for w in words:
    s += w          # O(n^2)

# Correct: one allocation, one copy per piece
s = "".join(words)  # O(n)

Answer

With the array sorted, place a pointer at each end. If the sum of the two values exceeds the target, the only way to reduce it is to move the right pointer left, because the left value is already the smallest available. If the sum is below the target, move the left pointer right for the mirror reason.

The correctness argument is an exchange argument: when you discard the right element, you have proved that it cannot pair with the current left element or with any element to the right of left, since all of those are at least as large. So every discarded candidate is provably not part of a solution, and the algorithm never skips a valid pair. That reasoning is what interviewers grade, because a candidate who cannot justify why the pointer moves is pattern matching.

The result is O(n) time and O(1) extra space against the O(n^2) brute force. If the array is unsorted, sorting first costs O(n log n), so the better answer is a hashmap: store each value with its index as you scan and check whether target minus the current value is already present, giving O(n) time and O(n) space in a single pass. State that trade off explicitly, space for time.

Two pointers generalises well beyond this: removing duplicates in place from a sorted array with a slow and fast pointer, the container with most water problem, three sum by fixing one element and running two pointers on the rest for O(n^2), and merging two sorted arrays. The standard follow ups are to return all unique pairs, which needs duplicate skipping after each match, and to handle an unsorted input, which is the hashmap variant.

// Sorted input: O(n) time, O(1) space
int[] twoSumSorted(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == target) return new int[]{lo, hi};
        if (sum < target) lo += 1;
        else hi -= 1;
    }
    return new int[]{-1, -1};
}

// Unsorted input: O(n) time, O(n) space, single pass
int[] twoSum(int[] a, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        Integer j = seen.get(target - a[i]);
        if (j != null) return new int[]{j, i};
        seen.put(a[i], i);
    }
    return new int[]{-1, -1};
}

Answer

Maintain a window [left, right] that always contains distinct characters. Extend right one character at a time. Store the last seen index of every character in a map.

When the incoming character was seen at an index at or after left, jump left to that index plus one, which removes the earlier occurrence in a single step. Update the best length at every position. For the string "abcabcbb", the window grows to "abc" of length 3, then the second 'a' pushes left to index 1 giving "bca", and the answer stays 3.

For "pwwkew" the answer is 3 from "wke". The complexity argument is the one interviewers want: right advances exactly n times, and left only ever moves forward and never past right, so left also advances at most n times in total across the whole run. Two monotone pointers over n positions means at most 2n pointer moves, so O(n) time despite the nested appearance of the loop.

Space is O(min(n, charset)), which is O(1) for a fixed ASCII alphabet if you use an int array of size 128 instead of a HashMap, and mentioning that array optimisation is a good signal. The classic bug is shrinking with left = map.get(c) + 1 without the guard that the stored index is still inside the window. In "abba" the second 'a' has a stored index of 0, and moving left backwards to 1 corrupts the window and returns 3 instead of 2.

Use left = Math.max(left, lastIndex + 1). The natural follow ups are longest substring with at most k distinct characters and minimum window substring, both the same window template with a different shrink condition.

// O(n) time, O(min(n, 128)) space
int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];
    Arrays.fill(last, -1);
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // guard: only move left FORWARD ("abba" bug)
        left = Math.max(left, last[c] + 1);
        last[c] = right;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

// "abcabcbb" -> 3 ("abc")
// "bbbbb"    -> 1 ("b")
// "pwwkew"   -> 3 ("wke")
// "abba"     -> 2  (fails without the max guard)

Answer

Build an array where prefix[i] is the sum of the first i elements, with prefix[0] = 0 as a sentinel. Then the sum of the range [l, r] inclusive is prefix[r + 1] minus prefix[l]. Building costs O(n) once, after which every query is O(1), which is the right structure whenever queries vastly outnumber updates.

The sentinel zero at index 0 is what removes the special case for l = 0, and forgetting it is the most common bug in this pattern. The important extension, and what interviews actually ask, is counting subarrays whose sum equals k. Since sum(l, r) = prefix[r + 1] - prefix[l], asking for a subarray summing to k is asking how many earlier prefix values equal current prefix minus k.

So sweep once, keep a HashMap from prefix value to how many times it has occurred, seed it with {0: 1} to account for subarrays starting at index 0, and at each position add the count of (running - k) to the answer. That is O(n) time and O(n) space and it works with negative numbers, which is precisely why the sliding window approach fails here: a window relies on the sum growing monotonically as you extend, and negatives break that invariant. Related variants that use the same trick are the longest subarray with sum k, subarray sums divisible by k, which keys the map on the modulo class, and counting subarrays with equal numbers of zeros and ones, which maps zero to minus one and then looks for a zero sum. For 2D there is an equivalent integral image where a rectangle sum is computed with four lookups by inclusion and exclusion.

// Range sums: O(n) build, O(1) per query
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];
int rangeSum = prefix[r + 1] - prefix[l];

// Count subarrays summing to k (works with negatives)
int subarraySum(int[] a, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);              // empty prefix, do not omit
    int running = 0, ans = 0;
    for (int x : a) {
        running += x;
        ans += count.getOrDefault(running - k, 0);
        count.merge(running, 1, Integer::sum);
    }
    return ans;                    // O(n) time, O(n) space
}

Answer

Kadane's algorithm scans once, carrying the best sum of a subarray that ends exactly at the current index. At each element the decision is binary: either extend the previous best ending subarray, or start fresh at this element. So current = max(a[i], current + a[i]), and the global answer is the maximum of all those values.

It is O(n) time and O(1) space against O(n^2) for the brute force and O(n log n) for divide and conquer. The reason it is correct is a dynamic programming argument: any optimal subarray ends at some index i, and the best subarray ending at i is exactly what the recurrence computes, so taking the max over all i is exhaustive. The bug that gets people rejected is initialising best to 0.

If every element is negative, the algorithm then returns 0, which corresponds to the empty subarray, and most problem statements require a non empty subarray, so the expected answer for [-3, -1, -7] is -1. Initialise both current and best to a[0] and loop from index 1, or use Integer.MIN_VALUE. Clarify with the interviewer whether the empty subarray is allowed; asking is a plus. Common follow ups: return the actual indices, which means tracking a tentative start that resets whenever you restart the window and committing it when best improves; the circular array variant, where the answer is the max of the normal Kadane result and the total sum minus the minimum subarray sum, with the special case that if all elements are negative that second formula produces an empty array and must be discarded; and the maximum product subarray, which needs both a running max and a running min because a negative number swaps them.

// O(n) time, O(1) space, correct for all negative input
int maxSubArray(int[] a) {
    int cur = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);
        best = Math.max(best, cur);
    }
    return best;
}

// WRONG for all negatives: returns 0 for [-3, -1, -7]
// int cur = 0, best = 0;

// With indices
int s = 0, bestL = 0, bestR = 0, cur = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
    if (cur + a[i] < a[i]) { cur = a[i]; s = i; }
    else cur += a[i];
    if (cur > best) { best = cur; bestL = s; bestR = i; }
}

Answer

Binary search maintains the invariant that if the target exists it lies within [lo, hi]. Compare against the middle element, discard the half that provably cannot contain it, repeat. Each step halves the search space so it is O(log n) time, and O(1) space iteratively or O(log n) recursively due to the call stack.

The famous bug is computing mid = (lo + hi) / 2. When lo and hi are both large, their sum overflows a 32 bit signed int, goes negative, and the array access throws ArrayIndexOutOfBoundsException. This bug lived in the JDK's own binary search for nine years until Joshua Bloch wrote it up in 2006.

The fix is mid = lo + (hi - lo) / 2, which never exceeds hi, or in Java mid = (lo + hi) >>> 1 using the unsigned shift. In Python integers are arbitrary precision so the overflow does not occur, but you should still name it because the interviewer is testing whether you know why the idiom exists. Termination requires that the range strictly shrinks every iteration.

With the while (lo <= hi) form you must write lo = mid + 1 and hi = mid - 1, never lo = mid, because if hi equals lo plus one then mid equals lo and lo = mid makes no progress, giving an infinite loop. Two other preconditions matter: the array must actually be sorted, and with duplicates plain binary search returns an arbitrary matching index, so you need lower bound or upper bound variants when you want the first or last occurrence. Expect follow ups on searching a rotated sorted array, where you identify which half is sorted first, and on binary searching the answer space rather than an array.

// O(log n) time, O(1) space
int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // NOT (lo + hi) / 2
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;               // must be mid - 1
    }
    return -1;
}

// The classic overflow:
// lo = 1_500_000_000, hi = 2_000_000_000
// (lo + hi) overflows int, goes negative -> AIOOBE
// Java alternative: int mid = (lo + hi) >>> 1;

Answer

The iterative version carries three references: prev starting at null, curr starting at head, and a temporary next. In each step save curr.next, point curr.next at prev, then advance prev to curr and curr to the saved next. When curr becomes null, prev is the new head.

It is O(n) time and O(1) space, and the reason you must save next before rewriting the pointer is that rewriting it destroys the only path to the rest of the list. Losing that temporary is the single most common bug and produces a one node list. The recursive version recurses to the tail, which becomes the new head, then on the way back sets head.next.next = head and head.next = null.

It is elegant but O(n) space because the call stack holds one frame per node, so a list of 100000 nodes overflows the stack. State that difference explicitly, because on any online assessment with large inputs the recursive version fails with a runtime error rather than a wrong answer. This question is rarely asked in isolation.

It is the building block for reverse nodes in k groups, reversing a sublist between positions m and n, checking whether a list is a palindrome in O(1) space by finding the middle with slow and fast pointers, reversing the second half and comparing, and reordering a list. A good habit for all of these is a dummy head node so that operations touching the first element need no special casing. Draw the pointer diagram on the whiteboard before coding, because the panel is watching whether you can reason about pointer rewiring without a compiler to catch you.

// Iterative: O(n) time, O(1) space
Node reverse(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node next = curr.next;   // save FIRST
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Recursive: O(n) time, O(n) stack space
Node reverseRec(Node head) {
    if (head == null || head.next == null) return head;
    Node newHead = reverseRec(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Answer

Floyd's tortoise and hare moves slow one node per step and fast two. If there is a cycle the fast pointer enters it first and then gains one node per step on the slow pointer, so the gap shrinks by exactly one each iteration and can never jump over, which means they must eventually coincide. If fast reaches null there is no cycle.

Detection is O(n) time and O(1) space. The proof for finding the cycle start is the part panels actually want. Let the distance from head to the cycle entry be x, the distance from the entry to the meeting point be y, and the remaining cycle length be z, so the cycle length is y + z.

When they meet, slow has travelled x + y and fast has travelled x + y + k(y + z) for some positive integer k. Fast has travelled exactly twice as far, so 2(x + y) = x + y + k(y + z), which simplifies to x + y = k(y + z) and therefore x = k(y + z) - y = (k - 1)(y + z) + z. In words, the distance from the head to the entry equals the distance from the meeting point forward to the entry, plus some whole number of extra laps.

So resetting one pointer to the head and advancing both one step at a time makes them meet exactly at the cycle entry. Cycle length is found by keeping one pointer fixed at the meeting point and counting steps until it returns. The interviewer's follow up is usually why a HashSet solution is unacceptable: it also runs in O(n) time but costs O(n) space, and the whole point of the question is the constant space constraint.

// Detect: O(n) time, O(1) space
Node detectCycleStart(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {          // cycle exists
            Node p = head;
            while (p != slow) {      // x = (k-1)(y+z) + z
                p = p.next;
                slow = slow.next;
            }
            return p;                // cycle entry node
        }
    }
    return null;                     // no cycle
}

Answer

Scan the string once. Push every opening bracket onto a stack. On a closing bracket, if the stack is empty the string is unbalanced because there is nothing to close, and otherwise pop and check that the popped opener is the matching type.

At the end, the string is balanced only if the stack is empty. That final emptiness check is the first commonly missed case: "(((" passes every in loop check and is still unbalanced. The second is the empty stack pop on input like ")(", which throws EmptyStackException if you pop blindly, and note that ")(" has equal counts of each bracket, which is why a simple counter solution is wrong for mixed bracket types.

Complexity is O(n) time and O(n) space, with the worst case space being all openers. A stack is the right structure because bracket nesting is last in first out by definition: the most recently opened bracket must be the first one closed. In Java prefer Deque with ArrayDeque over the legacy Stack class, since Stack extends Vector and is synchronised, so it is slower and iterates in the wrong order.

Use a HashMap from closing to opening bracket to keep the matching readable. Frequent extensions in Indian interviews: the minimum number of insertions to balance a string, the longest valid parentheses substring, which is either a stack of indices or a two pass left to right and right to left counter scan, and validating brackets when the string also contains wildcards. All of them build on this same push and pop skeleton, so getting the base case handling right matters more than it looks.

// O(n) time, O(n) space
boolean isBalanced(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (pairs.containsKey(c)) {
            if (stack.isEmpty()) return false;        // ")(" case
            if (stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();                           // "(((" case
}

Answer

For a queue from two stacks, keep an input stack and an output stack. Enqueue always pushes onto input, which is O(1). Dequeue pops from output, and only when output is empty do you drain the entire input stack into it, which reverses the order and puts the oldest element on top.

The naive analysis calls that O(n), but amortised it is O(1): every element is pushed to input once, moved to output once and popped once, so three constant operations per element across the whole lifetime, regardless of the interleaving of calls. This is the same amortised argument as array doubling, and stating it that way is the point of the question. The critical bug is transferring on every dequeue instead of only when output is empty, which makes it genuinely O(n) per call and also reorders elements incorrectly when enqueues are interleaved with dequeues.

A stack from two queues is the harder direction because a queue cannot reverse cheaply. The usual approach makes push expensive: enqueue the new element into the empty queue, then move every element from the other queue behind it, so the newest element is always at the front. That is O(n) push and O(1) pop with a single queue plus rotation.

There is no arrangement that gives O(1) amortised for both operations, which is the real answer to the comparison: stacks can be composed into a queue for free amortised, queues cannot be composed into a stack for free, because reversal is natural for LIFO and unnatural for FIFO. Follow ups include supporting peek, which uses the same lazy transfer, and making it thread safe.

// Queue from two stacks: O(1) amortised dequeue
class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>();
    private Deque<Integer> out = new ArrayDeque<>();

    void push(int x) { in.push(x); }              // O(1)

    int pop() {
        shift();
        return out.pop();                          // O(1) amortised
    }

    private void shift() {
        if (out.isEmpty()) {                       // ONLY when empty
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

// Stack from one queue: O(n) push, O(1) pop
void push(int x) {
    q.add(x);
    for (int i = 0; i < q.size() - 1; i++) q.add(q.remove());
}

Answer

A hash function must be deterministic, fast, and spread keys uniformly across buckets so that different keys rarely land in the same slot. A weak hash such as summing character codes maps "abc" and "cba" to the same value and creates immediate collisions, which is why real implementations use a polynomial rolling form: hash = hash * 31 + c, with 31 chosen because it is an odd prime and the JVM can compute it as a shift and subtract. Collisions are unavoidable by the pigeonhole principle, so the resolution strategy matters.

Chaining stores a list, or in modern Java a list that converts to a tree, at each bucket. It tolerates load factors above 1, deletion is trivial because you just unlink a node, and performance degrades gracefully. The cost is a pointer dereference per probe and extra memory for the node objects, and traversal has the same cache miss problem as any linked list.

Open addressing keeps everything in one array and probes for the next free slot. Linear probing checks the next index, which is extremely cache friendly because the probe sequence is contiguous, but it suffers primary clustering: once a run of occupied slots forms, any key hashing anywhere into that run extends it, so runs grow and probe lengths blow up as the load factor approaches 1. Quadratic probing and double hashing scatter the probe sequence to break up those clusters.

Deletion under open addressing needs tombstone markers, because clearing a slot outright would truncate the probe chain and make later keys unfindable. Python dicts and Go maps use open addressing, Java HashMap uses chaining, and the follow up is normally load factor and rehashing.

// Polynomial rolling hash (String.hashCode in Java)
int hash = 0;
for (char c : s.toCharArray()) hash = hash * 31 + c;

// Chaining: bucket holds a list
// bucket[i] -> (k1,v1) -> (k2,v2)
// load factor can exceed 1, delete is an unlink

// Linear probing: primary clustering
int idx = hash(key) % capacity;
while (table[idx] != null && !table[idx].key.equals(key)) {
    idx = (idx + 1) % capacity;    // contiguous run grows
}

// Double hashing breaks clusters
// idx = (h1(key) + i * h2(key)) % capacity

Answer

A binary tree is any tree where each node has at most two children, with no ordering constraint, so search is O(n) because you must examine everything. A binary search tree adds the invariant that every key in the left subtree is smaller than the node and every key in the right subtree is larger, which is what makes search, insert and delete O(h) where h is the height. The trap is that h is not automatically log n.

Inserting sorted data such as 1, 2, 3, 4, 5 into a plain BST produces a right skewed chain of height n, so operations degrade to O(n) and you have built a linked list with extra pointers. A balanced tree adds a rebalancing rule that keeps h at O(log n): AVL keeps the height difference of the two subtrees within 1, red black trees keep the longest path at most twice the shortest. This is why Java's TreeMap is a red black tree and not a plain BST.

On terminology, depth of a node is the number of edges from the root down to that node, so the root has depth 0. Height of a node is the number of edges on the longest path from that node down to a leaf, so a leaf has height 0. The height of the tree is the height of the root.

Some textbooks count nodes instead of edges, making both values one larger, so state your convention before you code, since an off by one on height is a real source of wrong answers on balanced tree checks. Related definitions worth knowing: a full tree has 0 or 2 children per node, a complete tree fills every level except possibly the last which fills left to right, and a perfect tree is both.

// BST invariant: left < node < right for the WHOLE subtree
//        8
//      /   \
//     3     10
//    / \      \
//   1   6      14

// Skewed BST from sorted inserts: height = n
// 1 -> 2 -> 3 -> 4 -> 5, search is O(n)

// Height (edges to deepest leaf), leaf height = 0
int height(Node n) {
    if (n == null) return -1;   // -1 for edge convention
    return 1 + Math.max(height(n.left), height(n.right));
}
// O(n) time, O(h) stack space

Answer

The three depth first orders differ only in where you process the node relative to its children. Preorder is node, left, right, and it is what you use to serialise or clone a tree because you create the parent before its children, and it is also the natural order for evaluating prefix expressions. Inorder is left, node, right, and on a binary search tree it emits keys in sorted ascending order, which is the standard way to validate a BST or to find the kth smallest element.

Postorder is left, right, node, which processes children before the parent, making it the correct order for deleting or freeing a tree, for computing subtree aggregates such as height, size or diameter, and for evaluating postfix expressions. Level order is breadth first, visiting the tree row by row using a queue, and it is what you need for the minimum depth, for printing a tree by levels, for right side view, and for any problem phrased in terms of levels or the shortest number of hops. All four are O(n) time.

The space differs and that is the follow up: the DFS orders take O(h) stack space, which is O(log n) on a balanced tree but O(n) on a skewed one, while level order takes O(w) where w is the maximum width, and on a perfect tree the last level holds about n/2 nodes, so BFS is O(n) space. Interviewers commonly ask for the iterative versions to test whether you understand the implicit stack, and ask you to reconstruct a tree from preorder plus inorder, which is possible, or from preorder plus postorder alone, which is not unique for general binary trees.

// All O(n) time. DFS: O(h) stack. BFS: O(w) queue.
void preorder(Node n)  { if (n == null) return; visit(n); preorder(n.left); preorder(n.right); }
void inorder(Node n)   { if (n == null) return; inorder(n.left); visit(n); inorder(n.right); }
void postorder(Node n) { if (n == null) return; postorder(n.left); postorder(n.right); visit(n); }

// Level order with a queue
List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int size = q.size();               // freeze the level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node n = q.poll();
            level.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        out.add(level);
    }
    return out;
}

Answer

The naive answers are sorting in O(n log n) or counting each value and rewriting the array in two passes. The interviewer wants one pass and O(1) space, which is Dijkstra's Dutch national flag partition. Keep three pointers: low marks the boundary after the last 0, mid is the scanning cursor, and high marks the boundary before the first 2.

The invariant is that everything before low is 0, everything from low up to mid is 1, everything after high is 2, and the region from mid to high is unexamined. On a[mid] == 0 swap with low, then advance both low and mid, which is safe because the value arriving at mid from low is already known to be a 1. On a[mid] == 1 just advance mid.

On a[mid] == 2 swap with high and decrease high, but crucially do not advance mid, because the value swapped in from high has never been inspected. That asymmetry is the entire question: candidates who advance mid on the 2 case get a wrong answer on inputs like [2, 0, 1] and cannot explain why. The loop runs while mid is less than or equal to high, and each iteration either advances mid or shrinks high, so it terminates in at most n steps: O(n) time and O(1) space.

Its real significance is that it is the three way partition used in quicksort to handle arrays with many duplicate keys, which turns quicksort's O(n^2) duplicate heavy worst case into linear behaviour. Expect a follow up asking you to generalise it to sorting by an arbitrary pivot value, or to the related problem of moving all zeros to the end while preserving relative order.

// One pass, O(n) time, O(1) space
void sortColors(int[] a) {
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a, low, mid);
            low += 1;
            mid += 1;
        } else if (a[mid] == 1) {
            mid += 1;
        } else {
            swap(a, mid, high);
            high -= 1;      // do NOT advance mid here
        }
    }
}

// [2,0,1] breaks if you advance mid on the 2 branch

Answer

When the values are a permutation of a bounded range such as 1 to n or 0 to n, the array itself can act as the hash table, which is how you drop the O(n) auxiliary space that a HashSet would cost. Cyclic sort walks index i and, while the value sitting at i does not belong there, swaps it to its correct home at index value minus 1. Each swap places at least one element permanently, so despite the inner while loop the total number of swaps across the whole run is at most n, giving O(n) time and O(1) space.

After the pass, any index i whose value is not i + 1 immediately identifies both the missing number, i + 1, and the duplicate, the value actually sitting there. The subtle part interviewers probe is the loop condition. Compare values, not indices, and use while a[i] != a[a[i] - 1] rather than while a[i] != i + 1, because with duplicates present the latter loops forever swapping two equal values back and forth.

That infinite loop is the failure mode they are looking for. The same template solves find all numbers disappeared in an array, find all duplicates, first missing positive, and set mismatch. Alternative approaches are worth naming as a comparison: XOR of all indices and values finds a single missing number in O(1) space but cannot handle a duplicate too, and the sum and sum of squares system of equations works but overflows a 32 bit int for large n. Cyclic sort is the one that generalises, which is why it is the expected answer.

// O(n) time, O(1) space
int[] findMissingAndDuplicate(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        // compare VALUES, not indices, or duplicates loop forever
        while (a[i] != a[a[i] - 1]) {
            int j = a[i] - 1;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] != i + 1) return new int[]{i + 1, a[i]};
    }
    return new int[]{-1, -1};
}
// total swaps <= n, so the nested while is still O(n)

Answer

Binary search does not need an array. It needs a monotonic predicate: a boolean function of a candidate answer that is false for every value below a threshold and true for every value at or above it. Whenever a problem asks for the minimum capacity, the minimum speed, the maximum minimum distance or the smallest value satisfying a constraint, you can binary search the answer space and use a feasibility check as the comparison.

The canonical example is the ship packages within D days problem: the answer lies between the largest single package weight and the total weight, and the check is a greedy O(n) simulation counting the days needed at a given capacity. Total cost is O(n log(sum of weights)), which is trivially fast even for large ranges. Koko eating bananas, split array largest sum, minimum days to make bouquets and allocate minimum pages are the same template, and the last one shows up constantly in Indian campus assessments.

The key move to say out loud is: identify the search space, prove the predicate is monotonic, then binary search it. Lower bound and upper bound are the array versions of the same idea. Lower bound returns the first index whose value is greater than or equal to the target, upper bound returns the first index strictly greater, and their difference is the count of occurrences of the target.

Both use the half open form while (lo < hi) with hi initialised to n rather than n minus 1, and they never test for equality inside the loop, they just narrow. That structure is what lets them handle duplicates correctly where plain binary search returns an arbitrary matching index.

// Lower bound: first index with a[i] >= target
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;          // hi = n, half open
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
// upperBound: change the test to a[mid] <= target
// count of target = upperBound - lowerBound

// Binary search on the answer: min capacity for D days
int shipWithinDays(int[] w, int days) {
    int lo = Arrays.stream(w).max().getAsInt();
    int hi = Arrays.stream(w).sum();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(w, mid, days)) hi = mid;
        else lo = mid + 1;
    }
    return lo;   // O(n log(sum))
}

Answer

Merge sort is O(n log n) in every case, stable, but needs O(n) auxiliary space. Quicksort is O(n log n) expected and O(n^2) worst case, unstable, and uses O(log n) stack space for recursion. Heap sort is O(n log n) guaranteed and in place, but unstable and slow in practice.

Insertion sort is O(n^2) in general but O(n) on nearly sorted input, stable, and genuinely the fastest choice for small arrays. Counting and radix sort break the comparison lower bound by exploiting bounded keys and run in O(n + k) and O(d * n). Stability means equal keys keep their original relative order, which matters whenever you sort by one field after another, for example sorting candidates by score and then by city while preserving the score order within a city.

The practical question is why quicksort beats merge sort despite the worse bound. Quicksort is in place, so it has no allocation and no copy back, it partitions with a single sequential scan that is extremely cache friendly, and its constant factor is roughly two to three times smaller. The O(n^2) case only occurs on adversarial pivot choices, which randomised or median of three pivots make vanishingly unlikely.

Java's Arrays.sort splits on element type for exactly these reasons. For primitives it uses a dual pivot quicksort, because primitives have no notion of identity so instability is unobservable, and in place sorting avoids allocation. For objects it uses TimSort, a stable hybrid of merge sort and insertion sort that detects existing sorted runs, because Java's specification guarantees stability for object sorting and real world data is often partially ordered. Both fall back to insertion sort under a small threshold.

// Java: primitives vs objects take different paths
int[] prim = {5, 2, 9};
Arrays.sort(prim);              // dual pivot quicksort, unstable, in place

Integer[] objs = {5, 2, 9};
Arrays.sort(objs);              // TimSort, stable, O(n) extra space

// Stability in action: sort by score, then by city
people.sort(Comparator.comparingInt(P::score));
people.sort(Comparator.comparing(P::city));   // score order kept

// Same thing in one comparator (preferred)
people.sort(Comparator.comparing(P::city)
                      .thenComparingInt(P::score));

// Quicksort partition: one sequential, cache friendly scan
// Merge sort: O(n) buffer plus a copy back each level

Answer

Merging two sorted lists is a dummy head plus a tail pointer. Walk both lists, attach the smaller head to the tail, advance that list, and when one list runs out attach the remainder of the other in one step rather than looping. It is O(n + m) time and O(1) extra space since you are relinking existing nodes rather than allocating.

The dummy head is the point of the exercise: without it you need a special case to initialise the result head, and that special case is where the bugs live. For k lists there are three answers and the interviewer wants you to compare them. Merging them one at a time into an accumulator costs O(kN) where N is the total number of nodes, because the growing accumulator is rescanned on every merge, and this is the naive answer to avoid.

A min heap holding the current head of each list gives O(N log k): poll the smallest, attach it, and push its successor. Space is O(k) for the heap. Divide and conquer pairs the lists and merges them level by level, halving the number of lists each round, which also gives O(N log k) time with O(log k) recursion space and no heap allocation, so it usually runs faster in practice.

Say both and pick divide and conquer for arrays of lists, heap for a streaming source where the lists arrive incrementally. The same k way merge with a heap is what external merge sort does when the data does not fit in memory, and mentioning that link is a strong signal in a lateral interview.

// Merge two: O(n + m) time, O(1) space
Node merge(Node a, Node b) {
    Node dummy = new Node(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;   // attach remainder
    return dummy.next;
}

// Merge k with a min heap: O(N log k) time, O(k) space
PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.val - y.val);
for (Node head : lists) if (head != null) pq.add(head);
Node dummy = new Node(0), tail = dummy;
while (!pq.isEmpty()) {
    Node n = pq.poll();
    tail.next = n; tail = n;
    if (n.next != null) pq.add(n.next);
}

Answer

The requirement is O(1) for both lookup by key and eviction of the least recently used entry, and no single structure gives you both. A hashmap gives O(1) lookup but has no notion of ordering, so finding the least recently used entry would be an O(n) scan. A doubly linked list gives O(1) removal and O(1) insertion at either end given a node reference, but has no O(1) lookup.

Combine them: the hashmap maps key to the node object, and the doubly linked list orders nodes by recency with the most recent at the head and the eviction victim at the tail. On get, look up the node in O(1), unlink it from its current position and move it to the head. On put, if the key exists update the value and move to head, otherwise create a node, insert at head, put it in the map, and if size now exceeds capacity remove the tail node and delete its key from the map.

It must be doubly linked because unlinking a node in O(1) requires access to its predecessor, and a singly linked list would force an O(n) walk to find it. Use sentinel head and tail nodes so that insertion and removal never need null checks, which eliminates most of the bug surface. The two mistakes interviewers watch for are forgetting to remove the evicted key from the map, which leaks memory and later returns a stale node, and updating the list on put but not on get, which breaks the recency semantics entirely. In Java, LinkedHashMap with accessOrder true and an overridden removeEldestEntry does this in a few lines, and saying so after presenting the manual design is a plus.

// O(1) get and put
class LRUCache {
    class N { int k, v; N prev, next; N(int k, int v){this.k=k;this.v=v;} }
    private final Map<Integer, N> map = new HashMap<>();
    private final N head = new N(0,0), tail = new N(0,0);
    private final int cap;

    LRUCache(int cap) { this.cap = cap; head.next = tail; tail.prev = head; }

    private void remove(N n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFirst(N n) { n.next = head.next; n.prev = head;
                                 head.next.prev = n; head.next = n; }

    int get(int k) {
        N n = map.get(k);
        if (n == null) return -1;
        remove(n); addFirst(n);            // refresh recency
        return n.v;
    }

    void put(int k, int v) {
        N n = map.get(k);
        if (n != null) { n.v = v; remove(n); addFirst(n); return; }
        if (map.size() == cap) {
            N lru = tail.prev;
            remove(lru);
            map.remove(lru.k);             // do not forget this
        }
        N fresh = new N(k, v);
        addFirst(fresh);
        map.put(k, fresh);
    }
}

Answer

The brute force compares every element against every later element, O(n^2). A monotonic stack does it in O(n). Scan left to right holding a stack of indices whose values are strictly decreasing.

For each new element, pop every index whose value is smaller than the current one, and the current element is the answer for each popped index. Push the current index. Anything left on the stack at the end has no greater element to its right, so it gets minus one.

Every index is pushed exactly once and popped at most once, so the total work is 2n despite the nested while loop, which is the amortised argument the interviewer wants stated. Space is O(n) for the stack. The general recognition rule is worth memorising: whenever the problem asks for the nearest greater or smaller element on either side, the answer is a monotonic stack.

That covers daily temperatures, stock span, largest rectangle in a histogram, which uses the nearest smaller on both sides, and trapping rain water. For the circular variant, iterate 2n times using index modulo n and only push during the first pass. Sliding window maximum is the same idea with a monotonic deque instead of a stack.

Maintain indices in decreasing value order from front to back. Before adding a new index, pop from the back while the back value is smaller, since it can never be the maximum while the newer larger element is in the window. Pop from the front when the front index falls outside the window. The front is always the current window maximum, and each index enters and leaves once, so it is O(n) time and O(k) space against O(n log k) with a heap.

// Next greater element: O(n) time, O(n) space
int[] nextGreater(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();   // indices, decreasing values
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
            res[stack.pop()] = a[i];
        }
        stack.push(i);
    }
    return res;
}

// Sliding window maximum: O(n) time, O(k) space
int[] maxSlidingWindow(int[] a, int k) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] out = new int[a.length - k + 1];
    for (int i = 0; i < a.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
        dq.addLast(i);
        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
    }
    return out;
}

Answer

The straightforward solution keeps a second stack of minima. On push, also push the smaller of the new value and the current minimum, so the auxiliary stack always mirrors the main stack in height and its top is the minimum of everything currently in the stack. On pop, pop both.

Every operation stays O(1) and space is O(n). The reason a single min variable fails is that popping the current minimum leaves you with no way to recover the previous minimum without an O(n) scan, so history is exactly what the auxiliary stack preserves. A memory optimisation is to push onto the auxiliary stack only when the new value is less than or equal to the current minimum, and pop it only when the popped value equals the current minimum.

The equality case matters: with strict less than, duplicated minima are recorded once and the first pop removes the tracker while a copy is still present, giving a wrong answer for a sequence like push 2, push 2, pop, getMin. The genuinely O(1) extra space version stores an encoded value. Keep a min field, and when pushing a value smaller than min, push the encoded 2 * value minus min and then set min to value.

On pop, if the popped encoded value is smaller than min, the previous minimum is recovered as 2 * min minus the encoded value. It works because the encoding is invertible, but flag the overflow risk out loud, since 2 * value minus min can exceed the int range and you should use long. Interviewers usually accept the two stack answer and use the encoded trick as a bonus, so present the clean solution first and offer the optimisation.

// Two stacks: O(1) ops, O(n) space
class MinStack {
    private Deque<Integer> s = new ArrayDeque<>();
    private Deque<Integer> mins = new ArrayDeque<>();

    void push(int x) {
        s.push(x);
        // <= is required, else duplicate minima break pop
        if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
    }
    void pop() {
        int top = s.pop();
        if (top == mins.peek()) mins.pop();
    }
    int top()    { return s.peek(); }
    int getMin() { return mins.peek(); }
}

// Encoded O(1) space variant (use long to avoid overflow)
// push: if (x < min) { s.push(2L*x - min); min = x; } else s.push(x);
// pop:  if (s.peek() < min) min = 2*min - s.pop();

Answer

The shunting yard algorithm scans the infix string once. Operands go straight to the output. An operator is pushed, but first you pop and emit every operator already on the stack with higher precedence, or equal precedence when the operator is left associative, which is what makes a minus b minus c parse as (a minus b) minus c rather than the wrong grouping.

An opening parenthesis is pushed unconditionally and acts as a barrier that nothing pops past. A closing parenthesis pops and emits until the matching opener is found, then discards both. At the end pop everything remaining.

It is O(n) time and O(n) stack space. Right associative operators such as exponentiation are the standard trap: for them you pop only strictly higher precedence, otherwise 2^3^2 evaluates as 64 instead of the correct 512. Postfix is worth producing because evaluating it needs no precedence rules at all: push operands, and on each operator pop two, apply, push the result, which is a single O(n) pass.

Watch operand order for non commutative operators, since the second value popped is the left operand. The connection to the call stack is that both are the same mechanism. When a function calls another, the caller's frame with its locals and return address is suspended on the stack while the callee runs, and control returns to the most recently suspended frame first, which is exactly the last in first out discipline that nested parentheses and operator precedence require. Expression evaluation, recursion and undo history are all the same shape, which is why compilers use an explicit stack to parse expressions and the hardware uses one to run the resulting code.

// Infix to postfix: O(n) time, O(n) space
String toPostfix(String expr) {
    Map<Character, Integer> prec = Map.of('+',1, '-',1, '*',2, '/',2, '^',3);
    StringBuilder out = new StringBuilder();
    Deque<Character> st = new ArrayDeque<>();
    for (char c : expr.toCharArray()) {
        if (Character.isLetterOrDigit(c)) out.append(c);
        else if (c == '(') st.push(c);
        else if (c == ')') {
            while (!st.isEmpty() && st.peek() != '(') out.append(st.pop());
            st.pop();                       // discard '('
        } else {
            // '^' is right associative: use > instead of >=
            while (!st.isEmpty() && st.peek() != '('
                   && prec.getOrDefault(st.peek(), 0) >= prec.get(c)) {
                out.append(st.pop());
            }
            st.push(c);
        }
    }
    while (!st.isEmpty()) out.append(st.pop());
    return out.toString();
}
// a+b*c  ->  abc*+      (a+b)*c  ->  ab+c*

Answer

A naive array queue that advances head on dequeue leaks capacity: after n dequeues the front of the array is dead space that can never be reused. A circular queue fixes this by wrapping the indices with modulo capacity, so the storage is reused indefinitely and both enqueue and dequeue stay O(1) with no shifting and no allocation. The classic ambiguity is that head equals tail means both empty and full, and there are three standard resolutions: keep an explicit size counter, which is the clearest and what I would write, waste one slot so full is defined as (tail + 1) % capacity == head, or keep monotonically increasing counters and take the modulo only when indexing.

Say which one you chose and why, because the interviewer is checking whether you noticed the ambiguity at all. A deque is a double ended queue: push and pop at both ends in O(1). It is a strict superset of both a stack and a queue, which is why Java's recommended stack is ArrayDeque rather than the legacy Stack class.

Implementations are either a circular array, which is what ArrayDeque uses, or a doubly linked list, which is what LinkedList uses, and the array version is faster for the same cache locality reasons discussed for lists. Real uses: circular buffers back producer and consumer pipelines, audio and network packet buffers, and fixed size ring logs where old entries are overwritten. Deques back sliding window maximum, undo and redo pairs, work stealing schedulers where a worker takes from its own front and thieves take from the back, and browser history. The natural follow up is BFS, which needs a plain FIFO queue and is where you should mention that the queue holds the frontier.

// Circular queue with an explicit size counter: O(1) ops
class CircularQueue {
    private final int[] a;
    private int head = 0, tail = 0, size = 0;

    CircularQueue(int cap) { a = new int[cap]; }

    boolean enqueue(int x) {
        if (size == a.length) return false;      // full
        a[tail] = x;
        tail = (tail + 1) % a.length;
        size += 1;
        return true;
    }
    int dequeue() {
        if (size == 0) throw new NoSuchElementException();
        int x = a[head];
        head = (head + 1) % a.length;
        size -= 1;
        return x;
    }
}

// Deque covers both stack and queue in O(1)
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); dq.addLast(2);
dq.pollFirst();  dq.pollLast();

Answer

Iterative inorder pushes the entire left spine onto a stack, then pops a node, visits it, and moves to its right child, repeating until both the stack and the current pointer are exhausted. It is O(n) time and O(h) space, the same asymptotics as the recursive version, but the stack now lives on the heap so a skewed tree with 100000 nodes does not blow the JVM stack. That resilience is the practical reason interviewers ask for it.

The conceptual reason is that they want to see you understand recursion is only syntactic sugar over an explicit stack, and once you internalise that, iterative preorder becomes trivial: push the root, then repeatedly pop and visit, pushing right before left so left comes off first. Postorder is the awkward one because a node must be visited only after both children. The clean trick is to run a modified preorder in node, right, left order and reverse the output, which is O(n) time and O(n) space for the result.

The genuinely single pass version tracks the last visited node to decide whether the right subtree has already been processed. Say the reversal trick first, then offer the last visited version if pushed. Two follow ups almost always appear.

First, iterative inorder on a BST is how you find the kth smallest element without materialising the whole traversal, since you can stop after k pops. Second, Morris traversal achieves O(1) space by temporarily threading each node's inorder predecessor's right pointer to it and undoing the thread on the way back, which is worth naming even if you do not write it, because it shows you know O(h) is not the floor.

// Iterative inorder: O(n) time, O(h) heap space
List<Integer> inorder(Node root) {
    List<Integer> out = new ArrayList<>();
    Deque<Node> st = new ArrayDeque<>();
    Node cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) { st.push(cur); cur = cur.left; }
        cur = st.pop();
        out.add(cur.val);              // stop here after k pops = kth smallest
        cur = cur.right;
    }
    return out;
}

// Iterative postorder via reversed (node, right, left)
List<Integer> postorder(Node root) {
    LinkedList<Integer> out = new LinkedList<>();
    Deque<Node> st = new ArrayDeque<>();
    if (root != null) st.push(root);
    while (!st.isEmpty()) {
        Node n = st.pop();
        out.addFirst(n.val);           // reverse as we go
        if (n.left != null) st.push(n.left);
        if (n.right != null) st.push(n.right);
    }
    return out;
}

Answer

The naive check verifies node.left.val < node.val < node.right.val at every node and returns true, and it is wrong because the BST property is about entire subtrees, not immediate children. Take the tree with root 10, left child 5, and the left child's right child 12. Every local comparison passes, but 12 sits in the root's left subtree while being greater than 10, so an inorder traversal produces 5, 12, 10, which is not sorted.

Interviewers use exactly this shape, so name it before they do. The correct approach propagates a valid range downwards. Each node must lie strictly within (low, high).

Recurse left with the range (low, node.val) and right with (node.val, high), starting from negative infinity to positive infinity. It is O(n) time and O(h) space. In Java use Long bounds or nullable Integer bounds, because a node holding Integer.MIN_VALUE breaks a naive int sentinel comparison, and that overflow edge case is a common follow up.

The equally valid alternative is an inorder traversal that checks the sequence is strictly increasing, keeping only the previous value rather than the whole list, which is O(n) time and O(h) space and has the nice property of early exit on the first violation. Decide up front how duplicates are handled and ask, since some definitions allow equal keys in the right subtree, and that single decision flips a strict less than to a less than or equal. The natural follow ups are recovering a BST where exactly two nodes were swapped, which is the inorder scan spotting one or two descents, and finding the largest BST subtree inside an arbitrary binary tree, which is a postorder aggregation.

// Range approach: O(n) time, O(h) space
boolean isBST(Node n, Long low, Long high) {
    if (n == null) return true;
    if (low != null && n.val <= low) return false;
    if (high != null && n.val >= high) return false;
    return isBST(n.left, low, (long) n.val)
        && isBST(n.right, (long) n.val, high);
}
// call: isBST(root, null, null)

// WRONG: local comparison only
//        10
//       /
//      5
//       \
//        12     <- passes local check, breaks the BST

// Inorder alternative: previous value must strictly increase
Integer prev = null;
boolean inorderCheck(Node n) {
    if (n == null) return true;
    if (!inorderCheck(n.left)) return false;
    if (prev != null && n.val <= prev) return false;
    prev = n.val;
    return inorderCheck(n.right);
}

Answer

The diameter is the number of edges on the longest path between any two nodes, and that path need not pass through the root. The naive solution computes height at every node and sums the two child heights, which is O(n^2) because height is recomputed repeatedly. The linear solution is a postorder pass where each call returns the height of its subtree while updating a shared best with leftHeight plus rightHeight, the path that bends at this node.

Because every node is the bend point of exactly one candidate path, taking the maximum over all nodes is exhaustive. O(n) time, O(h) space. LCA in a general binary tree is the same postorder shape: recurse both sides, and if both sides return non null then the current node is the split point and therefore the LCA, otherwise propagate whichever side was non null.

This assumes both nodes exist in the tree, so ask, because if one might be absent you need a second pass or a found counter, and returning a wrong ancestor for a missing node is the classic bug. In a BST you can do better by exploiting ordering: walk down from the root, go left when both targets are smaller, right when both are larger, and stop at the first node that sits between them, which is O(h) time and O(1) space iteratively. The shared pattern, and the thing to say out loud, is that many tree problems are solved by a single postorder pass where the recursion returns one value upward, the height or an ancestor, while a shared accumulator records the best answer seen so far. Balanced tree checking, maximum path sum and largest BST subtree are all the same template.

// Diameter: O(n) time, O(h) space, one postorder pass
int best = 0;
int height(Node n) {
    if (n == null) return -1;
    int l = height(n.left), r = height(n.right);
    best = Math.max(best, l + r + 2);   // edges through this node
    return 1 + Math.max(l, r);
}

// LCA in a general binary tree: O(n) time, O(h) space
Node lca(Node n, Node p, Node q) {
    if (n == null || n == p || n == q) return n;
    Node l = lca(n.left, p, q);
    Node r = lca(n.right, p, q);
    if (l != null && r != null) return n;   // split point
    return (l != null) ? l : r;
}

// LCA in a BST: O(h) time, O(1) space
Node lcaBst(Node n, int p, int q) {
    while (n != null) {
        if (p < n.val && q < n.val) n = n.left;
        else if (p > n.val && q > n.val) n = n.right;
        else return n;
    }
    return null;
}

Answer

Insert walks down comparing keys until it hits a null link and attaches the new node there, which is O(h). The recursive form that returns the subtree root and assigns it back, node.left = insert(node.left, key), is cleaner than manual parent tracking and is what I would write in an interview. Delete has three cases.

A leaf is removed by returning null to the parent. A node with one child is replaced by that child. The two child case is the one that matters: you cannot simply remove the node because two subtrees would be orphaned, so you replace its key with either its inorder successor, the minimum of the right subtree, or its inorder predecessor, the maximum of the left subtree, then recursively delete that successor from the right subtree.

Either choice preserves the BST ordering because the successor is by definition the smallest key still greater than everything in the left subtree. The recursive delete of the successor is guaranteed to terminate quickly because the successor has at most one child, being the leftmost node of its subtree, so it falls into one of the easy cases. Both operations are O(h), which is O(log n) only when the tree is balanced, so state that constraint.

Two practical notes interviewers like. Repeatedly deleting using the successor biases the tree to the left over time and degrades it, which is why production implementations alternate or use a self balancing tree. And a plain BST built from sorted input degenerates into a linked list, so real systems use red black trees, which is what Java's TreeMap and C++ std::map are built on. The natural follow up is what rotation would restore balance here, which leads into AVL.

// Insert: O(h)
Node insert(Node n, int key) {
    if (n == null) return new Node(key);
    if (key < n.val) n.left = insert(n.left, key);
    else if (key > n.val) n.right = insert(n.right, key);
    return n;                       // duplicates ignored
}

// Delete: O(h)
Node delete(Node n, int key) {
    if (n == null) return null;
    if (key < n.val) { n.left = delete(n.left, key); return n; }
    if (key > n.val) { n.right = delete(n.right, key); return n; }

    if (n.left == null) return n.right;      // 0 or 1 child
    if (n.right == null) return n.left;

    Node succ = n.right;                     // two children
    while (succ.left != null) succ = succ.left;
    n.val = succ.val;
    n.right = delete(n.right, succ.val);
    return n;
}

Answer

A HashMap holds an array of buckets whose length is always a power of two. On put, it takes key.hashCode(), applies a spread function that XORs the high 16 bits into the low 16, and indexes with hash AND (n minus 1), which is a cheap substitute for modulo that works only because the length is a power of two. The spread step exists because that AND discards the high bits entirely, so hash codes differing only in their upper half would all collide.

Colliding entries form a linked list in the bucket. The load factor, 0.75 by default, is the fill ratio at which the table resizes: once size exceeds capacity times load factor, capacity doubles and every entry is redistributed. That resize is O(n) and is why you should pre size a map you know the size of, using new HashMap<>(expected / 0.75f + 1).

Since Java 8, once a single bucket reaches 8 entries and the table has at least 64 buckets, that bucket converts from a linked list into a red black tree, so worst case lookup within a bucket becomes O(log k) instead of O(k). It untreeifies back to a list at 6 entries, with the gap preventing thrashing. Degradation to O(n) happens when the hash function is poor and everything lands in one bucket, and before Java 8 that made HashMap collision denial of service attacks practical against web servers hashing request parameters.

The hashCode and equals contract is the other half: equal objects must produce equal hash codes, otherwise a lookup goes to the wrong bucket and never finds the entry. Mutating a key field after insertion changes its hash and strands the entry permanently, which is why map keys should be immutable.

// Index computation (power of two capacity)
int h = key.hashCode();
h = h ^ (h >>> 16);              // spread high bits down
int index = h & (capacity - 1);  // cheap modulo

// Resize trigger: size > capacity * 0.75
// Pre size to avoid the O(n) rehash
Map<String, Integer> m = new HashMap<>((int) (expected / 0.75f) + 1);

// Contract: equal objects MUST have equal hash codes
class Candidate {
    String email;
    @Override public boolean equals(Object o) {
        return o instanceof Candidate c && email.equals(c.email);
    }
    @Override public int hashCode() { return email.hashCode(); }
}

// Java 8+: bucket of 8 entries with table >= 64 becomes a
// red black tree, so a hot bucket is O(log k) not O(k)

Answer

The intuitive but wrong answer is that building a heap means n insertions of O(log n) each, giving O(n log n). That is true if you insert one at a time, but the bottom up build is different. Floyd's heapify starts at the last internal node, index n/2 minus 1, and sifts each node down, working backwards to the root.

The cost of sifting a node down is proportional to its height, not the height of the tree, and a heap is bottom heavy: about n/2 nodes are leaves with height 0 and cost nothing, n/4 have height 1, n/8 have height 2, and so on. Total work is the sum over h of (n / 2^(h+1)) times h, and that series converges to 2n, so building is O(n). The one line version of the argument is that most nodes are near the bottom and barely move, while only the few nodes near the root do expensive work.

A heap is stored as an array with no pointers: for index i the children are 2i+1 and 2i+2 and the parent is (i-1)/2, which makes it compact and cache friendly. Insert sifts up in O(log n), extract min swaps the last element to the root and sifts down in O(log n), and peek is O(1). Heap sort builds a max heap in O(n), then repeatedly swaps the root with the last unsorted position and sifts down over a shrinking heap, giving O(n log n) total with O(1) extra space and a guaranteed worst case. It is nonetheless slower than quicksort in practice because the sift down jumps around the array and destroys cache locality, and it is unstable, which is why library sorts use it only as a fallback.

// Bottom up build: O(n), not O(n log n)
void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i -= 1) siftDown(a, i, a.length);
}

void siftDown(int[] a, int i, int size) {
    while (true) {
        int l = 2 * i + 1, r = 2 * i + 2, largest = i;
        if (l < size && a[l] > a[largest]) largest = l;
        if (r < size && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        i = largest;
    }
}

// Heap sort: O(n log n) time, O(1) space, unstable
void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end -= 1) {
        int t = a[0]; a[0] = a[end]; a[end] = t;
        siftDown(a, 0, end);
    }
}

Answer

For top k, count frequencies in a HashMap in O(n), then push entries into a min heap of size k, evicting the smallest whenever the heap exceeds k. Every push is O(log k) so total time is O(n log k) with O(n + k) space, which beats sorting all counts at O(n log n) whenever k is much smaller than n. The counterintuitive part that gets asked is why a min heap for the largest k: the heap root is the weakest survivor, so it is the cheapest thing to evict when a stronger candidate arrives.

Say that out loud, and mention that bucket sort by frequency gives a true O(n) alternative, since frequencies are bounded by n, so you can index buckets by count and read them from the top. For a streaming median you need the middle of a growing multiset with fast insertion, and no single heap gives it because a heap exposes only one extreme. Use two: a max heap holding the smaller half and a min heap holding the larger half.

After every insertion rebalance so their sizes differ by at most one. The median is then the root of the larger heap, or the average of the two roots when sizes are equal, in O(1). Insertion is O(log n).

The invariant to protect is that every element of the low heap is less than or equal to every element of the high heap, which means you must push the new value into one heap and immediately move that heap's root across, rather than choosing a heap by comparison alone. Interviewers follow up with the sliding window median, which additionally needs lazy deletion or an ordered multiset, and with what changes if the stream contains billions of values, which leads into approximate quantile sketches.

// Top k frequent: O(n log k) time
Map<Integer, Integer> freq = new HashMap<>();
for (int x : a) freq.merge(x, 1, Integer::sum);
PriorityQueue<Integer> pq =
    new PriorityQueue<>((x, y) -> freq.get(x) - freq.get(y));  // MIN heap
for (int key : freq.keySet()) {
    pq.add(key);
    if (pq.size() > k) pq.poll();      // evict the weakest
}

// Streaming median: O(log n) add, O(1) find
PriorityQueue<Integer> low  = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> high = new PriorityQueue<>();

void addNum(int x) {
    low.add(x);
    high.add(low.poll());              // keeps low <= high
    if (high.size() > low.size()) low.add(high.poll());
}
double findMedian() {
    return low.size() > high.size() ? low.peek()
                                    : (low.peek() + high.peek()) / 2.0;
}

Answer

BFS explores level by level with a queue and finds the shortest path in an unweighted graph because it reaches every vertex by the fewest edges possible. Its memory is O(w) where w is the widest frontier, which on a dense graph can be most of the vertex set. DFS explores as deep as possible with a stack or recursion, uses O(h) memory, and is the right tool for anything about structure rather than distance: connectivity, topological order, cycle detection, bridges and articulation points, and strongly connected components.

Both are O(V + E) with an adjacency list. Real uses: BFS for shortest hops in a social graph or a word ladder, for multi source flood fill such as rotting oranges, and for level order problems; DFS for island counting, dependency resolution and backtracking. Cycle detection differs because of edge direction.

In an undirected graph, any edge to an already visited vertex that is not the vertex you came from is a cycle, so you carry a parent argument and skip it. Forgetting the parent check reports a false cycle on every single edge, since u and v each see the other as visited. Note that a parent check by vertex fails on parallel edges, so with multi edges you track the edge id instead.

In a directed graph the parent trick is meaningless and visited alone is not enough, because reaching a vertex again through a different path is legal in a DAG. You need three states: unvisited, in the current recursion stack, and fully done. A cycle exists only when you reach a vertex that is currently on the recursion stack, which is a back edge. The iterative equivalent is Kahn's algorithm: if topological sort cannot place every vertex, a cycle exists.

// Undirected cycle detection: parent check required
boolean dfsUndirected(int u, int parent, List<List<Integer>> adj, boolean[] vis) {
    vis[u] = true;
    for (int v : adj.get(u)) {
        if (!vis[v]) {
            if (dfsUndirected(v, u, adj, vis)) return true;
        } else if (v != parent) {
            return true;                 // real cycle
        }
    }
    return false;
}

// Directed cycle detection: three states, back edge to the stack
int[] state;   // 0 unvisited, 1 in stack, 2 done
boolean dfsDirected(int u, List<List<Integer>> adj) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) return true;                 // back edge
        if (state[v] == 0 && dfsDirected(v, adj)) return true;
    }
    state[u] = 2;
    return false;
}
// Both O(V + E). Bipartite check: BFS colouring, conflict means odd cycle

Answer

A topological order lists the vertices of a directed acyclic graph so that every edge points forwards, which is exactly what you need for build systems, task schedulers, package managers and course prerequisite problems. Kahn's algorithm computes it iteratively. Compute the in degree of every vertex, seed a queue with every vertex of in degree zero, then repeatedly remove a vertex, append it to the order, and decrease the in degree of each neighbour, enqueuing any that drop to zero.

It is O(V + E) time and O(V) space. The elegant part is cycle detection for free: if the produced order contains fewer than V vertices, the remaining vertices all had a non zero in degree that never resolved, which means they sit on a cycle. For course scheduling, model each course as a vertex and each prerequisite pair as an edge from the prerequisite to the course, then the schedule is feasible exactly when a full topological order exists.

Course schedule two asks for the order itself, which is the same run returning the accumulated list. The DFS alternative pushes each vertex onto a stack after all its descendants are finished and reverses the result, which is also O(V + E) but detects cycles through the three state colouring described earlier and risks stack overflow on deep graphs, so Kahn is the safer choice under an assessment time limit. Two things interviewers probe.

First, the order is not unique when several vertices have in degree zero at once, so if the problem demands lexicographically smallest, swap the queue for a min heap and accept O(V log V + E). Second, the algorithm modifies in degrees, so copy them if the caller needs the graph intact. A useful extension is the longest path in a DAG, which is a single dynamic programming pass in topological order.

// Kahn: O(V + E) time, O(V) space
int[] topoOrder(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) {        // e = {prereq, course}
        adj.get(e[0]).add(e[1]);
        indeg[e[1]] += 1;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);

    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx] = u;
        idx += 1;
        for (int v : adj.get(u)) {
            indeg[v] -= 1;
            if (indeg[v] == 0) q.add(v);
        }
    }
    // fewer than n placed => a cycle exists => schedule impossible
    return idx == n ? order : new int[0];
}

Answer

Dijkstra maintains tentative distances and repeatedly finalises the closest unfinalised vertex, relaxing its outgoing edges. With a binary heap it is O((V + E) log V), and with an adjacency matrix and a linear scan it is O(V^2), which is actually better on dense graphs where E approaches V^2. That representation choice matters generally: an adjacency matrix costs O(V^2) memory and gives O(1) edge lookup, while an adjacency list costs O(V + E) memory and iterates neighbours efficiently, so for a sparse graph with a million vertices a matrix is a terabyte and simply not an option.

Dijkstra's correctness rests on a greedy invariant: once a vertex is popped with the smallest tentative distance, no shorter path to it can exist, because any other route would have to pass through some unfinalised vertex that is already at least as far away. Negative edges destroy that invariant, since a later path could dip negative and undercut a finalised distance, so Dijkstra returns wrong answers rather than looping. It can be wrong even when there is no negative cycle at all, which is the precise statement interviewers want.

Bellman-Ford handles negative weights by relaxing every edge V minus 1 times, since any shortest path has at most V minus 1 edges, giving O(V * E). A further relaxation pass that still improves something proves a reachable negative cycle exists, which is how currency arbitrage is detected. Floyd-Warshall computes all pairs shortest paths with three nested loops over an intermediate vertex k, in O(V^3) time and O(V^2) space, and is the practical choice for dense graphs up to a few hundred vertices or when you need every pair. For unweighted graphs plain BFS is O(V + E) and beats all of them, and for uniform weights that alternate between two values a 0/1 BFS with a deque is the right tool.

// Dijkstra with a binary heap: O((V + E) log V)
int[] dijkstra(List<List<int[]>> adj, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.add(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        if (cur[1] > dist[cur[0]]) continue;   // stale entry, skip
        for (int[] e : adj.get(cur[0])) {      // e = {to, weight}
            int nd = dist[cur[0]] + e[1];
            if (nd < dist[e[0]]) {
                dist[e[0]] = nd;
                pq.add(new int[]{e[0], nd});
            }
        }
    }
    return dist;
}

// Bellman-Ford: O(V * E), detects negative cycles
for (int i = 0; i < n - 1; i++)
    for (int[] e : edges)
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]])
            dist[e[1]] = dist[e[0]] + e[2];
// one more improving pass => negative cycle

// Floyd-Warshall: O(V^3), all pairs
for (int k = 0; k < n; k++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);

Answer

A minimum spanning tree connects every vertex of a connected undirected weighted graph with the smallest total edge weight and exactly V minus 1 edges. Kruskal sorts all edges by weight and adds each one unless it would form a cycle, which is tested with a union find structure. Sorting dominates at O(E log E), and since E is at most V^2 that is equivalent to O(E log V), with union find operations effectively constant.

Prim grows a single tree from an arbitrary start vertex, repeatedly taking the cheapest edge crossing from the tree to the outside using a priority queue, giving O(E log V) with a binary heap or O(V^2) with an adjacency matrix and no heap. Both are greedy and both are correct because of the cut property: for any partition of the vertices into two sets, the lightest edge crossing that cut belongs to some minimum spanning tree. Kruskal applies it globally over the sorted edge list, Prim applies it locally to the cut between the current tree and everything else.

Choose Kruskal for sparse graphs, when the edge list is the natural input format, or when the edges are already sorted, and choose Prim for dense graphs, especially the O(V^2) matrix form which beats Kruskal's sort when E approaches V^2. Kruskal also handles a disconnected graph gracefully by producing a minimum spanning forest, whereas Prim only covers the component containing its start vertex. Practical caveats interviewers raise: the MST is unique only when all edge weights are distinct, otherwise several trees can tie at the same total weight; and an MST does not minimise the path between any specific pair of vertices, so it is not a substitute for Dijkstra. Real uses include network and cable layout, clustering by deleting the k minus 1 heaviest MST edges, and approximation algorithms for the travelling salesman problem.

// Kruskal: O(E log E), needs union find
int kruskal(int n, int[][] edges) {   // edges = {u, v, w}
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    DSU dsu = new DSU(n);
    int total = 0, used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) {   // false if it makes a cycle
            total += e[2];
            used += 1;
            if (used == n - 1) break;
        }
    }
    return used == n - 1 ? total : -1;   // -1 = disconnected
}

// Prim with a heap: O(E log V)
int prim(List<List<int[]>> adj, int n) {
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.add(new int[]{0, 0});
    int total = 0, count = 0;
    while (!pq.isEmpty() && count < n) {
        int[] cur = pq.poll();
        if (inTree[cur[0]]) continue;
        inTree[cur[0]] = true;
        total += cur[1];
        count += 1;
        for (int[] e : adj.get(cur[0]))
            if (!inTree[e[0]]) pq.add(new int[]{e[0], e[1]});
    }
    return count == n ? total : -1;
}

Answer

Disjoint set union maintains a partition of elements into sets with two operations: find returns the representative of an element's set, and union merges two sets. Naive implementations degrade to O(n) per operation because the tree of parent pointers can become a chain. Two optimisations fix this.

Union by rank, or by size, always attaches the shallower or smaller tree under the deeper or larger one, which keeps the height at O(log n) on its own. Path compression flattens the path during find by pointing every node visited directly at the root, so subsequent finds on those elements are constant. Applied together the amortised cost per operation is O(alpha(n)) where alpha is the inverse Ackermann function, which is at most 4 for any n that fits in the universe, so it is constant for all practical purposes.

Say alpha and then say effectively constant, because the interviewer wants both the precise bound and the practical reading. The tie break matters: on equal ranks pick either root and increment its rank by one, and note that rank is only an upper bound on height once path compression starts flattening trees, so you never decrease it. Three problem families it solves.

First, connected components and dynamic connectivity in an undirected graph, counting components by starting at n and decrementing on every successful union, which is the standard number of provinces or number of islands two problem. Second, Kruskal's MST cycle test. Third, the redundant connection problem, where the first edge whose endpoints already share a root is the answer. Others worth naming are accounts merge, where emails are unioned per account, evaluate division with weighted union find carrying a ratio to the parent, and offline dynamic connectivity processed in reverse.

// Union find: O(alpha(n)) amortised, effectively constant
class DSU {
    private final int[] parent, rank;
    private int components;

    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path halving
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;          // already together = cycle
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra] += 1;
        components -= 1;
        return true;
    }

    int components() { return components; }
}

Answer

Both keep a binary search tree's height logarithmic so operations stay O(log n) instead of degrading to O(n) on sorted input. An AVL tree stores a balance factor at each node, the height of the left subtree minus the height of the right, and requires it to stay within minus one to plus one. After an insertion or deletion you walk back up and rebalance with rotations.

There are four cases: left left needs a single right rotation, right right needs a single left rotation, left right needs a left rotation on the child followed by a right rotation on the node, and right left is the mirror. A rotation is a constant time pointer rewiring that preserves inorder order, which is why the BST property survives it. An insertion needs at most one rotation to restore balance, but a deletion may need O(log n) rotations up the path.

A red black tree enforces looser rules: every node is red or black, the root and all null leaves are black, a red node cannot have a red child, and every path from a node to its descendant leaves contains the same number of black nodes. Together those guarantee the longest path is at most twice the shortest, so height is O(log n), but the tree is less rigidly balanced than AVL. That trade off decides the usage.

AVL is more strictly balanced so lookups are slightly faster, making it preferable for read heavy workloads such as in memory indexes. Red black trees rebalance less on writes, so they win on write heavy workloads, which is why they back Java's TreeMap and TreeSet, C++ std::map and std::set, the Linux kernel's completely fair scheduler run queue and its virtual memory area tree, and the treeified buckets in Java 8's HashMap.

// Right rotation: fixes the left left case, O(1)
//     y            x
//    / \          / \
//   x   C   =>   A   y
//  / \              / \
// A   B            B   C
Node rotateRight(Node y) {
    Node x = y.left;
    Node b = x.right;
    x.right = y;
    y.left = b;
    y.height = 1 + Math.max(h(y.left), h(y.right));
    x.height = 1 + Math.max(h(x.left), h(x.right));
    return x;                      // new subtree root
}

// Four AVL cases after computing balance = h(left) - h(right)
// balance > 1  and key < node.left.val   -> rotateRight(node)
// balance < -1 and key > node.right.val  -> rotateLeft(node)
// balance > 1  and key > node.left.val   -> left then right
// balance < -1 and key < node.right.val  -> right then left

// Red black: root black, no red parent with a red child,
// equal black height on every root to leaf path
// => longest path <= 2 * shortest path => height O(log n)

Answer

The answer is disk and page geometry, not asymptotics. A balanced binary search tree over a hundred million rows has a height around 27, and if each node is a separate disk page that is 27 random input and output operations per lookup, which even on an SSD is orders of magnitude slower than the comparison work. Storage is read in fixed pages, typically 4KB, 8KB or 16KB, and reading one byte costs the same as reading the whole page.

A B-tree exploits this by storing hundreds of keys per node, one node per page, so the branching factor is in the hundreds and the height collapses. With a fan out of 400 you address 400^4, which is over 25 billion rows, in four levels, and the top levels stay cached in memory so a lookup is often a single physical read. The height is O(log_b n) where b is the fan out.

A B+ tree refines this further and is what MySQL InnoDB and PostgreSQL actually use for their primary indexes. All values live only in the leaf nodes and internal nodes hold keys purely for routing, which means internal nodes pack more keys per page and the fan out rises again, and the leaves are chained in a doubly linked list. That leaf chain is the decisive feature: a range query such as fetching every candidate with experience between 3 and 7 years finds the first leaf in O(log n) and then walks the chain sequentially, which is exactly the access pattern disks and read ahead are optimised for. Hash indexes give O(1) point lookups and are excellent for equality, but they cannot answer range queries, cannot serve an ORDER BY, and cannot support prefix matching on a composite key, which is why they are a specialised index type rather than the default.

// Height comparison for 100 million rows
// Binary search tree : log2(1e8)   ~ 27 levels  -> 27 disk reads
// B+ tree, fan out 400: log400(1e8) ~ 3.2 levels -> 3 to 4 reads

// B+ tree shape
// internal:      [ 10 | 40 | 90 ]        keys route only
//               /     |    |     \
// leaves:  [1..9] <-> [10..39] <-> [40..89] <-> [90..]
//                       linked leaves = cheap range scans

// Range scan: descend once, then walk the leaf chain
// SELECT * FROM candidates WHERE exp BETWEEN 3 AND 7;
//   O(log n) to locate, then sequential

// Hash index: O(1) equality, but this cannot use it
// SELECT * FROM candidates ORDER BY exp;

Answer

A trie stores strings as a tree of characters where each path from the root spells a prefix, so all words sharing a prefix share a path. Insert and exact lookup are O(L) where L is the word length, and crucially independent of how many words are stored, which a hashmap cannot match once you need prefix semantics. For autocomplete on city names, walk the query down the trie in O(L), then collect the words in the subtree below that node with a depth first search, which costs O(k) in the number of results.

Typing "Ban" descends three levels and yields Bangalore, Banda, Bankura; typing "Che" yields Chennai and Cherrapunji. To rank suggestions, store the top k completions or a popularity score at each node, so the answer is read directly rather than recollected, which is what production search boxes do. The hashmap alternative that stores every prefix of every word works and gives O(1) lookup, but the space cost is O(n * L^2) characters across all entries, versus a trie that shares prefixes and stores roughly the number of distinct prefix characters.

For a list of 5000 Indian cities the difference is small, but for millions of search queries it decides feasibility. A plain hashmap keyed only on full words cannot answer prefix queries at all without scanning every key, which is the point to state clearly. Trie space is the honest weakness: a naive node with 26 child pointers wastes memory on sparse branches, so use a HashMap of children, or compress single child chains into a radix tree, which is what IP routing tables and Redis stream keys use. Other classic trie problems are word search two on a board, longest common prefix, replace words with roots, and maximum XOR of two numbers using a binary trie of bits.

// Trie for city autocomplete: O(L) insert and prefix lookup
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord;
    String word;
}

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String city) {
        TrieNode cur = root;
        for (char c : city.toLowerCase().toCharArray()) {
            cur = cur.children.computeIfAbsent(c, k -> new TrieNode());
        }
        cur.isWord = true;
        cur.word = city;
    }

    List<String> suggest(String prefix, int limit) {
        TrieNode cur = root;
        for (char c : prefix.toLowerCase().toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) return List.of();     // O(L)
        }
        List<String> out = new ArrayList<>();
        collect(cur, out, limit);                  // O(k)
        return out;
    }

    private void collect(TrieNode n, List<String> out, int limit) {
        if (out.size() >= limit) return;
        if (n.isWord) out.add(n.word);
        for (TrieNode child : n.children.values()) collect(child, out, limit);
    }
}
// "ban" -> [Bangalore, Banda, Bankura]

Answer

The choice is driven by whether the underlying array changes. A prefix sum array answers any range sum in O(1) after an O(n) build, and it is the right answer when the data is static, because nothing else beats a constant time query. The moment a single element updates, the prefix array must be rebuilt from that index onwards at O(n) per update, so with q updates you pay O(nq), which is what fails the hidden test cases.

A Fenwick tree, also called a binary indexed tree, gives O(log n) for both point update and prefix query, using O(n) space and about ten lines of code. It works by having index i hold the sum of a block whose length is the lowest set bit of i, so traversal uses i AND minus i to jump between blocks. It is limited to operations with an inverse, which is why it handles sums and XOR naturally but not minimum or maximum, since range minimum cannot be derived by subtracting one prefix from another.

A segment tree stores every range in a binary tree of 4n nodes and supports any associative operation: sum, minimum, maximum, greatest common divisor, or a custom merge. Build is O(n), query and update are O(log n), and with lazy propagation it also supports range updates in O(log n) by deferring a pending change at an internal node until a query descends into it. So the decision rule to state out loud is: static data, use prefix sums; point updates with sums only, use a Fenwick tree because it is smaller, faster by constant factors and much less code; anything else, minima, maxima, range assignments or range additions, use a segment tree with lazy propagation. The follow ups are usually the 2D versions and, for the offline case where all queries are known in advance, Mo's algorithm at O((n + q) * sqrt(n)).

// Fenwick tree: O(log n) update and prefix query, O(n) space
class Fenwick {
    private final int[] t;
    Fenwick(int n) { t = new int[n + 1]; }

    void update(int i, int delta) {          // 1 indexed
        for (; i < t.length; i += i & (-i)) t[i] += delta;
    }
    int prefix(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i)) s += t[i];
        return s;
    }
    int range(int l, int r) { return prefix(r) - prefix(l - 1); }
}

// Segment tree query: any associative merge, O(log n)
int query(int node, int nl, int nr, int l, int r) {
    if (r < nl || nr < l) return NEUTRAL;        // disjoint
    if (l <= nl && nr <= r) return tree[node];   // fully covered
    int mid = nl + (nr - nl) / 2;
    return merge(query(2*node,   nl,      mid, l, r),
                 query(2*node+1, mid + 1, nr,  l, r));
}
// Static data with no updates? Prefix sums, O(1) query.

Answer

Dynamic programming applies when a problem has optimal substructure, meaning the optimal answer is built from optimal answers to subproblems, and overlapping subproblems, meaning the same subproblem is solved repeatedly by naive recursion. Fibonacci is the minimal example: the naive recursion is O(2^n) because fib(n minus 2) is recomputed exponentially often, while caching makes it O(n). If subproblems do not overlap, as in merge sort, you have divide and conquer, not dynamic programming, and saying that distinction unprompted is a strong signal.

Memoisation is top down: write the natural recursion and store each result in a map or array keyed by state. It is easy to derive from a brute force, it only computes states you actually reach, and it costs recursion stack space, so deep states risk overflow. Tabulation is bottom up: fill a table in dependency order with loops.

It avoids the stack entirely, is usually faster by constant factors, and allows space optimisation by keeping only the last row or two, but you must work out the correct iteration order yourself. In an interview, write the recursion, add memoisation, then convert to tabulation only if asked, because that sequence shows your derivation rather than a memorised table. The critical communication skill is stating the state definition explicitly before writing code.

Say "let dp[i][j] be the minimum number of coins to make amount j using the first i coin types", then the transition, then the base cases, then the answer cell. Coin change is a clean example: dp[amount] is the fewest coins to make that amount, dp[0] is 0, and dp[a] is one plus the minimum over each coin of dp[a minus coin], giving O(amount * coins) time. Interviewers reject candidates who write correct dynamic programming they cannot explain, because it reads as memorisation.

// Memoisation, top down: O(n) time, O(n) space + recursion
int coinsMemo(int amount, int[] coins, Integer[] memo) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] != null) return memo[amount];
    int best = Integer.MAX_VALUE;
    for (int c : coins) {
        int sub = coinsMemo(amount - c, coins, memo);
        if (sub >= 0) best = Math.min(best, sub + 1);
    }
    memo[amount] = (best == Integer.MAX_VALUE) ? -1 : best;
    return memo[amount];
}

// Tabulation, bottom up: O(amount * coins), no recursion stack
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);        // sentinel for unreachable
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
// state: dp[a] = fewest coins to make amount a

Answer

0/1 knapsack: given items with weights and values and a capacity W, maximise total value with each item usable at most once. State it as dp[i][w] equals the best value achievable using the first i items with capacity w. The transition is a binary choice: skip item i, giving dp[i minus 1][w], or take it when its weight fits, giving value[i] plus dp[i minus 1][w minus weight[i]], and take the maximum.

Base cases are zero across the first row. Time is O(n * W) and space is O(n * W), which is pseudo polynomial, not polynomial, because W is a numeric value rather than an input length, and pointing that out is a genuine advanced signal. Space reduces to O(W) with a single row because each row depends only on the row above, but the inner loop must run from W down to the item weight.

Iterating upwards would reuse the same item multiple times within one row, which silently turns it into the unbounded knapsack, and that inversion is exactly the bug interviewers hunt for. Longest common subsequence: dp[i][j] is the length of the longest common subsequence of the first i characters of one string and the first j of the other. If the characters match, dp[i][j] is one plus dp[i minus 1][j minus 1], otherwise it is the maximum of dropping one character from either string.

That is O(m * n) time and space, again reducible to two rows of O(min(m, n)). LCS is the engine behind diff tools and git, and its cousins are edit distance, longest palindromic subsequence, which is LCS of the string with its reverse, and shortest common supersequence. If asked to reconstruct the actual subsequence rather than its length, keep the full table and backtrack from the bottom right corner.

// 0/1 knapsack, O(n * W) time, O(W) space
int knapsack(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < wt.length; i++) {
        // MUST go downward, else the item is reused (unbounded)
        for (int w = W; w >= wt[i]; w -= 1) {
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}
// state: dp[w] = best value with capacity w using items seen so far

// LCS, O(m * n) time and space
int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}