Coding Interview Questions & Patterns
The coding interview rewards pattern recognition, not memorization. Learn the core patterns — two pointers, sliding window, BFS/DFS, dynamic programming — and the questions become familiar.
Interview questions & answers
Given a solution, how do you state its time and space complexity, and what mistakes do interviewers watch for?
Report the dominant growth term for time and the extra memory for space, dropping constants and lower-order terms. Count the recursion stack as space (O(depth)) even when nothing is allocated. Use distinct variables when inputs differ (O(V + E), O(a + b)) instead of collapsing everything into n. Distinguish average vs worst case (hash lookup is O(1) average, O(n) worst).
Find two numbers in an array that sum to a target. Walk through both the sorted and unsorted approaches.
Unsorted: one pass with a hash map from value to index; for each num, check if target - num was seen — O(n) time, O(n) space. Sorted: converging two pointers from both ends, moving in based on the sum — O(n) time, O(1) space. Check the complement before inserting so an element does not match itself.
Find the length of the longest substring without repeating characters.
Sliding window with a set of the window's characters. Advance right; while the new char is already in the set, remove s[left] and increment left. Track the max window width. Each character enters and leaves once, so O(n) time.
Count the number of subarrays whose elements sum to exactly k.
Use a prefix sum: a subarray sums to k when prefix[j] - prefix[i] == k. Sweep left to right with a hash map of prefix-sum counts seen so far. At each index add the count of prefix - k, then record the current prefix — O(n) time. Seed the map with {c}{0: 1}{/c} (the empty prefix) or every subarray starting at index 0 is missed — the classic bug here.
Group a list of strings into anagrams.
For each string build a canonical key: the sorted string, or a 26-length count tuple. Use a hash map from key to list of originals; anagrams collide into the same bucket. Sorted key is O(n * k log k); count-tuple key is O(n * k) for strings of length k.
Detect whether a linked list has a cycle, and find where the cycle begins.
Floyd's fast/slow: advance slow +1 and fast +2; if they meet there is a cycle — O(1) space. To find the start: after they meet, reset one pointer to the head and advance both by 1; they meet at the cycle entrance. Alternative: a visited set of nodes, but that costs O(n) space.
Given daily temperatures, for each day find how many days until a warmer temperature.
Use a monotonic decreasing stack of indices. For each day, while the current temperature exceeds the temperature at the stack's top index, pop and record the day difference as its answer. Push the current index. Each index is pushed/popped once — O(n) time.
Validate whether a binary tree is a valid binary search tree.
Inorder traversal of a BST must be strictly increasing — check each value exceeds the previous. Or recurse with (low, high) bounds: every node must lie in its allowed open interval, tightening bounds as you descend. Both are O(n); watch for duplicate-value and integer-boundary edge cases.
Determine whether you can finish all courses given prerequisite pairs (course schedule).
Model courses as a directed graph; a valid schedule exists iff the graph is a DAG (no cycle). Run topological sort (Kahn's): repeatedly remove in-degree-0 nodes. If you cannot remove all nodes, a cycle exists and it is impossible — O(V + E).
Count the number of islands in a 2-D grid of land and water.
Treat the grid as a graph: each land cell is a node, adjacent land cells are edges. Scan every cell; when you hit unvisited land, BFS/DFS to flood the whole island and mark it visited, then increment the count. Each cell is visited once — O(rows * cols). Union-find is an alternative.
Coin change: fewest coins to make a target amount from given denominations.
DP over amounts: dp[a] = fewest coins to make amount a, initialized to infinity, dp[0] = 0. For each amount, try every coin: dp[a] = min(dp[a], dp[a - coin] + 1). Answer is dp[target] (or -1 if unreachable) — O(amount * coins) time.
Find the k largest elements of a large array. Compare your options.
Size-k min-heap: push each element, pop the smallest when size exceeds k — O(n log k) time, O(k) space. Sorting: O(n log n) — simpler but wasteful when k << n. Quickselect: O(n) average if you do not need them sorted. Pick based on k vs n and whether output must be ordered.
Merge a list of possibly overlapping intervals into the minimal set of disjoint intervals.
Sort by start, then sweep left to right. If the current start is <= the last merged end, extend the last interval with max of the ends; otherwise append a new interval. O(n log n) time from the sort, O(n) output. Clarify whether touching intervals ([1,2],[2,3]) count as overlapping.
Given meeting time intervals, compute the minimum number of conference rooms required.
Sort by start; keep a min-heap of end times for active meetings. For each meeting, if the earliest end <= its start, pop (that room frees up); then push its end time. The answer is the max heap size reached — O(n log n). Equivalent: sweep sorted starts vs sorted ends and track overlap count.
Find the contiguous subarray with the largest sum (maximum subarray).
Kadane's: one pass with cur = max(x, cur + x) — extend the running subarray or restart at x — and best = max(best, cur). O(n) time, O(1) space; initialize with the first element so all-negative arrays return the max element, not 0. The greedy/DP view: cur is the best subarray ending here — a one-state DP.
The interviewer gives you an AI assistant in the editor and says you may use it freely. How do you work to maximize your evaluation?
State the approach first: clarify constraints, name the pattern and target complexity out loud — the reasoning is what is scored. Use the assistant for boilerplate, not the core idea; you must own the algorithm choice. Review generated code like a PR: check its complexity against the constraints, trace a small example and the edge cases, and narrate the verification. When it is wrong, debug visibly — localize the bug with a trace rather than regenerating and hoping.