Brute force first, then improve

Interview craft Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from itertools import combinations
vals, k = [1, 5, 3, 3, 7], 2
pairs = combinations(vals, 2)  # every pair of positions
slow = sum(1 for a, b in pairs if abs(a - b) == k)
print(slow)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 5

Right: 1 pairs with both 3s, 5 pairs with both 3s, and 5 pairs with 7.

This O(n²) count is the baseline that the next page speeds up to O(n) with a counter of earlier values.

Why not the others?
  • B 3. Each copy of 3 forms its own pair with 1 and with 5.
  • C 4. 5 and 7 also differ by 2.

30-second answer

A brute-force answer proves you understand the question and gives a baseline cost. To improve it, look for repeated work: a lookup done in a loop (use a hash map), a range recomputed each time (use a window or prefix sums), a sorted structure you ignore (use two pointers or binary search), or the same sub-question solved many times (use DP). Each improvement should come with its new cost.

Practise saying it · 45 s. No recording, just a timer

Explain going from brute force to an efficient solution.

Say your answer out loud, then check which of these points you covered:

  • Baseline and cost
  • Find repeated work
  • New cost

Deep dive

Name the bottleneck explicitly: 'the inner loop searches the list again'.

Trading memory for time (a set or a table) is the most common improvement.

If time is short, coding the brute force correctly beats an unfinished optimal answer.

Common mistakes

  • Silently coding an optimal answer with no explanation.
  • Spending most of the time on a brute force you will throw away.

Senior take & follow-ups

Say the baseline cost and the target cost in the same sentence.

Follow-up questions

Think of your answer first, then open the hint.

  1. When should you code the brute force?

    Show hint

    When you are stuck on the optimal idea, or when the interviewer asks for it first.

  2. How do you find the repeated work?

    Show hint

    Write the brute-force loops and ask which computation in the inner loop repeats across iterations.

Suggest a fix if something here is wrong or out of date.