Lessons · Python · saying the cost out loud
Say the cost out loud, before you are asked
Name the time, name the space, and say where each comes from, in one breath: 'O(n) time because one pass; O(n) space because the set can hold every item.'
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Every coding interview ends with 'what's the complexity?'. The people who answer in one clean sentence are remembered as people who understand their own code; the people who say 'it's fast' are asked a harder question next.
How to think about it
Count the passes over the input: that is the time. Count what grows with the input: that is the space. Say both with the reason, then the edge case, then stop talking.
Worked example
def has_dup(xs):The code you wrote.
return len(set(xs)) != len(xs)One pass builds the set.
# Say: "O(n) time and O(n) extra space: one pass, and a set that can grow to n."The cost and where it comes from.
# Then the edge case: "An empty list returns False."Named before anyone asks.
print(has_dup([1, 2, 1]), has_dup([]))True False
Your turn
Say the cost of a loop inside a loop over n items.
# Say: "O() time, because for each item I scan every other item."
Solve one with the tests running
The trap
Saying 'it's fast' or 'linear-ish'. Vague words invite a follow-up you did not choose. A number and a reason end the question.