Data Structures Interview Questions (2026): Must-Know Q&A

An array stores its elements in one contiguous block of memory, so the address of any index is just base_address + index * element_size, a single calculation with no scanning involved. Insertion at the front is a different problem: every existing element has to shift one slot to the right to make room, which touches all n elements in the worst case.

Count the characters in one string, then walk the second string decrementing those same counts, and confirm every count lands back at zero. A dict, or in Python collections.Counter, handles both ASCII and Unicode in the same O(n) pass, since it never assumes anything about the size of the alphabet. The fixed 26-slot array some prep material teaches only works for lowercase English letters; it breaks or has to grow for accented characters or emoji, so Counter is the safer default unless the interviewer has explicitly scoped the input to lowercase ASCII.

Two pointers, one at each end, closing toward the middle. At each step, skip past any character that isn't alphanumeric on either side before comparing, and lowercase both before checking equality. The moment the pointers meet or cross without a mismatch, it's a palindrome; any mismatch along the way ends it immediately. Building a cleaned-up copy of the string first works too, but it costs O(n) extra space; the two-pointer version reads directly off the original string and needs none.

An array gives you O(1) random access by index and better cache locality, since the data sits contiguously and the CPU can prefetch it. A singly linked list gives up random access entirely, finding the 500th element means walking 500 pointers, in exchange for O(1) insertion or deletion once you already have a reference to the right node, no shifting required.

The list also costs more memory per element: each node needs a pointer to the next node on top of the actual value, real overhead once you're storing something as small as an int.

Iteratively, keep three pointers as you walk the list once: prev starts at None, curr starts at head. At each step, save curr.next before overwriting it, point curr.next back at prev, then advance both prev and curr forward. Once curr runs out, prev is sitting at the new head.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

The recursive version is shorter to write but easy to get backwards under pressure: reverse everything after the head first, then fix the head's own two pointers last. reverse_list(head.next) returns the new head of the already-reversed rest of the list, head.next.next = head is the line that actually flips the link, and head.next = None keeps the old head from pointing at itself once it becomes the new tail. Both run in O(n) time; the iterative version uses O(1) space, the recursive one O(n) for the call stack.

A stack is LIFO, last in first out, push and pop both happen at the same end. A queue is FIFO, first in first out, you enqueue at one end and dequeue from the other. A deque, a double-ended queue, supports O(1) push and pop at both ends, a strict superset of both: you can use one to implement a stack, a queue, or a sliding window. Python's collections.deque is what most people reach for instead of a plain list once popping from the front matters, since list.pop(0) is O(n).

Push every opening bracket onto a stack as you scan left to right. The moment you hit a closing bracket, it has to match whatever's currently on top of the stack, since brackets close in the reverse order they opened, exactly what a stack's LIFO behavior gives you for free. A mismatch, or a closing bracket with nothing left on the stack, means invalid; an empty stack at the very end means every bracket found its match.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

O(n) time, O(n) space in the worst case of an all-opening-brackets string. This is also one of the cleanest examples of why a stack exists at all: the problem is fundamentally about matching things in reverse order, and a stack is the structure built exactly for that.

The O(1) part assumes a good hash function spreads keys evenly across buckets and the table isn't too full. Worst case, if every key happens to hash into the same bucket, a lookup degrades to scanning a list of n items, O(n). Java's HashMap actually hedges against this directly: since Java 8, once a single bucket collects more than 8 entries and the table itself is at least 64 slots, that bucket converts from a linked list into a small red-black tree, capping the true worst case at O(log n) instead of O(n) for that bucket.

This is probably the single most-asked interview question in any language, and the reason it's still asked is that the naive answer, check every pair, is O(n^2) and almost everyone's first instinct. A hash map flips it to O(n): walk the array once, and before inserting the current number, check whether target minus the current number is already a key in the map. If it is, you've found the pair; if not, insert the current number and keep going.

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

