How to Approach an Interview Problem

Big-O & the Python Toolkit, lesson 3 of 3

How to Approach an Interview Problem

A six-step routine: clarify, examples, brute force, optimise, code, test.

11 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Interviewers grade the process as much as the final code. Follow the same six steps every time:

  1. Clarify. Restate the problem. Ask about input size, empty input, duplicates, negatives, and what to return when there's no answer.
  2. Examples. Work one normal case and one edge case by hand. This catches misunderstandings early.
  3. Brute force. Describe the simplest correct approach and its Big-O, even if it's slow.
  4. Optimise. Compare it with the constraints. Ask: what work is repeated? Can sorting, a hash map, two pointers or a heap remove it?
  5. Code. Write it cleanly, with clear names, talking as you go.
  6. Test. Trace your examples through the code, then the edge cases. State the final time and space complexity.

Worked example: given a list of integers, return the smallest absolute difference between any two of them.

  1. Clarify: n up to 10⁵ → aim for O(n log n). Negatives and duplicates allowed. Fewer than two numbers → return None.
  2. Examples: [4, 9, 1, 7] → 2 (7 and 9). [5, 5] → 0. [3] → None.
  3. Brute force: compare every pair. O(n²): 5·10⁹ steps at n = 10⁵. Too slow.
  4. Optimise: after sorting, the closest pair must sit next to each other (anything between them would be even closer). Sort, then compare neighbours: O(n log n).
  5. Code it (below).
  6. Test: a quick random cross-check against the brute force catches mistakes the examples miss.
Example

Brute force as a safety net

Comparing a fast solution with a slow-but-obvious one on many small random inputs is called stress testing. It's the quickest way to find the edge case you forgot. Try breaking min_gap (say, drop the length check) and rerun. Sorting takes O(n log n) time and a new O(n) list; the scan uses O(1) working space beyond that list.

Edge cases to run through before you say "done":

  • empty input, a single element, exactly two
  • all elements equal, lots of duplicates
  • negatives and zero
  • already sorted, reverse sorted
  • the answer at the very first or last position
  • the maximum size (is it fast enough?)
Quiz

Your code starts with best = nums[0]. Which input is most likely to crash it?

Quiz

n ≤ 10⁵ and your brute force is O(n²). What's the best next move?

Quiz

What does this print?

Exercise

Fix the first draft

second_largest(nums) should return the second largest distinct value, or None if there isn't one.

  • [3, 1, 2] → 2
  • [5, 5, 4] → 4 (the two 5s count once)
  • [7, 7] → None, [] → None

The first draft works on the happy path only. Walk through the edge cases and fix it. Bonus: do it in one pass with O(1) extra space, keeping the best two values seen so far.