VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 00: The method and Big-O

Lesson 0.1 of 6 in this moduleFree

The six-step interview loop

One method for every coding problem: clarify, brute force, optimise, code, test, explain complexity. Worked end to end on 'does this list contain a duplicate?', including how the best answer changes when the constraints change.

about 15 min 5 Python examples 4 quick checks

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 six steps in order (clarify, brute force, optimise, code, test, complexity) with the question each step answers.
Diagram— the six steps in order (clarify, brute force, optimise, code, test, complexity) with the question each step answers.

The loop is not bureaucracy. Each step answers one question, and each question exists because people fail without it:

  1. Clarify: what exactly are the inputs, the limits and the edge cases?
  2. Brute force: what is the simplest correct answer, and what does it cost?
  3. Optimise: what work is being repeated, and what could I remember instead?
  4. Code: can I write it cleanly, one idea per line?
  5. Test: does it survive empty, tiny, duplicate and extreme inputs?
  6. 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?

  1. Interviewers require two solutions
  2. It proves you understand the problem, gives a correct baseline to test against, and shows exactly what work the optimisation must remove
  3. Brute force is usually fast enough
  4. It wastes time on purpose
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.

python
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.

for n = 5, the brute force checks the 10 cells above the diagonal of the index grid; a table shows the count reaching about 5 × 10⁹ comparisons at n = 100,000.
Diagram— for n = 5, the brute force checks the 10 cells above the diagonal of the index grid; a table shows the count reaching about 5 × 10⁹ comparisons at n = 100,000.

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.

python
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).

four frames scanning [3, 1, 4, 1, 5]; the set grows {3}, {1, 3}, {1, 3, 4}, and at index 3 the value 1 is already in the set, so the answer is True.
Diagram— four frames scanning [3, 1, 4, 1, 5]; the set grows {3}, {1, 3}, {1, 3, 4}, and at index 3 the value 1 is already in the set, so the answer is True.
python
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?

  1. Sorting is always faster in Python
  2. Sorting finds more duplicates
  3. Sets can't store negative numbers
  4. 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
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.

a decision map from the constraints to the best approach for the duplicate question: brute force, hash set, sort in place, mark inside the array, cycle detection, or external methods.
Diagram— a decision map from the constraints to the best approach for the duplicate question: brute force, hash set, sort in place, mark inside the array, cycle detection, or external methods.
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]:

python
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?

  1. 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
  2. Negative numbers are slow
  3. Python can't flip signs of large numbers
  4. It only works on sorted lists
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, not a, b, tmp2.
  • Return early when the answer is known (return True at 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.

python
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?

  1. Use a set anyway
  2. Sort a copy
  3. Fall back to comparing pairs, O(n²) time, O(1) space, unless more constraints (like values in 1..n) unlock a cleverer method
  4. Use sign marking
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

  1. What question does each of the six steps answer?
  2. Why is O(n²) too slow for n = 100,000 in Python, in rough numbers?
  3. What work does the brute force repeat, and how do the set and sort versions remove it?
  4. When would you choose sorting over a set?
  5. Which constraint makes sign marking possible, and why?
  6. Why test the fast version against the brute force on random inputs?
Answers
  1. Clarify (inputs, limits, edges), brute force (simplest correct and its cost), optimise (what repeats), code (clean), test (edges), complexity (time and space, and why).
  2. About n²/2 = 5 × 10⁹ comparisons; at roughly 10⁷ simple operations per second that's minutes, not under a second.
  3. 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.
  4. When memory is tight (O(1) extra) and modifying the input is allowed, accepting O(n log n) time.
  5. Values in 1..n: each value maps to an index, so the array itself can record what's been seen.
  6. The brute force is easy to trust, so it's a reference that catches bugs in the clever versions.