One pass, O(n) time, O(n) space for the map. Worth contrasting with the sorted-array, two-pointer version further down this page: that one gets you O(1) extra space instead of O(n), but only because it assumes the array is already sorted and doesn't need to return original indices. Which one an interviewer wants usually comes down to whether the input is sorted and whether the original indices matter, not which technique is objectively better.

A binary tree just means every node has at most two children, no ordering rule attached. A binary search tree adds one invariant on top: for every node, everything in its left subtree is smaller, everything in its right subtree is larger. That single rule is what makes search, insert, and delete all O(h), where h is the tree's height, instead of requiring a full scan.

This is breadth-first search on a tree, and it's the one traversal that needs a queue instead of recursion, since preorder, inorder, and postorder all naturally fall out of a recursive call stack but level order doesn't. Push the root onto a queue, then repeatedly pop a node, record its value, and push its children, left first, then right, onto the back of the queue. Processing one full level before any node from the next level enters the output is exactly what a FIFO queue gives you for free.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

The inner for loop over len(queue), captured before the loop starts mutating the queue, is what separates the levels from each other in the output instead of returning one flat list. O(n) time and space either way, since every node gets visited and queued exactly once.

The depth of a tree is 1 plus the larger of its two subtrees' depths, and an empty tree has depth 0, which is the whole algorithm in one sentence: max_depth(node) is 0 for a null node, otherwise 1 + max(max_depth(node.left), max_depth(node.right)). It's a three-line recursive function, and the most common way candidates overcomplicate it is reaching straight for an iterative BFS with a level counter when the recursive version is shorter, just as correct, and exactly what most interviewers expect as the first answer before asking for the iterative version as a follow-up.

A heap only guarantees an order between a parent and its own children, min-heap: parent less than or equal to both children, not any relationship between siblings or across the whole tree the way a BST orders everything. That weaker guarantee is exactly what makes peek O(1) and insert or extract O(log n), and it's also why a heap can't do an in-order traversal to get sorted output the way a BST can.

Heaps are also usually array-backed rather than pointer-backed. The complete-tree shape means a node at index i has children at 2i+1 and 2i+2, no actual pointers needed, more cache-friendly than chasing node references the way a BST does.

Prefix queries. A hash set can tell you instantly whether "cat" is a member, but it can't efficiently tell you every stored word that starts with "ca" without scanning the whole set. A trie stores strings character by character down shared paths, so every word sharing the prefix "ca" lives under the same branch, and finding all of them means walking one subtree instead of checking every entry.

An adjacency list stores, for each vertex, only the vertices it actually connects to, O(V + E) total space, the right default for sparse graphs, a social graph, a road network, where most vertices aren't directly connected to most others. An adjacency matrix stores a V by V grid marking every possible edge, O(V^2) space regardless of how many edges actually exist, but it buys O(1) "are these two vertices connected" checks instead of scanning a list.

Dense graphs, or ones where you're constantly asking whether an edge exists between two specific vertices rather than what a vertex connects to, lean toward a matrix. Most real-world graphs are sparse, which is why an adjacency list is the more common default.

It means the average cost per operation, spread across a long sequence of operations, is O(1), even though any single operation in that sequence might individually cost more. A dynamic array append is the textbook case: most appends are O(1) because there's room, but every so often one append triggers a full resize and copy, O(n) for that one call. Average the occasional expensive call across all the cheap ones before it and the amortized cost per append comes out to O(1). It's a claim about a sequence, not a guarantee about any single call.

Growing by a fixed amount would make a full sequence of appends cost O(n^2) overall, because filling n slots one at a time would need roughly n separate reallocations and copies. Growing by a multiplicative factor instead keeps that amortized to O(1) per append: CPython over-allocates by roughly one-eighth of the current size plus a small constant, and Java's ArrayList grows by 1.5x, oldCapacity plus oldCapacity right-shifted by one, straight from the source. Different factors, same underlying trick.

Kadane's algorithm keeps a running sum and resets it the moment it would drag the total below the value of the current element alone, since a bad enough running total can only hurt whatever comes after it. Track two numbers in one pass: current_sum, the best sum ending exactly at this index, and best_sum, the best seen anywhere so far. At each element, current_sum becomes max(element, current_sum + element).

