Skills101

AdvancedData Structures & Algorithms · Lesson 40 of 40 · Updated ·

How to Approach a DSA Interview Problem — From Brute Force to Optimal

You have learnt many data structures and algorithms. In a coding round the hard part is often not the algorithm itself but choosing it, under time pressure, while explaining your thinking. This lesson gives a method you can repeat for any problem, and works through one problem from a slow answer to a fast one. Patterns of interview rounds differ between companies and change over time, so treat this as a general method, not a description of any one company's process.

1. The method in seven steps

StepWhat you doWhat you say aloud
1. UnderstandRestate the problem; work one small example by hand"So for input …, the answer should be …"
2. ClarifyAsk about input size, value range, duplicates, negatives, empty input, ties"Can the array be empty? Are values whole numbers?"
3. ConstraintsUse n to guess the complexity you need"n is 10⁵, so O(n²) is too slow; I need O(n log n)."
4. Brute forceState the simplest correct idea and its cost"Checking every pair works, but it is O(n²)."
5. OptimiseFind the repeated work; match a pattern"We re-sum the same range; prefix sums avoid that."
6. CodeWrite clean code with clear namesExplain each block briefly as you write
7. TestDry-run a small example, then edge cases; state time and space"For an empty list this returns 0, which is right."

Do not skip steps 1 and 2. Solving the wrong problem quickly is the most common way to fail a round that you could have passed.

2. Let the constraints guide you

Online judges commonly allow around 1–2 seconds, and a typical machine does roughly 10⁸ simple steps per second (it varies with the language and the judge). So the size of n tells you which complexities can fit:

Table matching input size to complexity: n up to 10 allows O(n factorial), 20 allows O(2 to the n times n), 500 allows O(n cubed), 5,000 allows O(n squared), 10 to the 5 or 10 to the 6 needs O(n log n) or O(n), and 10 to the 9 needs O(log n) or O(1)

This is a guide, not a law. But if a problem says n ≤ 20, it is a strong hint that trying all subsets is intended; if it says n ≤ 10⁵, a nested loop over all pairs will almost certainly time out.

3. Worked example: students in a marks range

Problem: n students have marks from 0 to 100 (whole numbers). Then q questions follow, each asking: "how many students scored between L and R, inclusive?" Both n and q can be up to 10⁵.

Step 1–2. Example: marks [45, 72, 88, 45, 91, 60], question (45, 72) → 45, 72, 45, 60 → 4. Ask: are L ≤ R always? Can marks repeat? (Yes, here.)

Step 4 — brute force. For each question, scan all marks: O(n) per question, O(n · q) total, up to 10¹⁰ steps. Correct but too slow.

Step 5 — find the repeated work. Every question scans the same unchanged list. Two ways to avoid that:

  • Sort once, then each question is two binary searches: the first position with mark ≥ L and the first with mark > R. O((n + q) log n).
  • Marks are small whole numbers (0..100), so count how many students got each mark, build prefix sums of the counts, and answer each question in O(1): P[R + 1] − P[L]. O(n + q + 100).

Comparison of three approaches for n = q = 10 to the 5: scanning all marks per query takes about 10 times 10 to the 9 steps, sort plus two binary searches about 3.3 million, and a count array with prefix sums about 200 thousand

All three give the same answers — check that before trusting the fast ones:

from bisect import bisect_left, bisect_right

def brute(marks, queries):
    return [sum(1 for m in marks if L <= m <= R) for L, R in queries]

def with_sort(marks, queries):
    s = sorted(marks)
    return [bisect_right(s, R) - bisect_left(s, L) for L, R in queries]

def with_counts(marks, queries, M=100):
    cnt = [0] * (M + 1)
    for m in marks:
        cnt[m] += 1
    P = [0] * (M + 2)                     # P[i] = students with mark < i
    for i in range(M + 1):
        P[i + 1] = P[i] + cnt[i]
    return [P[R + 1] - P[L] for L, R in queries]

marks = [45, 72, 88, 45, 91, 60]
queries = [(45, 72), (0, 100), (73, 87), (90, 100)]
print(brute(marks, queries))
print(with_sort(marks, queries))
print(with_counts(marks, queries))
[4, 6, 0, 1]
[4, 6, 0, 1]
[4, 6, 0, 1]

Step 7 — test edge cases. The questions above already include a range with nobody (73..87 → 0) and the full range (0..100 → everyone); also try L = R (one exact mark). Then state the cost: "O(n + q) time and O(M) extra space, where M = 101 possible marks."

Notice that the constraint on the values (0..100), not just on n, unlocked the fastest idea. Always read every constraint.

4. Clues that point to a pattern

If the problem says…Try…
sorted array, find a pair or a positiontwo pointers, binary search
"subarray" with a sum or a countprefix sums + hash map, sliding window
"k largest / smallest", "top k"heap
next greater / smaller elementmonotonic stack
fewest steps in an unweighted grid or graphBFS
weighted shortest pathDijkstra
dependencies, order of taskstopological sort
"are these connected?" with mergesunion-find
all combinations, permutations, subsetsbacktracking (small n)
count ways, min cost, max value with choicesdynamic programming
meetings, bookings, time rangessort the intervals, sweep
prefix search over many wordstrie

When no clue fits, go back to the brute force and ask: what is computed again and again? Storing it (hashing, prefix sums, DP) or ordering the data (sorting, heaps) is the usual fix.

5. Testing like an interviewer

Before saying "done", dry-run your code on the example line by line, then try these inputs aloud:

  • empty input, and a single element;
  • all elements equal, and many duplicates;
  • negative numbers and zero;
  • already sorted and reverse sorted input;
  • the largest values — can a sum overflow int in Java? Use long.

A short check like this often finds an off-by-one error before the interviewer does.

def max_pair_sum(nums):
    if len(nums) < 2:                # edge case found while testing
        return None
    a, b = sorted(nums)[-2:]
    return a + b

for case in [[3, 9, 4], [5], [], [-2, -7, -1], [4, 4, 4]]:
    print(case, "->", max_pair_sum(case))
[3, 9, 4] -> 13
[5] -> None
[] -> None
[-2, -7, -1] -> -3
[4, 4, 4] -> 8

Common mistakes

  • Starting to code before confirming the problem with an example.
  • Ignoring the constraints and writing an O(n²) solution for n = 10⁵.
  • Staying silent; the interviewer cannot give credit for thinking they cannot hear.
  • Jumping to a "clever" idea without first stating a correct brute force.
  • Not testing edge cases, or forgetting to state the time and space complexity.
  • Learning solutions by heart instead of the pattern behind them; a small change in the question then breaks the memorised answer.

Quick recap

  • Understand → clarify → constraints → brute force → optimise → code → test.
  • About 10⁸ simple steps per second is a rough guide: n = 10⁵ needs O(n log n) or better.
  • Optimise by finding repeated work; match clues to patterns.
  • Small value ranges allow counting arrays and prefix sums.
  • Dry-run, test edge cases, and say the complexity out loud.

Practice what you learned

📝 Quiz: Approaching DSA Interview Problems5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →