Working a Problem Out Loud

The first five minutes decide most coding rounds. This lesson is the sequence, with the same problem worked twice.

The framework

1. CLARIFY        2-3 min   inputs, output, constraints, edge cases
2. EXAMPLE        1-2 min   work a small case by hand, out loud
3. APPROACH       2-3 min   state it, give the complexity, get agreement
4. CODE          15-20 min  narrate decisions, not syntax
5. TEST           3-5 min   walk your own code through an example
6. OPTIMISE       remaining  only after something works

The order is the point. Steps 1-3 take five minutes and are where the score is decided.

The problem

“Given a list of transactions, return the top K customers by total spend.”

The version that goes badly

[00:00] Interviewer: ...top K customers by total spend.
[00:05] Candidate:   Okay. So I'll sort the transactions...

        def top_k(transactions, k):
            totals = {}
            for t in transactions:
                totals[t['customer']] += t['amount']
            return sorted(totals.items(), key=lambda x: -x[1])[:k]

[04:30] Candidate:   Done.
[04:35] Interviewer: What happens on the first transaction for a customer?
[04:50] Candidate:   Oh — KeyError. Let me use defaultdict.
[05:30] Interviewer: What if two customers have the same total?
[05:45] Candidate:   Hmm. It'd pick... whichever sorted puts first, I guess.
[06:10] Interviewer: Is that deterministic?
[06:30] Candidate:   ...probably not, actually.
[07:00] Interviewer: What's the complexity?
[07:10] Candidate:   O(n log n) for the sort.
[07:20] Interviewer: Can you do better if k is small and n is large?
[07:40] Candidate:   Umm. Maybe a heap?
[08:30] Interviewer: Let's move on.

The code was nearly right. What failed:

• No clarification, so the tie-break and the empty case were discovered by the interviewer.
• Complexity stated only when asked, and the improvement guessed rather than reasoned.
• Every issue surfaced by the interviewer rather than the candidate — the round became a correction session.

The version that goes well

[00:00] Interviewer: ...top K customers by total spend.

[00:10] Candidate:   Let me make sure I have it. Input is a list of transactions,
                     each with a customer identifier and an amount. I return the K
                     customers with the highest total. A few questions.

                     What shape is a transaction — a dict, a tuple, an object?
[00:25] Interviewer: Dicts with 'customer' and 'amount'.

[00:30] Candidate:   Can amounts be negative — refunds?
[00:35] Interviewer: Good question. Yes, treat refunds as negative.

[00:40] Candidate:   Then a customer could have a negative total, and I should not
                     assume totals are positive. What if two customers tie for the
                     last spot?
[00:55] Interviewer: Break ties by customer id ascending.

[01:00] Candidate:   And roughly how big is the input? That decides whether I sort
                     everything or use a heap.
[01:10] Interviewer: Assume millions of transactions, k is small — say 10.

[01:20] Candidate:   That's useful. Last one: if there are fewer than K distinct
                     customers, return all of them?
[01:30] Interviewer: Yes.

[01:35] Candidate:   Let me work a small example.

                     transactions = [
                       {'customer': 'A', 'amount': 50},
                       {'customer': 'B', 'amount': 30},
                       {'customer': 'A', 'amount': -10},   # refund
                       {'customer': 'C', 'amount': 40},
                     ]
                     totals = {A: 40, B: 30, C: 40}
                     k = 2 → A and C both have 40, B has 30.
                            → A and C, ordered A then C by the tie-break.

[02:20] Candidate:   So the approach. One pass to build the totals — O(n) time,
                     O(m) space where m is distinct customers. Then select the top
                     K. Sorting is O(m log m); with k=10 and m possibly in the
                     millions, a heap gives O(m log k), which is much better. I'll
                     use heapq.nlargest, which does exactly that.

                     For the tie-break I'll sort by (-total, customer_id) so higher
                     totals come first and ties resolve alphabetically. That also
                     makes the output deterministic, which matters if this is
                     tested.

                     Does that sound right before I write it?
[03:10] Interviewer: Yes, go ahead.

Three minutes, and the interviewer has already scored: clarified constraints, surfaced refunds, found the tie-break, chose an algorithm from the stated data size, and asked for agreement.

import heapq
from collections import defaultdict

def top_k_customers(transactions, k):
    """Return the k customers with the highest total spend.

    Ties are broken by customer id ascending. Refunds are negative amounts.
    O(n) to aggregate, O(m log k) to select, where m = distinct customers.
    """
    if k <= 0 or not transactions:
        return []

    totals = defaultdict(float)
    for t in transactions:
        totals[t["customer"]] += t["amount"]

    # nlargest with a key that is deterministic on ties
    return heapq.nlargest(k, totals.items(), key=lambda kv: (kv[1], _invert(kv[0])))


