Cracking the interview

The failure is almost never the algorithm

People who fail technical interviews rarely fail because they did not know the algorithm. They fail because they started coding ninety seconds in, discovered a problem with their approach at minute twenty, and had nothing to fall back on.

The candidates who pass follow a visible process. They ask questions first, state a bad solution out loud before writing a good one, and explain what they are doing while they do it. That process is learnable in an afternoon, and it is worth more than another fifty solved problems.

The reason is structural: the interviewer cannot see your thinking. They are evaluating a recording of what you said and wrote. Silence while you brilliantly solve the problem in your head scores far worse than talking through a mediocre approach.

Step 1: clarify before you think

Interview questions are deliberately under-specified. The missing details are part of the test, and asking for them is scored positively rather than treated as weakness.

Ask about size: how many elements? That single answer tells you which complexities are acceptable. If n is up to a million, O(n squared) is off the table and you have just eliminated a wrong path for free.

Ask about the data: can it be empty, can values be negative, are duplicates possible, is it sorted, does it fit in memory? Each answer either simplifies your solution or reveals a case that would have broken it.

Ask about the output: one answer or all of them, the value or its index, and what should happen when there is no answer at all.

Two minutes here saves fifteen later, and it demonstrates exactly the caution people want in a colleague.

// "Find two numbers in an array that sum to a target."
//
// Q: How large can the array be?
// A: Up to 10^5.                 -> O(n^2) is ~10^10. Too slow. Need O(n log n) or better.
//
// Q: Is it sorted?
// A: No.                         -> two pointers need a sort; a hash map does not.
//
// Q: Return values or indices?
// A: Indices.                    -> sorting would destroy them. Map wins.
//
// Q: Exactly one answer guaranteed?
// A: Yes.                        -> no tie-breaking, no empty-result handling.
//
// Q: Can the same element be used twice?
// A: No.                         -> check the map BEFORE inserting the current element.

five questions, ~90 seconds
-> hash map, one pass, O(n) time, O(n) space
-> and the "check before insert" detail already settled

Step 2: say the brute force out loud

State the obvious solution before writing anything, even when it is embarrassingly slow. 'The brute force is to check every pair, which is O(n squared). Let me see if I can do better.'

This costs fifteen seconds and buys three things. It proves you understand the problem. It gives you a correct baseline you can always fall back to if the clever idea collapses. And it frames the rest of the conversation as optimisation, which is a much better position than a blank screen.

Then improve it deliberately rather than by inspiration. Ask what the brute force is wasting - because every optimisation in this course is the removal of a specific waste.

Re-scanning things you already saw? Remember them in a hash map (chapter 5). Re-sorting or re-searching a sorted thing? Binary search it (chapter 5). Re-computing the same sub-answer? Cache it (chapter 12). Comparing every pair when order would help? Sort first (chapter 4). Exploring every arrangement blindly? Prune it (chapter 3).

// The optimisation table - what the waste is, and what removes it

// waste: re-scanning what you already walked past
//   -> hash map / set                        O(n^2) -> O(n)

// waste: linear scanning a SORTED structure
//   -> binary search                         O(n)   -> O(log n)

// waste: recomputing the same sub-answer
//   -> memoisation                           exponential -> polynomial

// waste: comparing all pairs when order helps
//   -> sort, then two pointers               O(n^2) -> O(n log n)

// waste: exploring branches that cannot win
//   -> pruning / early exit                  huge -> tractable

// waste: keeping everything when you need the k best
//   -> heap of size k                        O(n log n) -> O(n log k)

"my brute force is O(n^2) because I re-scan the earlier elements"
     -> the waste is re-scanning
     -> the fix is a hash map
     -> O(n)

Step 3: code it, then test it before they do

Narrate while you write. Not every character, but the shape: 'I will keep a map from value to index, walk once, and check for the complement before inserting.' If you go quiet for two minutes the interviewer loses the thread, and a correct solution they could not follow scores worse than a partial one they could.

When the code is down, trace it yourself on a small input before being asked. Walk through with three or four elements out loud, watching the variables change. This is the same predict-and-verify habit the whole course has been drilling, and it catches most off-by-one errors in under a minute.

Then volunteer the edge cases rather than waiting: empty input, one element, all duplicates, no valid answer, the largest allowed size. Saying 'let me check the empty case' unprompted is one of the strongest signals you can send.

Finish by stating the complexity of what you wrote, in time and in space, and say whether you think it can be improved. That is the sentence that ends the question cleanly.