def max_subarray(nums):
    current_sum = best_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        best_sum = max(best_sum, current_sum)
    return best_sum

The brute-force answer checks every possible subarray, O(n^2) or worse if you recompute each sum from scratch instead of reusing the previous one. Kadane's does the whole problem in one pass and O(1) extra space, and the same reset logic generalizes to maximum product subarray and maximum sum circular subarray, both with a small extra twist on top.

Start with the widest possible container, one pointer at index 0 and the other at the last index, since width is the one dimension guaranteed to shrink on every later move. The area at any step is capped by the shorter of the two lines, so move whichever pointer sits at the shorter line inward. Moving the taller line's pointer can only lose width with no chance of finding anything taller, since the shorter line was already the bottleneck; moving the shorter line's pointer is the only move that has any chance of replacing it with something better.

def max_area(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        width = right - left
        best = max(best, width * min(heights[left], heights[right]))
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

That greedy move is the part candidates usually can't justify on the spot. It works because you're never discarding a container that could have beaten the current best, only ones the shorter line already proved can't.

Division would make this trivial, multiply everything once and divide out each element, but it breaks the moment a zero shows up, and interviewers ask this question specifically to rule that shortcut out. The O(n), no-division answer runs two passes: build a running prefix product as you walk left to right, then walk back to right to left multiplying in a running suffix product, so the output ends up holding prefix times suffix for every index without a third array.

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Two passes, O(1) extra space if you don't count the output array, since the running prefix and suffix are just single variables. A naive version computing prefix and suffix as two separate arrays still works and is still O(n) time, it just costs O(n) extra space the running-variable version avoids.

A doubly linked list adds a prev pointer to every node, which buys O(1) removal of a node you already have a reference to (no need to walk from the head to find its predecessor) and O(1) traversal backward. That's exactly why an LRU cache is almost always built on a doubly linked list plus a hash map: evicting the least-recently-used node and moving a node to the front both become O(1).

The cost is one extra pointer per node, which on a 64-bit system is another 8 bytes just for bookkeeping, plus slightly more code to keep both pointers consistent on every insert and delete.

A dummy head node makes the pointer bookkeeping simpler, since it removes the special case of deciding which list's node becomes the very first node of the result. Walk both lists with two pointers, at each step attaching whichever current node is smaller onto the tail of the result and advancing only that list's pointer. Once one list runs out, attach whatever's left of the other list wholesale, since it's already sorted.

def merge_two_lists(l1, l2):
    dummy = tail = ListNode()
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

It's O(n + m) time for lists of length n and m, and O(1) extra space beyond the dummy node, since every node gets relinked in place rather than copied. This is the same building block the merge step of merge sort on linked lists reuses, and a smaller version of the k-list heap merge covered later on this page.

Two pointers, offset by n nodes. Advance a fast pointer n steps ahead first, then move both fast and a slow pointer forward together, one step at a time. By the time fast reaches the end of the list, slow is sitting exactly n nodes behind it, at the node right before the one that needs removing. A dummy node ahead of the head keeps the edge case of removing the head itself from needing separate handling.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

One pass, O(n) time, O(1) space, and the dummy node is what makes "remove the last node" and "remove the head" the same code path instead of a special case. The two-pass version, count the length first, then walk to length minus n, works too and is arguably easier to reason about first; the interviewer is usually listening for whether you can spot the fixed-gap two-pointer trick without being told to look for it.

Keep an "in" stack for pushes and an "out" stack for pops. Enqueue just pushes onto "in". Dequeue pops from "out" if it has anything in it; if "out" is empty, dump everything from "in" onto "out" first, which reverses the order so the oldest element ends up on top, then pop.

class QueueFromStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def enqueue(self, x):
        self.stack_in.append(x)

    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

Each element only ever moves from "in" to "out" once in its lifetime, so even though a single dequeue call can occasionally cost O(n) if "out" is empty, the amortized cost across n operations works out to O(1) per call.

Chaining stores a small list, or in Java's case sometimes a tree, at each bucket, and a collision just means two keys share a bucket and both live in it. Open addressing instead finds a different slot for the colliding key using a probe sequence, linear, quadratic, or double hashing, and keeps looking until it finds an empty one.

Here's a detail a lot of prep material gets backwards: Python's dict doesn't use chaining. It uses open addressing with a pseudo-random probing sequence, more cache-friendly since everything stays in one contiguous table instead of scattered linked nodes. Java's HashMap does use chaining. Same problem, two mainstream languages, two different answers, and interviewers who've actually read the source will notice if you assume every hash table works the same way underneath.

It depends which one, and this is a case where the classic CS-textbook answer, "no, hash tables have no defined order," is now wrong for at least one mainstream language. Since Python 3.7, dict preserves insertion order as a language guarantee, not just an implementation quirk you shouldn't rely on. Java's HashMap still makes no such promise; if you need insertion order in Java, you reach for LinkedHashMap instead, a real, separate class built for exactly that.

Every anagram shares the same multiset of characters, so sorting each string's characters produces an identical key for every member of the same group, a five-character string sorted always produces the same five characters in the same order regardless of which anagram it started as. Use that sorted string as a dict key and append each original string to the list stored under it; whatever ends up grouped under the same key is the answer.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Sorting each string costs O(k log k) for a string of length k, so the whole pass is O(n * k log k) across n strings. A character-count tuple as the key instead of a sorted string drops that to O(n * k), since counting characters is linear and doesn't need a sort, a small optimization that matters more once k gets large.

Sorted input gives the tree no reason to branch. Each new value is always larger than everything already inserted, so it always becomes the right child of the previous node, and the "tree" ends up as a straight line, functionally a linked list wearing a tree's name, with height n instead of log n.

Self-balancing trees, AVL, red-black, fix this by enforcing a balance constraint after every insert and delete, using rotations to keep height bounded at O(log n) regardless of insertion order. Without that constraint, a plain BST's performance depends entirely on luck.

Do it bottom-up in one pass instead of computing height separately for every node, which would be O(n^2) on a skewed tree. Return -1 the moment any subtree is found unbalanced and let that short-circuit propagate up instead of continuing to compute heights nobody needs anymore.

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1

    return check(root) != -1

The BST invariant isn't local, it's global: every node in a left subtree has to be smaller than the node above it, not just smaller than its own immediate parent. A tree where a node's left child is smaller and right child is larger can still be invalid if a grandchild two levels down the right subtree happens to be smaller than the root; comparing only parent to child would miss that entirely. The correct approach carries a valid range, a lower and upper bound, down through the recursion, narrowing it at every step: going left tightens the upper bound to the current node's value, going right tightens the lower bound.

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

An inorder traversal that checks the output comes out strictly increasing works too and is arguably more intuitive, since a BST's inorder traversal visiting nodes in sorted order is the definition of the structure. Both run in O(n) time and O(h) space for the recursion stack; the bounds-passing version avoids building the full inorder list in memory if you only care about a true or false answer.

In a plain binary tree, finding the LCA needs a full traversal since there's no ordering to exploit, checking every node for whether both targets fall somewhere in its subtrees. A BST's ordering rule turns that into a single directed walk from the root: at each node, if both target values are smaller, the LCA has to be somewhere in the left subtree, so go left; if both are larger, go right; the moment the current node sits between the two targets, or equals one of them, that node is the LCA, and the search stops.

def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node
    return None

O(h) time, where h is the tree's height, no recursion stack needed at all since it's a straight-line walk down from the root. That single ordering property is why this version runs in O(h) instead of the O(n) a general binary tree LCA needs; it's a good example of an interviewer testing whether you actually understand what a BST's invariant buys you, not just whether you can traverse a tree.

Each node holds a dict of child characters to child nodes, plus a flag marking whether a complete word ends there, since "car" being a valid word doesn't mean every prefix of it, "c", "ca", is also a complete word on its own.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

Both operations run in O(m), where m is the length of the word being inserted or searched, independent of how many other words the trie already holds. The trade-off is memory: a dict-of-children node is more compact than a fixed 26-slot array for lowercase-only tries, but neither is free once you're storing millions of words, which is why production autocomplete systems often compress tries further, a radix tree or a DAWG, collapsing single-child chains into one edge.

BFS explores level by level, visiting every vertex at distance 1 before any vertex at distance 2, so the first time it reaches a target vertex, that's guaranteed to be by the shortest possible number of edges. DFS commits to one path and follows it as deep as it goes before backtracking, so it can absolutely find a path to the target, just not necessarily the shortest one, since it never compares path lengths against each other the way BFS's level-by-level structure does automatically.

Kahn's algorithm builds the order from the outside in: compute the in-degree, the number of incoming edges, for every vertex, then repeatedly pull out any vertex with in-degree zero, since it has no unmet prerequisite left, append it to the result, and decrement the in-degree of everything it pointed to. A vertex whose in-degree just dropped to zero becomes eligible and joins the queue.

from collections import deque

def topological_sort(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    in_degree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_courses else []

If the graph has a cycle, some subset of vertices never reaches in-degree zero, since each one in the cycle is always waiting on another vertex in that same cycle, and the algorithm stalls out with vertices still left unprocessed. Checking len(order) == num_courses at the end is exactly how this same function doubles as a cycle detector for a directed graph, no separate coloring pass needed the way the DFS-based cycle check earlier on this page uses.

Each element has exactly two states, in the subset or not, so building every subset means walking a decision tree of depth n where every node branches in two directions. Backtracking makes that explicit: at each index, first recurse having included the current element in the running subset, then undo that choice and recurse again having excluded it, adding a copy of the running subset to the result at every node of that tree, not just the leaves.

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

There are exactly 2^n subsets of an n-element set, so the result size alone puts a floor of O(2^n) on the runtime no matter how the code is written; the backtracking version hits that bound without doing extra wasted work. The current.pop() line after the recursive call is the actual "backtrack" step, undoing the choice so the next iteration of the loop starts from a clean slate instead of carrying the previous branch's element along.

Track two counts as you build a string one character at a time: how many open parentheses have been placed and how many close parentheses have been placed. Add an open paren any time you've placed fewer than n of them; add a close paren only when the number of close parens placed so far is still less than the number of opens, since a close paren can never legally outnumber the opens that came before it in a valid sequence.

def generate_parentheses(n):
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

That close_count < open_count check is the entire pruning logic, and it's what keeps this from generating invalid strings and filtering them out afterward, the approach some candidates reach for first. Pruning invalid branches as early as possible, rather than generating everything and checking validity after the fact, is the general principle behind every backtracking problem on this page, not just this one.

A rotated sorted array still has one useful property at every step of a binary search: at least one of the two halves, split at the midpoint, is guaranteed to still be in normal sorted order, even though the array as a whole isn't. Check which half is sorted by comparing the midpoint against the left endpoint, then check whether the target falls inside that sorted half's range. If it does, search there; if not, the target has to be in the other half, rotated or not.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Still O(log n), same as a plain binary search, since every step still eliminates half the remaining search space, it just needs one extra comparison up front to figure out which half is safe to reason about normally. The version with duplicate values allowed is the harder follow-up: when nums[left] == nums[mid], you can't tell which half is sorted anymore, and the only safe move is shrinking the search by one from the left, which degrades the worst case to O(n).

Quicksort partitions in place around a pivot and recurses on both sides, average O(n log n), but a poor pivot choice, already-sorted input against a naive first-element pivot, degrades it to O(n^2). Merge sort splits down the middle regardless of the data's order and merges back up, a guaranteed O(n log n) no matter what the input looks like, at the cost of O(n) extra space for the merge step that quicksort's in-place partitioning doesn't need.

Stability is the other deciding factor people forget to mention: merge sort is stable, equal elements keep their original relative order, which matters when you're sorting objects by one field but want ties to preserve an earlier sort by a different field. Quicksort isn't stable unless you specifically engineer it to be. That's why Python's sort and Java's Arrays.sort for objects both use variants of merge sort, Timsort in Python's case, under the hood, while quicksort's better cache behavior and lack of extra allocation is exactly why it's still the default for sorting primitive arrays in Java, where stability doesn't matter since primitives don't carry any identity beyond their value.

Here's the version worth having memorized cold, average-case complexity unless noted otherwise:

complexity = {
    "array: indexed access":         "O(1)",
    "array: search, unsorted":       "O(n)",
    "array: insert/delete at end":   "O(1) amortized",
    "array: insert/delete at front": "O(n)",
    "linked list: search":           "O(n)",
    "linked list: insert at head":   "O(1)",
    "hash table: get/set, average":  "O(1)",
    "hash table: get/set, worst":    "O(n)",
    "BST, balanced: search":         "O(log n)",
    "BST, unbalanced: search":       "O(n) worst case",
    "heap: push/pop":                "O(log n)",
    "heap: peek min or max":         "O(1)",
    "heap: build from array":        "O(n)",
    "trie: search, key length m":    "O(m)",
    "BFS/DFS: full graph traversal": "O(V + E)",
}

The one people get wrong most often: building a heap from an existing array of n elements is O(n), not O(n log n). It looks like it should be n calls to an O(log n) sift-down, but most nodes in a complete tree sit near the bottom and only sift a short distance, so the total work across the whole array sums to a linear bound, not n log n.

A min-heap capped at size 10. Keep the 10 current leaders in the heap with the smallest of them at the top; for every new score, compare it against that minimum, and only push and pop if the new score actually beats the current 10th place. That's O(log 10), a constant in practice, per update.

A sorted array of the top 10 would need a shift on every insertion to keep it sorted, still small since it's bounded at 10, but a heap gets you there with less bookkeeping. A full BST is overkill here; you don't need a strict global order over the top 10, only the current minimum among them.

Whether you need ordering. A hash map gives you O(1) average get and put with no guarantee about iteration order, unless it's specifically Python's dict, which does preserve insertion order. A tree-based map trades that O(1) for O(log n), but in exchange you get sorted iteration, and range queries, floor and ceiling lookups, "give me every key between X and Y," that a hash map simply can't answer without scanning everything.

If nobody's ever going to ask what's just below a given key or want the results in sorted order, a hash map wins on speed and there's no reason to pay for ordering you won't use.

Two pointers, one starting at each end. If the sum at the two pointers is too small, move the left pointer right to increase it; too large, move the right pointer left to decrease it; exact match, done. It works specifically because the array is sorted, moving either pointer moves the sum in a predictable direction, which is what makes the O(n) single pass possible.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

A sliding window with a dict that stores the last index seen for each character, which lets the left edge jump straight past a duplicate instead of inching forward one step at a time. Expand the right edge of the window; the moment you hit a character already inside it, jump the left edge past that duplicate, and track the widest window seen along the way.

def longest_unique_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

A plain set instead of a dict also works and is still O(n), but it can only tell you a character is a duplicate, not where, so the left pointer has to creep forward one position at a time until the duplicate falls out of the window. Same Big-O, noticeably smaller constant factor with the dict version, and that distinction is exactly what separates a working answer from one that shows real fluency.

A single stack can't answer getMin in O(1) on its own, since the minimum could be buried anywhere below the top and finding it means scanning down. Keep a second stack alongside the main one that tracks the minimum seen so far at each point in the main stack's history. Every push also pushes the smaller of the new value and the current minimum onto the min-stack; every pop pops both stacks together, so the min-stack's top always reflects the correct minimum for whatever's left in the main stack after the pop.

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

    def push(self, val):
        self.stack.append(val)
        current_min = min(val, self.min_stack[-1]) if self.min_stack else val
        self.min_stack.append(current_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]

Every operation stays O(1), at the cost of doubling the memory to O(n) for the second stack. A cheaper variant only pushes onto the min-stack when the new value is a new minimum or a tie, instead of on every push, which trims the memory overhead in the common case where the minimum doesn't change often, at the cost of slightly trickier pop logic to know when to pop the min-stack too.

Strings are immutable in both Python and Java, so s = s + "x" doesn't modify s in place. It allocates an entirely new string, copies the old contents plus the addition into it, and rebinds s to point at the new object. Do that 10,000 times and you're copying an ever-growing string on every iteration, O(n^2) total work for what looks like a simple loop.

The fix is the same idea in both languages: accumulate into a mutable structure and join once at the end. In Python, append to a list and call "".join(pieces). In Java, use a StringBuilder and call .toString() once. Interviewers ask this specifically because it's a real bug that ships in production code, not a trick invented for interviews.

Scanning every window from scratch costs O(n*k), fine for small k but not for the million-element, thousand-wide windows some systems monitor in real time. A monotonic deque gets it down to O(n) total: keep indices in decreasing order of their values, so the front of the deque is always the current window's maximum. Before adding a new index, pop off the back anything smaller than the new value, since those popped elements can never be the maximum of any future window once a larger, later element has outlived them. Pop from the front whenever the index there has aged out of the window.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()  # stores indices, values decreasing
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Every index enters and leaves the deque at most once, which is what keeps the total work O(n) instead of O(n*k) even with a while loop nested inside the for loop. It's a common spot where candidates assume nested loops mean quadratic time without checking whether the inner loop's total work across the whole run is actually bounded.

Floyd's cycle detection, the tortoise and hare. Two pointers walk the list at different speeds; if there's a cycle, the faster one eventually laps the slower one and they meet inside the loop. No cycle, and the fast pointer just hits the end.

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

It runs in O(n) time and O(1) space, which is the whole point of asking it instead of the obvious O(n) space answer, dropping every visited node into a hash set and checking for a repeat. Interviewers usually follow up by asking you to find where the cycle starts, not just whether one exists, which needs a second pass from the head after the first meeting point.

Load factor is roughly the number of stored items divided by the table size. Once it crosses a threshold, Java's HashMap defaults to 0.75, the table resizes: allocate a bigger array, then re-hash and re-insert every existing key into it, an O(n) operation on the day it happens. But that expensive resize only happens once every time the table roughly doubles, so spread across the sequence of inserts that led up to it, the extra cost per insert averages out to a small constant, the same amortized argument as dynamic array growth.

I don't have the exact crossover point memorized for every language runtime, and it genuinely differs across them, but the shape of the answer is universal: a rare expensive operation, paid for by many cheap ones before it, averages out to cheap.

AVL trees enforce a stricter balance factor, the heights of a node's two subtrees can differ by at most 1, which keeps lookups slightly faster since the tree stays closer to perfectly balanced. Red-black trees allow a looser bound, roughly twice the height of an optimal tree, in exchange for cheaper writes: a red-black insert needs at most 2 rotations to restore balance and a delete needs at most 3, both constant, while an AVL delete can cascade rebalancing all the way up to the root.

That's why red-black trees show up more often in general-purpose library code. Java's TreeMap, C++'s std::map, and several structures inside the Linux kernel itself all use one, where writes happen constantly and a strict AVL balance isn't worth the extra rotation cost. AVL trees still win when you're doing far more reads than writes and every bit of lookup speed matters.

Sorting the whole array and indexing in works, but it's O(n log n) for information you don't need, the full order of everything else. A min-heap capped at size k does better: push the first k elements, then for every remaining element, push it and pop the smallest if the heap now exceeds size k. Whatever survives at the end is the kth largest.

public int kthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap by default
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
}

Worth saying out loud in the interview: Java's PriorityQueue is a min-heap by default, so capping it at size k and popping the smallest whenever it overflows is what gives you the kth largest sitting at the top when you're done, not the other way around. That's O(n log k), a real win over O(n log n) once k is small relative to n. Quickselect gets you to average O(n) instead, worse worst-case at O(n^2), so it's a fair follow-up to ask which one you'd actually pick and why: heap if you need it to stay correct under adversarial input, quickselect if average-case speed matters more and you trust the input isn't hostile.

Track three states per vertex during DFS instead of the usual visited or unvisited: white (never touched), gray (currently on the recursion stack), black (fully explored, done). A cycle exists if DFS ever hits an edge pointing to a gray vertex, a back edge into a node that's still an ancestor in the current traversal path, not just any previously-visited node.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}

    def dfs(v):
        color[v] = GRAY
        for neighbor in graph[v]:
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[v] = BLACK
        return False

    return any(color[v] == WHITE and dfs(v) for v in graph)

This is a common spot for candidates to mix up directed and undirected logic. In an undirected graph, a simple visited-set DFS that just skips the vertex you came from is enough, revisiting any other already-visited neighbor means a cycle. Apply that same simpler check to a directed graph and it produces false positives, since a directed graph can perfectly legitimately have two separate edges pointing into the same vertex without any cycle at all.

Dijkstra's is a greedy algorithm built on a min-heap: keep a running best-known distance to every vertex, start the source at 0 and everything else at infinity, and repeatedly pull the vertex with the smallest known distance off the heap. For each of that vertex's neighbors, check whether reaching them through the current vertex beats whatever distance they already had recorded, and if so, update it and push the improved distance onto the heap.

import heapq

def dijkstra(graph, source):
    distances = {v: float("inf") for v in graph}
    distances[source] = 0
    heap = [(0, source)]
    while heap:
        dist, node = heapq.heappop(heap)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return distances

The if dist > distances[node]: continue line is the part that trips people up, since the heap can hold multiple stale entries for the same vertex from earlier, worse updates; skipping them instead of removing them from the heap is simpler than implementing a decrease-key operation. Runs in O((V + E) log V) with a binary heap. It only works because edge weights are non-negative; a negative edge can invalidate an already-finalized shortest distance, which is exactly the gap Bellman-Ford exists to cover instead.

Big-O describes growth as input size approaches infinity, so it deliberately drops constant factors and lower-order terms, an algorithm that does 5n operations and one that does 500n operations are both O(n). That's the right abstraction for reasoning about scale, but it hides real differences at the input sizes you actually hit in practice.

A linear scan through a small array can beat a hash table lookup on the same data, because computing a hash and following pointers around a scattered table has real constant overhead that a tight, cache-friendly loop over contiguous memory doesn't. I don't have a clean crossover point to give you, it depends on the hash function, the cache size, and the language runtime, but the fact that it exists is exactly the kind of thing a strong candidate mentions unprompted instead of treating Big-O as the whole answer.

Push the head of each of the k lists into a min-heap, keyed by value. Pop the smallest, append it to the result, and if the node you just popped has a next, push that node into the heap too. Repeat until the heap is empty.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

With N total nodes across all k lists, this runs in O(N log k), since the heap never holds more than k elements at once and every one of the N nodes gets pushed and popped exactly once. Merging the lists pairwise as a divide-and-conquer tournament (merge list 1 with list 2, list 3 with list 4, then merge those results together, and so on) lands at the same O(N log k). Merging them one after another in sequence instead, list 1 into 2, that result into 3, degrades to O(N * k), a common mistake when candidates reach for pairwise merging without thinking about the order.

Split the data across two heaps instead of keeping one sorted structure. A max-heap holds the smaller half of the numbers seen so far, a min-heap holds the larger half, and the two are kept balanced in size, differing by at most one element. The median is either the max-heap's top on its own, when it holds one more element than the min-heap, or the average of both heaps' tops when the two are exactly equal in size.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap, stored as negatives
        self.large = []  # min-heap

    def add_num(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Python's heapq only implements a min-heap, so the max-heap side is faked by negating every value going in and out, a trick worth naming explicitly since it's not obvious from the code alone. add_num runs in O(log n), find_median in O(1), which beats keeping the whole stream in one sorted list and re-sorting or re-inserting on every add.