Preparing for Google

One ordering, by dependency rather than by date. Each step says what to read, what to drill, and the criterion for moving on. Start at step zero.

The seven steps of the 45 minutes, the English you say at each one, and what Google's own guide says about Drawings. If you read one page before the interview, read this.

The fifteen shapes that cover most questions, a recognition table keyed on the wording of the prompt, and sixty problems grouped by pattern.

Big O, amortised analysis and space complexity. The question behind the question is always "where does the log come from?"

Quicksort and merge sort written from scratch, and when merge sort works where quicksort is impractical. Google asks that one literally.

The email asks for it in writing: implement one using only arrays, in the space of an interview. Chaining, open addressing, tombstones and resizing.

Binary, n-ary, tries, and one balanced tree with its rotations. "You should know how it's implemented."

The three representations with their trade-offs, traversals, topological sort and union-find.

Weighted shortest paths, and the admissible heuristic that separates A* from Dijkstra.

Recognising the travelling salesman and knapsack in disguise, and what to say once you have.

Operation costs, generators, __slots__, the __eq__/__hash__ contract. They expect real depth in whichever language you pick.

Solving recursively, and proving by induction that the algorithm does what you claim it does.

Combinatorics, probability and n-choose-k. Google leans on this harder than most companies do.

Processes and threads, mutexes, semaphores, monitors, deadlock, context switching and scheduling. Your largest gap, and the email spells it out point by point.

Fifty pages: Google's own NALSD method, capacity arithmetic, production reliability, model serving, and ten worked cases including the translation pipeline this role is named after.

The ten-minute version, for the night before.

Eight to ten STAR stories covering ambiguity, feedback, user first and caring for the team. Only you can supply the stories.

Every table worth having, in one place. Not study material — this is what you scan for ten minutes the night before.

The full index, the runnable code, the drill harness and the audit.

Problems solved, and the mistakes that keep coming back.

Finding a pair, counting frequency, deduplicating, grouping equivalent things.

'Sorted array' plus 'a pair or a triple'; or a cycle in a linked structure.

'Contiguous subarray or substring' plus 'longest' or 'shortest'.

'Sorted array'; or 'the smallest k such that something is possible'.

'How many ways', 'minimum cost to', 'longest such-and-such'.

'All of the…', 'how many ways' when you have to list them.

Anything with a root, children, depth or levels.

'Prefix', 'autocomplete', 'dictionary of words'.

'Connected', 'reachable', 'fewest steps', 'valid order', 'prerequisites'.

'Cheapest route', 'minimum cost', 'earliest time to reach'.

'k largest', 'k closest', 'median of a stream', 'merge k sorted things'.

'Balanced brackets', 'next greater', 'largest rectangle'.

'Intervals', 'meetings', 'scheduling', 'overlapping'.

'Linked list', 'reverse', 'from the end', 'cycle'.

'Palindrome', 'anagram', 'parse', 'format', 'compress'.

'Without division', 'in place', 'one pass', 'constant extra space'.

'Spiral', 'rotate', 'in place' on a two-dimensional grid.

'Appears once', 'no extra space', 'count the bits', 'without arithmetic operators'.

The prompt opens with 'Design a…' and gives a target complexity per operation.

'Threads', 'in order', 'alternate', 'at most N at a time', 'deadlock'.