Coding Interview Problems

Coding Interview Problems

A coding interview problem is a small, self-contained puzzle you must solve out loud in 20–45 minutes: read a precise input specification, produce a correct output, and explain why your approach is fast enough. The trap is thinking the goal is "get the right answer." It is not. The interviewer already knows the answer. They are watching how you get there: how you clarify ambiguity, pick a data structure, trade time for space, and reason about the growth rate of your solution as the input gets large. Two candidates can both return the correct value and get opposite verdicts — one narrated a decision process, the other guessed until the tests passed.

Precise definition

A coding interview problem consists of four parts: (1) an input domain (types, sizes, ranges, whether values are sorted/unique/signed), (2) a required output and its exact format, (3) constraints — the killer detail, e.g. 1 ≤ n ≤ 105, which silently tells you the target complexity, and (4) an implicit resource budget in time and memory. Your job is to produce an algorithm whose worst-case running time, expressed in Big-O of the input size n, fits the budget, then implement it bug-free. "Fits the budget" is concrete: a modern machine does roughly 10⁸–10⁹ simple operations per second, so a constraint of n = 105 rules out an O(n²) = 10¹⁰ solution but welcomes O(n log n) ≈ 1.7×10⁶.

Reading the constraint backwards is the single most useful interview skill: the size of n is a coded hint for the intended algorithm class.

Reading constraints as a hint

• n ≤ 20 → exponential is fine: O(2ⁿ) subsets or O(n!) permutations, backtracking.
• n ≤ 500 → O(n³) accepted, e.g. Floyd-Warshall / 3 nested loops.
• n ≤ 5000 → O(n²) accepted, e.g. simple DP tables.
• n ≤ 105–106 → you must reach O(n log n) or O(n): sorting, hashing, two pointers, sliding window.
• n ≤ 109 or huge → O(log n) or O(1): binary search on the answer, or a closed-form formula.

Worked example: Two Sum, counted

Problem: given nums = [2, 7, 11, 15] and target = 9, return indices of the two numbers that sum to the target. Answer: [0, 1] because 2 + 7 = 9.

Brute force. Check every pair (i, j). For n=4 that is C(4,2)=6 pair checks; in general n(n−1)/2 → O(n²) time, O(1) space. At n=10⁵ that is ~5×10⁹ checks — several seconds, too slow.

Hash-map, one pass. Walk once; for each value x ask whether target − x was already seen in a hash map of value→index.

• i=0, x=2: need 7, map empty. Store {2:0}. (1 lookup)
• i=1, x=7: need 2, found at index 0 → return [0,1]. (1 lookup, done at step 2)

That is 2 lookups instead of 6. In the worst case (no answer until the end) it is n lookups, each O(1) average → O(n) time, O(n) space. We spent memory (the map) to erase a factor of n from time. That space-for-time trade is the heartbeat of interview problem-solving.

Pitfalls and what the interviewer is probing

• Jumping to code. Silence then typing signals no plan. First restate the problem, state assumptions, name a brute force, then optimize. Interviewers grade the narration.
• Not clarifying the input domain. Can values be negative? Duplicates? Is the array sorted? Empty input? Each answer can change the optimal algorithm. They are probing whether you defend against undefined behavior.
• Confusing average and worst case. Hash-map lookups are O(1) average but O(n) worst case under adversarial collisions; quicksort is O(n log n) average, O(n²) worst. Say which you mean.
• Ignoring space. An O(n) time, O(n) space answer may lose to an O(n) time, O(1) two-pointer answer. They probe whether you see the trade.
• Off-by-one and edge cases. Empty array, single element, all-equal, integer overflow. Dry-run your code on n=0 and n=1 out loud before claiming it works.

When it matters + trade-offs across complexity classes

The recurring decision is picking a point on the time–space curve that clears the constraint with margin. Neighbouring classes trade sharply:

• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Each jump changes the largest solvable n by orders of magnitude. Going from O(n²) to O(n log n) via sorting is the most common single win.
• Sorting first (O(n log n)) often unlocks two-pointer or binary-search steps, beating a hash approach when you also need order — but a hash map gives O(n) if you only need membership.
• Recursion vs DP. Naive recursion may be O(2ⁿ); memoizing overlapping subproblems collapses it to polynomial by spending O(states) memory.
• In real systems the same reasoning sizes indexes, batch jobs, and hot loops — the interview is a compressed rehearsal of the daily engineering question "will this scale?"

Key takeaways

• The verdict rewards a narrated decision process — clarify the input domain, state a brute force, then optimize — not just a passing return value.
• Read the constraint on n backwards: it encodes the intended complexity class (n≤20 → exponential; n≤10⁵ → O(n log n) or better).
• Most optimizations are a deliberate space-for-time trade, like Two Sum's hash map turning O(n²) into O(n) time at O(n) space.
• Always distinguish average vs worst case, and pressure-test edge cases (empty, single element, overflow) before declaring the solution correct.