The single highest-leverage reflex in an interview: the stated bound on n already tells you which complexity the interviewer is fishing for. Roughly 10^8 basic operations fit in a second, so the input size pins down the shape of the answer before you have thought about the problem at all.
Write pickApproach(n) returning the intended complexity as a string:
n <= 20 — "O(2^n) / bitmask" (subsets are still affordable, so brute force over subsets is the point)n <= 300 — "O(n^3)" (think Floyd-Warshall or interval DP)n <= 5000 — "O(n^2)" (a two-dimensional DP table)n <= 1000000 — "O(n log n)" (sort, heap, or binary search on the answer)- anything larger —
"O(n)" (one pass, maybe two pointers or a hash map)
The bands are inclusive on their upper bound, so n = 20 is the bitmask band and n = 21 is the next one down.