The judge says Time Limit Exceeded on test 7 of 12, and tests 1 to 6 passed.
Nothing is wrong with your answer: it is correct on every input it finishes. In
a live round the same failure sounds different — the interviewer says "this
table has ten lakh rows", waits, and then asks what your code would cost. Locally
everything was instant, because your sample had twenty rows.
Any problem where a small input hides the cost: duplicate detection, pair sums,
top-k, "find the two closest values", nested lookups inside a loop, or a pandas
apply that queries another table per row. Common on judges with a one or two
second limit, and common in data interviews where the interviewer names a real
row count on purpose. It is also the shape of a first-month production bug, when
a nightly batch that ran fine in testing misses its window.
Linked module: 6.3 (Coding round for AI roles); related arithmetic: 4.9.
A nested loop over the same list compares every pair. For n rows that is about n squared divided by two comparisons. The trap is that n squared looks harmless until n gets real: doubling the rows makes the work four times bigger, and the growth is invisible at sample size.
Measured on one ordinary laptop, the pure-Python duplicate check took 0.026 seconds at 2,000 rows, 0.097 at 4,000 and 0.399 at 8,000. Each doubling costs about four times more, which is the definition of quadratic with a stopwatch attached. Scaling that same measurement to ten lakh rows predicts roughly 1.8 hours. The one-pass version using a set finished the same ten lakh rows in about 0.020 seconds on the same machine. Your numbers will differ; the ratio will not.
That is the whole diagnosis. The judge's time limit and a nightly batch window are the same constraint wearing different clothes. A thirty-minute window has room for the one-pass version several thousand times over, and no room at all for the quadratic one.
The hidden version of this bug in data work is worse, because it does not look
like a loop. A .apply that looks up another table per row, a for loop that
calls a merge inside it, or a repeated list.count() inside a comprehension all
create the same quadratic shape while looking like one tidy line.
Before you write code, estimate. Ask the interviewer or read the constraints for the row count. Then say the cost out loud: "with a nested loop this is O(n squared); at the size you named that will not finish, so I will use a hash map." Estimating first is worth marks even if your first version is still the slow one.
The four swaps that fix most of these
if x in a_list inside a loop is O(n) each
time. Put the values in a set or dict once, and the test becomes about
one step.codes.count(c) inside a loop rescans the list per
code. One pass with collections.Counter replaces all of them..apply that queries
another table with a single merge or map, which hashes the key once.When the judge has already failed you, do not start rewriting logic. Time limit exceeded is a complexity message, not a correctness message. Find the innermost repeated work, ask what it costs per outer iteration, and replace the inner scan with a lookup structure. Then re-estimate before resubmitting.
Measure it yourself once, so the intuition is yours rather than borrowed.
Time both versions at three sizes with time.perf_counter, check that the slow
one grows about four times per doubling, and extrapolate to the size in the
question. Ten minutes of this buys you a permanent instinct for when a nested
loop is fine and when it is fatal.
Make a complexity estimate part of the restatement, not an afterthought: say the expected cost before you type. Keep the rough scale in your head — a nested loop is comfortable in the thousands, doubtful in the tens of thousands, and hopeless in the lakhs. In practice sessions, always run your solution once at a realistic size rather than only at sample size, because a sample can never expose this class of bug. In real work, apply the same habit to any batch job with a deadline, and check the row count that the job will see in production and not the one in your test file.
Q: "This works. What is its complexity, and what would you change if the table had ten lakh rows?" Strong answer: state time and memory separately, name the exact line that dominates, propose the swap, and give the new cost. Mentioning that you measured the difference yourself, with the doubling ratio you saw, is what makes the answer sound like experience rather than revision. Interviewers ask this to find out whether you can predict a production problem before it happens, which is most of what senior engineers are paid for.