Technical questions
Big O and data structures for product managers
In this lesson7 sections
An unofficial lesson drawing on the methods in the Coding Questions chapter of Cracking the PM Interview by Gayle Laakmann McDowell and Jackie Bavaro (2014). PracHub is not affiliated with the authors or publisher. Buy the book
Big O is how engineers describe the way code slows down, or eats memory, as its data grows. For a PM it answers the question under most feasibility arguments: will this still work when we're ten times bigger? Live coding is uncommon in PM loops today, but technical PM rounds and design questions assume you can read a cost like O(n²) and pick a sensible data structure. Coding and technical rounds in PM interviews covers how those rounds run.
You're the PM for an invented second-hand furniture marketplace with 100,000 live listings, growing about 6% a month. A nightly job flags duplicate listings, mostly sellers re-posting a sofa to get back to the top of the feed. Tomás, the engineer who owns it, says it took 80 minutes last night. Is that a someday problem or a next-quarter one?
What big O measures
It tracks the trend as the input grows, for running time or for memory, and ignores the stopwatch. O(n) means doubling the input roughly doubles the work, on a laptop or a server rack, so engineers can compare approaches without running them.
Tomás's job compares every listing with every other one: about n²/2 pairs, so O(n²). Double the listings and the work quadruples. At a microsecond a comparison:
| Live listings | Pairs compared | Time |
|---|---|---|
| 100,000 | 5 billion | about 1.4 hours |
| 200,000 | 20 billion | about 5.6 hours |
| 1,000,000 | 500 billion | about 6 days |
The job has a five-hour window each night. At twice today's size it misses, and at 6% a month that's about a year away. A machine twice as fast buys only about six months of growth. When the cost is quadratic in a count that keeps rising, such as users or listings, the fix is a different design, and it's far cheaper to see that a year early.
To practise the feasibility habit, try Load Balancing Google.com Front Ends: Server Selection Strategies and Data Structures or Build Facebook post reactions: rules, data model, APIs and counts at scale. For each design, name the count that drives its cost and what a tenfold rise does.
Load Balancing Google.com Front Ends: Server Selection Strategies and Data Structures
A technical product manager question asking how a simple load balancer for Google.com would pick a front-end server for each request and which data...
Build Facebook post reactions: rules, data model, APIs and counts at scale
A product manager technical design question about implementing multi-type reactions on Facebook posts.
Choosing the nightly duplicate check
Tomás shows you the current job and the one he'd write instead. Version A compares every pair:
for each listing a in listings:
for each listing b after a:
if looks_same(a, b):
flag(a, b)
The inner loop runs over the list once for every listing, so the two loops multiply: O(n²). Starting each inner loop after a skips pairs already checked, which halves the work to the table's 5 billion comparisons. Halving doesn't change the trend, since doubling the listings still quadruples it, so big O drops the half and keeps n².
Version B makes one pass and remembers the titles it has seen:
seen = empty set
for each listing in listings:
key = normalize(listing.title) // lowercase, strip punctuation
if key is in seen:
flag(listing)
else:
add key to seen
Asking whether a key is in a set takes constant time on average (the next section shows why), while checking a list of earlier titles takes longer as the list grows. So the one pass is O(n). The set is the price. It holds one key per listing, so it needs O(n) memory: at roughly 100 bytes a title, about 10 MB today and 100 MB at a million listings.
Sorting gives Tomás a third option: sort by normalized title and compare neighbours. Built-in sorts cost O(n log n), so count that rather than writing your own. Duplicates land side by side, and with the database doing the sort the job never holds every title in memory.
So you're trading time against memory. Version A needs nothing extra but grows quadratically. Version B is linear and keeps a set that grows with the catalogue. Sorting sits between them on time and leaves the memory to the database.
Big O names the winner as the data grows, not on every dataset. On one seller's 30 listings, Version A's pair check may well beat Version B. On the full catalogue, Version A is the 80-minute job. On small or oddly shaped data, ask for a measurement before you promise a speed-up.
Know the floor. Any correct check must look at every listing at least once, so nothing beats O(n), and Version B is there. Further gains come from constants, such as a faster normalize or more machines, so stop asking for a cleverer algorithm. Big O in an interview goes deeper if you'll write code, and algorithms, data structures and complexity analysis defines the terms.
Which duplicates the moderators see
Then ask what Version B gives up. A fuzzy looks_same could match "Oak dining table, seats 6" with "6-seat oak dining table"; Version B catches only exact matches after normalizing. Which duplicates matter is a product call, and it's yours.
Exact matching is what makes Version B fast. Its set is a hash table, which turns each key into a number pointing to one slot, like a cloakroom ticket sending the attendant to one numbered hook. Engineers quote O(1) for insert and lookup, meaning on average: when a poor hash function or bad luck piles many keys into one slot, lookups there become a scan, O(n) at worst. Two titles one word apart get unrelated numbers, so the table can't tell they're close.
Moderators also want each cluster of duplicates once, not a heap of pairs. Swap the set for a map from each normalized title to the IDs of the listings that share it, filled in the same single pass, then send the entries with two or more IDs to the review queue, biggest first. Time stays O(n). The map holds IDs beside the titles, so memory grows, and the clusters still miss every fuzzy duplicate.
Arrays, strings and hash tables shows how tables earn their average. To practise this step, try Construct a hash from scratch and adapt it for tables, sharding and security and explain it aloud as if to an engineer.
Finding every ring of linked accounts
Duplicate clusters catch one seller re-posting. Trust and safety wants every ring of linked accounts, where a link is a shared phone number, device or card. No link joins one ring to the next, so a search from one account finds only its own ring. To get them all, go through the accounts and start a fresh search from each one no earlier search reached.
Each search then needs an order, and that's the reviewers' call. Breadth-first search checks every account one link from the start, then two links, and so on outward, which suits reviewers who want the closest accounts first. It keeps the accounts waiting their turn in a queue, oldest first. Depth-first search follows one chain of links as far as it goes, then backs up and tries the next branch. Choosing a tree or graph traversal goes further.
Run either one on the accounts and their links and it meets loops: A shares a phone with B, B a device with C, and C a card with A. Mark each account as visited, or the search circles that loop forever. The same marks tell the outer pass which accounts are already reached. With them, each account and each link is handled at most once, so a search takes time in proportion to accounts plus links, and memory goes to the marks and the accounts still waiting.
To practise this step, try Path-Planning Algorithm for a Wheeled Robot Crossing a Room Around Fixed Obstacles, talk it through, and end by stating your search's cost in time and memory.
The last risk is depth. Depth-first search is usually written recursively, the function calling itself on each linked account, and every call still waiting on a deeper one holds memory on the call stack. Down a chain of 50,000 linked accounts that's 50,000 waiting calls, O(n) memory, and Python stops at about 1,000 levels by default, so the search fails early. The marks matter here too: a call on an account already marked returns at once, the base case that lets the calls end at all. Rewrite the search as a loop that keeps its own stack of accounts to visit, newest first, and Python's limit no longer applies. Any recursion can be rewritten this way, sometimes with more effort. The stack and queue lesson and From recursion to dynamic programming go further.
To practise this step, try Product catalog lookup: item attributes plus a cycle-safe tree of related items. Before any code, say how you'd look items up, what happens when related items loop back, and how deep the recursion could go.
Matching tonight's listings to saved searches
The buyer-alert job matches each of tonight's new listings (a of them) against each saved search (s of them). Trying every pair costs O(a × s): 2,000 listings against 300,000 saved searches is 600 million checks. The two counts get separate letters because they grow separately. If saved searches grow tenfold and new listings don't, the job grows tenfold, not a hundredfold.
Tomás asks which side to put in a map. Say each saved search is an exact key, category plus city. Map each key to the buyers who saved it and every new listing needs one lookup, with the 300,000-search map held in memory. Map tonight's 2,000 listings by key instead and the map stays small, but every saved search does its own lookup. Either way, building the map and then running the lookups happen one after the other, so their costs add instead of multiplying.
That only holds while searches are exact keys. A saved search for sofas from $200 to $400 has no single key to look up, and the job drifts back toward trying every pair. Ranges need listings kept in price order.
Serving price filters as listings arrive
Price filters and price-range alerts ask the same thing: every listing between two prices, while new listings arrive all day. Keep the listings in a sorted list and a halving search finds a price fast: compare it with the middle listing, discard the half that can't hold it, repeat. A loop that halves its range on each pass is O(log n), about 20 steps among a million listings. But slotting a new listing into the middle of a sorted list shifts everything after it, O(n).
A balanced binary search tree keeps both cheap. Each node holds a listing and has at most two children (hence "binary"), and order is kept: everything down a node's left side is cheaper, everything down its right side dearer. Each step down rules out one side, the same halving, so finding or inserting costs O(log n). A range costs O(log n) to find its start, then one step per listing in it. Insert listings in price order with nothing rebalancing the tree and it becomes a long chain, sliding toward O(n). Library sorted maps, such as Java's TreeMap, rebalance themselves; ask whether a home-made one does. Sorting and binary search covers the rest.
What to bring to the design review
Questions for Tomás:
What count drives the cost, and how fast is it growing?
Is there a search inside a loop that a set or a map could replace?
What does the faster version give up, in matches or in memory?
Are we at the floor yet?
Then recommend:
"The pair check is quadratic, so it misses the five-hour window at twice today's size, about a year out at our growth. I'd ship the set version this quarter: linear time, and about 10 MB of memory today, 100 MB at a million listings. First, a week of both side by side, to count the near-duplicates exact matching misses."
For a full technical design case, try Technical design of a Google app that alerts shoppers to deals at nearby stores. For each component, say which structure holds its data and which operation on it runs most.