def _invert(customer_id):
    """Ties: lower id should rank higher, but nlargest takes the largest key."""
    return tuple(-ord(c) for c in customer_id)

[06:40] Candidate:   Actually, that _invert helper is ugly and only works for
                     strings. Let me do it the clearer way — take the top k by
                     total, then sort that small slice properly. It's k log k
                     extra, and k is 10.

import heapq
from collections import defaultdict

def top_k_customers(transactions, k):
    """Return the k customers with the highest total spend, as (customer, total).

    Ties broken by customer id ascending. Refunds are negative amounts.
    Time: O(n + m log k).  Space: O(m).
    """
    if k <= 0 or not transactions:
        return []

    totals = defaultdict(float)
    for t in transactions:
        totals[t["customer"]] += t["amount"]

    # over-fetch so ties at the boundary can be resolved correctly
    candidates = heapq.nlargest(min(k * 2, len(totals)), totals.items(),
                                key=lambda kv: kv[1])
    candidates.sort(key=lambda kv: (-kv[1], kv[0]))
    return candidates[:k]

Catching your own inelegance and saying why you are changing it is a positive signal, not a negative one.

Test it yourself, before being asked

txns = [
    {"customer": "A", "amount": 50},
    {"customer": "B", "amount": 30},
    {"customer": "A", "amount": -10},
    {"customer": "C", "amount": 40},
]

print(top_k_customers(txns, 2))
print(top_k_customers(txns, 10))          # k > distinct customers
print(top_k_customers([], 3))             # empty input
print(top_k_customers(txns, 0))           # k = 0
print(top_k_customers([{"customer": "A", "amount": -5}], 1))   # all negative

[('A', 40.0), ('C', 40.0)]
[('A', 40.0), ('C', 40.0), ('B', 30.0)]
[]
[]
[('A', -5.0)]

Line one is the tie-break working: A and C both total 40, A first. Walking your own code through the example you built in step 2 catches most bugs before the interviewer sees them — and it demonstrates the habit that matters on the job.

Narrate decisions, not syntax

noise                                    signal
"now I'm writing a for loop"             "one pass, so this is O(n)"
"I'll call this variable totals"         "a dict so lookups are O(1) — a list
                                          would make this quadratic"
"and then return"                        "returning tuples rather than dicts so
                                          the caller can sort them directly"
"semicolon... no, Python"                (say nothing)

And when you need to think:

"Let me think about the tie-break for thirty seconds."

Twenty seconds of announced silence reads as composure. Twenty seconds of unannounced silence reads as being stuck.

When you are actually stuck

Say so, and say where:

weak:   [silence]
weak:   "I don't know."

strong: "I can get an O(n²) solution by comparing every pair — let me write that
         first so we have something correct, then look for the improvement. My
         instinct is that the repeated inner scan is the waste, so I'm looking for
         something that lets me answer the inner question in constant time. That
         usually means a hash map or sorting first."

That last version has: a working fallback, a stated complexity, an identified bottleneck, and a direction. It scores well even if you never reach the optimum. A brute force you can explain beats an optimum you cannot.

Take a hint gracefully, too:

Interviewer: "What if you sorted first?"
Candidate:   "Right — if it's sorted, the two-pointer approach works, because I
              can move the pointer that can improve the result. That's O(n log n)
              for the sort and O(n) for the scan, so O(n log n) overall, and I drop
              the extra space the hash map needed. Let me redo it."

Interviewers give hints deliberately. How you use one is part of the assessment; treating it as a failure is worse than needing it.

The clarifying questions that always apply

INPUT      what type? can it be empty? can it be huge?
VALUES     negatives? zero? duplicates? nulls? unicode?
OUTPUT     what exactly — indices or values? what order? what on no result?
SCALE      how many elements? does it fit in memory?
TIES       what breaks them? must the result be deterministic?
CONSTRAINTS can I modify the input? extra space allowed? library functions?

Pick the three or four that could change your approach. Asking all sixteen is its own failure — it reads as stalling.

Managing the clock

0:00-0:05   clarify, example, approach            ← if you skip this you lose the round
0:05-0:25   code the straightforward solution
0:25-0:30   test it yourself, fix what you find
0:30-0:40   optimise, or extend as asked
0:40-0:45   your questions

At 20 minutes with nothing working, abandon the clever approach and write the brute force. A correct O(n²) at 35 minutes scores far above an unfinished O(n) at 45.

The scoring

Practice

clarifying questions asked: 0
time to first line of code: 12 seconds

totals = {A: 40, B: 30, C: 40}
k=2 → A and C tie at 40 → tie-break needed

"now I'm writing a for loop"       noise
"a dict so lookups are O(1)"       signal

"I can get O(n²) by comparing every pair — let me write that first, then look
 for the improvement. The repeated inner scan is the waste."

Next: complexity analysis — Big-O measured rather than recited.