L62 · Company-Tagged — Microsoft & Amazon

Series: LeetCode — From Basics to Interview-Ready · Session 62 / 65 · Phase 4 · Interview simulation

Prerequisites

You should have finished Phases 1–3 (patterns through advanced). This is not a new-pattern session — it's a targeting session. You already own the techniques; now you point them at the specific problem distributions and interview styles of the two companies most people in this series are aiming at.

Watch first (skim before the session)

Why this session exists

By this point you've drilled patterns in isolation. Interviews don't hand you a labelled pattern — they hand you a story, and they're tagged by company because different companies pull from different corners of the problem space and grade differently. This session is about targeting: work the frequency-ranked list for your target company, and rehearse the delivery style that company rewards.

The two companies here have genuinely different cultures, and treating an Amazon loop like a Microsoft loop (or vice versa) leaves marks on the table.

Microsoft: style and staples

Microsoft interviews tend to be conversational and extension-driven. A single problem often grows: you solve the base case, then they add a constraint ("now the input streams in", "now do it in place", "now handle duplicates"). They care about clean code, correct edge cases, and how gracefully you adapt when the problem mutates mid-interview.

Staple problems (real LeetCode, classically Microsoft-tagged):

• LC151 · Reverse Words in a String — in-place-ish string surgery; watch multiple spaces.
• LC54 · Spiral Matrix — careful boundary bookkeeping; the extension is "generate" (LC59).
• LC48 · Rotate Image — in-place 90° rotation; the transpose-then-reverse trick.
• LC236 · Lowest Common Ancestor of a Binary Tree — the recursive return-up pattern.
• LC138 · Copy List with Random Pointer — hashmap or the interleave trick.
• LC146 · LRU Cache — hashmap + doubly-linked list; a design classic they love.
• LC33 · Search in Rotated Sorted Array — binary search with the sorted-half decision.
• LC53 · Maximum Subarray — Kadane; extension to "return the subarray".

Amazon: style and staples

Amazon interviews wrap DSA in Leadership-Principles framing and value clear narration, explicit trade-offs, and edge-case discipline. The coding bar is medium-heavy; the differentiator is often how you communicate — stating assumptions, calling out complexity, and connecting your choices to customer impact.

Staple problems (real LeetCode, classically Amazon-tagged):

• LC200 · Number of Islands — the single most-asked Amazon graph problem; DFS/BFS flood fill.
• LC56 · Merge Intervals — sort-then-sweep; the canonical interval problem.
• LC146 · LRU Cache — design; also huge at Amazon.
• LC127 · Word Ladder — BFS shortest transform (Hard).
• LC973 · K Closest Points to Origin — heap / quickselect.
• LC1 · Two Sum — still asked as a warm-up; nail it in 60 seconds.
• LC994 · Rotting Oranges — multi-source BFS.
• LC207 · Course Schedule — topological sort / cycle detection.

From first principles: why company-tagged practice works

Mental model

Memory hook

"Amazon: narrate and dive deep. Microsoft: solve then stretch." Two four-word cues, one per company, capturing the delivery difference. On the morning of a loop, recite the one for that company; it primes the behaviour the graders actually reward.

What interviewers actually ask (mixed mock)

Run these as a timed mock, alternating the two styles. For each, state complexity out loud and name at least one edge case before coding.

• LC200 · Number of Islands — Amazon. DFS/BFS flood fill. Probe: grid traversal + visited handling; follow-up: count island shapes (LC694) or largest island (LC695).
• LC56 · Merge Intervals — Amazon, Microsoft. Sort by start, sweep. Probe: the overlap condition; follow-up: insert one interval into a sorted set (LC57).
• LC54 · Spiral Matrix — Microsoft. Boundary shrinking. Probe: off-by-one on the four edges; follow-up: generate the spiral (LC59).
• LC146 · LRU Cache — both. Hashmap + DLL, all ops O(1). Probe: the eviction wiring; follow-up: LFU (LC460, Hard).
• LC33 · Search in Rotated Sorted Array — Microsoft. Which half is sorted. Probe: the pivot logic; follow-up: with duplicates (LC81).
• LC973 · K Closest Points to Origin — Amazon. Max-heap of size k or quickselect. Probe: why a heap beats a full sort; follow-up: quickselect for average O(n).

The escalation is always there — have the follow-up ready before they ask. That readiness is what "senior signal" looks like.

Tradeoff

Timing rubric — the 75-minute session

This is a mock, so it runs against a clock. Two problems, alternating styles, plus a delivery review.

Within each 25-minute problem, the internal marks that matter: clarify by minute 2, approach stated by minute 6, coding by minute 8, complexity restated by minute 20, edge cases walked by minute 24. If you are coding before minute 6 you skipped the part that is actually graded.

Self-scoring — two scorecards

Score each problem against the scorecard for the style you ran it in. These deliberately differ, because the two rooms reward different things.

Amazon scorecard (0–2 each, out of 10):

• Stated the brute force and its complexity before optimising.
• Named the insight explicitly, as a sentence, rather than silently rewriting the code.
• Justified the chosen data structure in one sentence tied to the requirement.
• Enumerated edge cases before running — empty input, single element, all-duplicates, extreme bound.
• Connected a choice to impact at least once ("quickselect avoids the full sort, which matters when n is millions and k is small").

Microsoft scorecard (0–2 each, out of 10):

• Base case solved cleanly with no dead code or leftover variables.
• Boundary bookkeeping correct on the first run — no off-by-one discovered by the interviewer.
• Proactively invited the extension rather than waiting to be asked.
• Adapted to the mutation without rewriting from scratch — the original structure survived.
• Code reads well: meaningful names, early returns, no nesting past three levels.

