In an ML engineer interview, the coding round usually gives you 45 to 60 minutes for one or two problems. The interviewer is grading four things: is it correct on edge cases, do you know its time and space cost, is the code clean, and can you explain your thinking while you work. A method makes all four visible, especially under pressure, when the instinct is to start typing.
This lesson teaches the loop you'll use on every problem in this roadmap, then runs it end to end on a small problem: does a list contain a duplicate? Small problems are where habits form. By the end you'll have three working solutions, know exactly when each one is the right answer, and know how to say so out loud.
1. Why a fixed method, from first principles
Ask what usually goes wrong in a coding round:
| Failure | What it looks like | The step that prevents it |
|---|---|---|
| Solving the wrong problem | Assumed the input was sorted; it wasn't | Clarify |
| Freezing while looking for the clever trick | Ten silent minutes, no code | Brute force first |
| An answer that's correct but too slow | O(n²) on n = 10⁵ | Optimise, guided by the constraints |
| Messy code that hides bugs | One 40-line function with index juggling | Code cleanly |
| Missing edge cases | Crashes on an empty list | Test |
| Can't say what it costs | "It's fast, I think" | Complexity |
The loop is not bureaucracy. Each step answers one question, and each question exists because people fail without it:
- Clarify: what exactly are the inputs, the limits and the edge cases?
- Brute force: what is the simplest correct answer, and what does it cost?
- Optimise: what work is being repeated, and what could I remember instead?
- Code: can I write it cleanly, one idea per line?
- Test: does it survive empty, tiny, duplicate and extreme inputs?
- Complexity: what are the time and space costs, and why?
Quick check
Why say a brute-force solution out loud before optimising, even when you suspect a faster method?
Show the answer
B. It proves you understand the problem, gives a correct baseline to test against, and shows exactly what work the optimisation must remove — A correct baseline anchors everything else: it defines the problem, provides test answers, and makes the repeated work visible.
2. Step 1: Clarify
The problem: given a list of integers nums, return True if any value appears at least twice, otherwise False.
Before writing anything, ask:
| Question | Why it matters |
|---|---|
How large can n be? |
Decides whether O(n²) is acceptable (lesson 0.3) |
| What range can the values take? | Small ranges allow counting by index instead of hashing |
| Can the list be empty, or have one element? | Both should return False; easy to crash on |
| May I modify the input (sort it in place)? | Unlocks an O(1)-extra-memory solution |
| Is memory limited? | A set of a million values costs tens of MB in Python |
| Is it one list, or many queries? | Many queries change what's worth precomputing |
Suppose the answers are: n up to 100,000, values between −10⁹ and 10⁹, the list may be empty, modifying it is
allowed, memory is not tight. Write those down; they will choose the algorithm.
Constraint arithmetic: if each step costs about one simple operation, and Python manages roughly 10⁷ simple operations per second, then anything near n² = 10¹⁰ steps is far too slow. We will need something close to O(n) or O(n log n). (Lesson 0.3 turns this into a reusable table.)
3. Step 2: Brute force
The simplest correct idea: compare every pair of positions.
def contains_duplicate_brute(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n): # j > i: each pair once
if nums[i] == nums[j]:
return True # stop at the first match
return False
assert contains_duplicate_brute([3, 1, 4, 1, 5]) is True
assert contains_duplicate_brute([1, 2, 3]) is False
assert contains_duplicate_brute([]) is False
assert contains_duplicate_brute([7]) is False
print("brute force works")
Why it's correct: every pair (i, j) with i < j is checked, so if a duplicate exists, one of those comparisons
finds it.
Cost:
- Time: the inner line runs (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 times in the worst case (no duplicates). That is O(n²).
- Space: two loop counters, O(1) extra.
Check it against the constraints: at n = 100,000 that's about 5 × 10⁹ comparisons. At roughly 10⁷ per second in Python, that's around 8 minutes. Correct, but far too slow. So we optimise, and the reason is the constraint, not style.
4. Step 3: Optimise, by asking what work is repeated
Look at what the brute force actually does. When it reaches index j, it compares nums[j] with every earlier
value, one by one. Then at j + 1 it walks through all of them again. The repeated work is re-scanning the past.
The question we're really asking at each step is only: "have I seen this value before?" That suggests two ideas.
Optimisation A: sort, then check neighbours
If the list were sorted, equal values would sit next to each other. One pass comparing neighbours finds any duplicate.
def contains_duplicate_sort(nums):
nums.sort() # O(n log n), in place: no extra list
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]: # equal values are adjacent after sorting
return True
return False
assert contains_duplicate_sort([3, 1, 4, 1, 5]) is True
assert contains_duplicate_sort([1, 2, 3]) is False
assert contains_duplicate_sort([]) is False
print("sort version works")
- Time: sorting is O(n log n), the scan O(n); total O(n log n). At n = 10⁵ that is about 1.7 million comparisons: well under a second.
- Space:
list.sort()works in place, so the only extra memory is the sort's own bookkeeping (Python's sort can use up to n/2 temporary slots in the worst case; in an interview, say "in place, O(1) extra apart from the sort's internals"). - Catch: it modifies the input. We asked in step 1 whether that's allowed. If not,
sorted(nums)makes a copy: O(n) extra space.
Optimisation B: remember what you've seen in a set
Instead of reordering the data, remember the values seen so far in a structure with fast membership checks. A
Python set answers "is x in here?" in O(1) on average (lesson 0.5 explains why).
def contains_duplicate_set(nums):
seen = set()
for x in nums:
if x in seen: # O(1) average membership check
return True
seen.add(x) # remember it for later elements
return False
assert contains_duplicate_set([3, 1, 4, 1, 5]) is True
assert contains_duplicate_set([1, 2, 3]) is False
assert contains_duplicate_set([]) is False
assert contains_duplicate_set([-10**9, 10**9, -10**9]) is True
print("set version works")
- Time: one pass, each step O(1) on average: O(n).
- Space: the set may hold up to n values: O(n). In CPython that's very roughly 40 to 70 bytes per value, so 100,000 values cost a few MB. Fine under our constraints.
The trade-off in one sentence: the sort trades time (n log n instead of n) for memory (O(1) extra instead of O(n)); the set trades memory for time. Which is better depends on the constraints, which is the point of the next section.
Quick check
The set version is O(n) and the sort version O(n log n). Why might an interviewer still prefer the sort version?
Show the answer
D. If memory is tight or the extra set is too large, sorting in place needs only O(1) extra memory, at the cost of a log n factor in time and modifying the input — Optimisation always trades something. The constraints decide whether time or memory is the scarce resource.
5. When the constraints change, the best answer changes
This is the habit that separates strong candidates: say how your answer would change if a constraint changed. Interviewers often ask exactly that as a follow-up.
| If the constraint becomes… | Best approach | Time | Extra space | Why |
|---|---|---|---|---|
| n ≤ 1,000 | Brute force | O(n²) | O(1) | 500,000 comparisons is instant; simplest wins |
| n ≤ 10⁶, memory is fine | Hash set | O(n) | O(n) | The default |
| O(1) extra memory, may modify | Sort in place | O(n log n) | O(1) | Order replaces memory |
| Values are in 1..n, may modify | Mark seen values inside the array | O(n) | O(1) | The array itself becomes the "seen" table |
| Read-only, n + 1 values all in 1..n | Cycle detection on index links | O(n) | O(1) | A duplicate creates a cycle (module 07) |
| More data than memory | External sort, or a Bloom filter | disk passes | tiny | Can't hold all values at once |
The "values in 1..n" row is worth seeing, because it shows how a constraint on values unlocks a new idea. If every
value v is between 1 and n, then v - 1 is a valid index. We can mark "I've seen v" by flipping the sign of
nums[v - 1]:
def contains_duplicate_marking(nums):
"""Values must be in 1..len(nums). Modifies nums (restore it if the caller needs it)."""
for x in nums:
slot = abs(x) - 1 # the index that represents value |x|
if nums[slot] < 0: # already marked: we've seen |x| before
return True
nums[slot] = -nums[slot] # mark |x| as seen
return False
assert contains_duplicate_marking([1, 3, 4, 2, 2]) is True
assert contains_duplicate_marking([3, 1, 2]) is False
assert contains_duplicate_marking([1]) is False
print("marking version works")
- Time: O(n). Extra space: O(1). It reuses the input's sign bit as storage.
- Only valid because of the value constraint. With values up to 10⁹, there's no index for them, and the trick doesn't apply. That's exactly why you ask about value ranges in step 1.
Quick check
Why does the sign-marking trick need every value to be between 1 and n?
Show the answer
A. It uses value v to address index v − 1; values outside 1..n have no index to mark, and existing negative values would be confused with marks — The trick turns the value range into storage. Without that constraint there is nowhere to record 'seen'.
6. Step 4: Code cleanly
A few habits that keep interview code readable and bug-free:
- Name things for what they mean:
seen,slot,left,right, nota,b,tmp2. - Return early when the answer is known (
return Trueat the first duplicate). - One idea per line; comment the why, not the what.
- Keep helper functions small; a 40-line function hides bugs.
- Don't optimise prematurely: write the clear O(n) version, not a micro-optimised one.
7. Step 5: Test
Run the cases that break real code: empty, single, all the same, no duplicates, duplicates at the edges, extreme values, and a large random check against the brute force.
import random
def contains_duplicate_brute(nums):
n = len(nums)
return any(nums[i] == nums[j] for i in range(n) for j in range(i + 1, n))
def contains_duplicate_set(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
def contains_duplicate_sort(nums):
nums = sorted(nums) # copy, so tests don't see a mutated list
return any(nums[i] == nums[i - 1] for i in range(1, len(nums)))
cases = [
([], False), ([7], False), ([2, 2], True), ([1, 2, 3, 4], False),
([5, 1, 2, 3, 5], True), ([-10**9, 10**9], False), ([0, -0], True),
]
for nums, expected in cases:
for fn in (contains_duplicate_brute, contains_duplicate_set, contains_duplicate_sort):
assert fn(list(nums)) == expected, (fn.__name__, nums)
# Random cross-check: the fast versions must agree with the brute force.
rng = random.Random(0)
for _ in range(300):
nums = [rng.randint(-20, 20) for _ in range(rng.randint(0, 25))]
want = contains_duplicate_brute(nums)
assert contains_duplicate_set(nums) == want
assert contains_duplicate_sort(nums) == want
print("all tests pass")
The random cross-check against the brute force is the most valuable test habit in this roadmap: the brute force is slow but easy to trust, so it becomes the reference for every faster version.
8. Step 6: Complexity, said clearly
| Approach | Time | Extra space | Modifies input? | Best when |
|---|---|---|---|---|
| Brute force | O(n²) | O(1) | No | n is small |
| Sort + neighbours | O(n log n) | O(1) in place | Yes | memory is tight |
| Hash set | O(n) average | O(n) | No | the default |
| Sign marking | O(n) | O(1) | Yes | values are in 1..n |
Say the why, not just the symbol: "The set version is O(n) time because each element does one O(1) average lookup and one insert; O(n) space because in the worst case every value is distinct and stored."
9. Saying it out loud
A 30-second script for this problem:
"Let me confirm: n up to 10⁵, any integers, empty input returns False, and I may use extra memory. The brute force compares every pair, O(n²), about 5 × 10⁹ steps here, too slow. The repeated work is re-scanning earlier values, so I'll remember them in a set: one pass, O(n) time, O(n) space. If memory were tight I'd sort in place and compare neighbours, O(n log n) time with O(1) extra. Let me code the set version and test empty, single, all-equal and extreme values."
Quick check
Midway through, the interviewer says: 'Now assume the list is read-only and you may use only O(1) extra memory, values arbitrary.' What is the honest best answer?
Show the answer
C. Fall back to comparing pairs, O(n²) time, O(1) space, unless more constraints (like values in 1..n) unlock a cleverer method — With read-only input, arbitrary values and O(1) memory, the faster methods are all ruled out; naming the trade-off and what would unlock better is the strong answer.
Check yourself
- What question does each of the six steps answer?
- Why is O(n²) too slow for n = 100,000 in Python, in rough numbers?
- What work does the brute force repeat, and how do the set and sort versions remove it?
- When would you choose sorting over a set?
- Which constraint makes sign marking possible, and why?
- Why test the fast version against the brute force on random inputs?
Answers
- Clarify (inputs, limits, edges), brute force (simplest correct and its cost), optimise (what repeats), code (clean), test (edges), complexity (time and space, and why).
- About n²/2 = 5 × 10⁹ comparisons; at roughly 10⁷ simple operations per second that's minutes, not under a second.
- Re-scanning earlier values for every new element. The set remembers them for O(1) lookups; sorting puts equal values next to each other so one neighbour check suffices.
- When memory is tight (O(1) extra) and modifying the input is allowed, accepting O(n log n) time.
- Values in 1..n: each value maps to an index, so the array itself can record what's been seen.
- The brute force is easy to trust, so it's a reference that catches bugs in the clever versions.