8–10 — loop-ready for that style. 5–7 — the code is there, the delivery is not; that gap is the cheapest thing in this whole track to close. Below 5 — re-run the same problem tomorrow in the same style before adding new problems. The failure is not the algorithm.

A useful diagnostic: if your Amazon score is much higher than your Microsoft score, you narrate well but write messy first drafts. The reverse means you write clean code silently. Both are fixable, and they are fixed by different drills.

Common failure modes

Working the list top-down instead of weakness-first. The frequency list is sorted by how often problems appear, not by how badly you need them. Number of Islands sitting at the top is irrelevant if you can already write it cold. Cross off everything you are fluent at before you start, then work what remains.

Memorising the list instead of the patterns. Company banks rotate. A candidate who memorised forty tagged problems and meets the forty-first is worse off than one who owns the eight underlying patterns, because memorisation actively suppresses the classification step. Use the list as a weighting over patterns, never as a script.

Practising silently and assuming narration will appear on the day. It will not. Narration under pressure consumes bandwidth that difficulty is already using, which is precisely why it collapses at the moment it is needed. If you did not narrate in practice, you will not narrate in the room.

Treating the follow-up as optional. At Microsoft the follow-up frequently is the interview; the base problem is the warm-up that establishes you can code. Finishing the base and stopping reads as finishing half the question.

Reciting Leadership Principles by name. Amazon's rubric rewards the behaviour — depth of investigation, high standards on edge cases, clear ownership of a trade-off. Naming the principle out loud while your code has an off-by-one is worse than saying nothing.

Skipping the warm-up problem. The first problem in any session absorbs the cold-start penalty. In a real loop that penalty lands on a graded problem. Spend three minutes on Two Sum so it lands somewhere harmless.

Ignoring the clarification phase because you recognise the problem. Recognising it is exactly when you are most likely to solve a subtly different problem than the one asked. Restate it in your own words regardless — it costs ninety seconds and catches the expensive mistakes.

Recovery scripts

You blank on a staple you have definitely solved before. Do not chase the memory; rebuild from the classification. "This is a connected-components count on a grid, so it is flood fill. I need a visited mechanism and a traversal — let me sink islands in place to avoid the extra structure." The category regenerates the code. Chasing a remembered solution does not.

The Microsoft extension breaks your whole approach. Say the cost plainly and choose: "Streaming input means I cannot do the second pass. My prefix array approach does not survive that — I would need a monotonic structure maintained online. Let me sketch that rather than patch the current code." Recognising that a mutation invalidates the design is the exact thing being tested.

You are asked for a complexity you have not worked out. Derive it out loud instead of guessing. "Outer loop over n cells, and each cell is pushed and popped at most once across all traversals, so O(rows × cols) total rather than per cell." A derived answer survives the follow-up question; a guessed one does not.

You give a wrong complexity and realise it. Correct yourself immediately and cheaply: "I said O(n log n) — that is wrong, the sort dominates only if k is close to n; with a size-k heap it is O(n log k)." Self-correction is a positive signal. Hoping nobody noticed is not.

Thirty seconds of silence and nothing coming. Fall back to a concrete example out loud. Take a 3×3 grid, walk it by hand, and describe what you are doing. Narrating a hand-trace is legitimate work, keeps the room engaged, and restarts the approach more reliably than staring.

In practice

Frequency-ranked company lists are a real and legitimate prep tool (LeetCode's own company tags, and community-maintained frequency lists). The signal is noisy — banks rotate, and no list is a guarantee — so treat it as a weighting, not a script. The durable habit this session builds is meta: near any high-stakes evaluation, spend your last scarce hours on the intersection of "most likely to appear" and "where I'm weakest", and rehearse the delivery the evaluator rewards. That transfers well beyond coding interviews.

Follow-up chains — have the next question ready

At both companies the escalation is expected. Knowing the chain in advance is what lets you invite it rather than survive it. Company attributions describe these problems' long-standing reputation as commonly-asked questions, not any claim about a specific interview loop.

• Number of Islands (200) → Max Area of Island (695) → Number of Distinct Islands (694) → "what if the grid does not fit in memory?" The memory variant is a union-find-over-row-boundaries conversation, and saying so is enough even if you do not implement it.
• Merge Intervals (56) → Insert Interval (57) → Non-overlapping Intervals (435) → Meeting Rooms II (253). The last one flips from sorting to a heap, which is the interesting jump.
• Spiral Matrix (54) → Spiral Matrix II (59) → "now do it for a non-square matrix" → "now start from the centre". Pure boundary discipline all the way down.
• LRU Cache (146) → LFU Cache (460) → "make it thread-safe" → "now it is distributed". The last two are design conversations, not code, and they are where a strong candidate separates.
• Search in Rotated Sorted Array (33) → with duplicates (81) → Find Minimum in Rotated Sorted Array (153). The duplicates variant breaks the worst case to O(n) and being able to say why is the whole point of the follow-up.
• K Closest Points (973) → "do it in average O(n)" (quickselect) → "the points arrive as a stream" (bounded max-heap) → "there are a billion points across a hundred machines" (per-shard top-k, then merge).

The pattern across every chain: the first follow-up is a variant, the second changes the constraint, the third removes the assumption that the data fits on one machine. Expect that shape and the escalation stops being a surprise.

Practice queue

Run as a timed mock in this order; log each as cold / warm / hint / failed, and note whether you narrated + handled the follow-up.

1. LC200 Number of Islands — Amazon staple.
2. LC56 Merge Intervals — both.
3. LC54 Spiral Matrix — Microsoft staple.
4. LC146 LRU Cache — design, both.
5. LC33 Search in Rotated Sorted Array — Microsoft.
6. LC973 K Closest Points to Origin — Amazon.