Design an App Discovery Service

This one is the exam. Builders publish apps into a gallery, users search and browse and type-ahead their way around it, and the ones they keep get remixed. You are asked for the backend of that in an hour, in three escalations, on top of types someone else already wrote.

Nothing here is an algorithm. Every hard part is a product rule that has to survive the next requirement.

The recipe

Say before you type: "Two indexes and an append-only log. Current state answers what is true now; the log answers what happened, and I never let one rewrite the other."

Four structures carry the whole problem:

private apps = new Map<string, AppRecord>();
private tagToApps = new Map<string, Set<string>>();
private aliases = new Map<string, string>();
private events: DiscoveryEvent[] = [];

If you can name those four in the first two minutes, phase three is bookkeeping. If you reach for one map and improvise, phase three is a rewrite.

Identity is a namespace

An app id is owner + "/" + slug. Say why out loud: two builders both shipped something called crm, and neither of them is wrong. Keying on the slug alone collides on the most popular names — exactly the ones a gallery has the most of.

The other half of that: identity is exact. Normalize tags, normalize queries, never normalize the id. Ada/CRM and ada/crm are two rows, and quietly merging them loses one builder's app.

Two indexes, one truth

Tags live on the app and the app lives under the tag:

app.tags: Set<string>       // what is this app about
tagToApps: Map<string, Set<string>>  // who is in this category

Both, always, in the same method. The bug the hidden tests hunt for is the republish path: an app that swaps ["sales"] for ["productivity"] and stays in the sales bucket forever. Removing from one side and forgetting the other is how a gallery starts serving apps that no longer claim the tag.

And notice which republish rule is the graded one. tags present replaces the set; tags absent leaves it alone. undefined is not [] — that distinction is the difference between a title edit and a silent untagging.

The false override

Visibility has a default, an override, and an order:

const override = record.overrides.get(userId);
if (override !== undefined) return override;
return record.accessLevel === "PUBLIC";

undefined, not falsy. A Set of allowed users cannot express hide this public app from this one person, and the moment you need that — a takedown, a block, a mistaken publish — a Set forces a rewrite. Reach for Map<string, boolean> the first time and say why.

Overrides also outlive the metadata they hang off. Republishing an app replaces the title and the access level; it must not quietly re-expose a row to someone it was taken away from.

Normalize once

Tags, queries, and prefixes all go through the same function, then the same alias table. That is the whole reason "Marketing & Sales", "sales", and "SALES" browse to one place.

Two things about aliases interviewers actually ask. First, register the alias key normalized too — an alias table keyed on raw input matches nothing. Second, adding an alias does not rewrite tags already stored; it changes what future writes resolve to. That is a real product decision with a real consequence: alias first, then import, or run a backfill. Saying that unprompted is worth more than the code.

Prefix means three things

The word shows up in this problem three times, and they are unrelated:

• Identity prefix — owner/ namespaces the app.
• Query prefix — suggest() matches from the front, not anywhere.
• Category prefix — a canonical tag is the browse path.

Search uses includes. Autocomplete uses startsWith. Mixing them gives you a type-ahead that suggests Landing Page Builder when you type age, which reads as a bug to everyone who sees it.

A scan is fine here. Name the trie as the thing you would reach for at scale and move on — building one costs ten minutes and buys nothing the tests can see.

The rollout is a hash, not a coin

bucket < rolloutPercentage

Two properties, both graded. Stable: the same user hashes to the same bucket forever, so nobody flips arms between page loads. Monotonic: raising the percentage only ever adds users, so a ramp never reshuffles the cohort you were measuring.

<= instead of < puts bucket 0 into a 0% rollout — a "disabled" experiment that is quietly serving one percent of traffic. And Math.random() fails both properties at once.

Overrides beat the hash, and the event records which decided: a pinned user has no bucket to report, so bucket and rolloutPercentage come back null. That null is not a nicety — it is how you exclude pinned staff from the experiment read.

Events are facts

Search and suggest write; nothing rewrites. Republishing an app under a new title does not change what a search returned last Tuesday, and moving the rollout does not restate which arm served a past query. Hand back copies for the same reason — a caller that mutates resultAppIds has edited your evidence.

recordRemix is where the log earns its keep, because validation is against history, not against current state:

if (source.kind === "SEARCH" && !source.resultAppIds.includes(appId)) return false;
if (source.kind === "SUGGEST" && !this.isDiscoverable(appId, userId)) return false;

A search named the apps it showed, so ask the event. A suggestion named a tag, not an app, so the event cannot answer and you ask the world instead. Two source kinds, two different questions — collapsing them into one check is the failure mode.

And a rejected remix consumes no id. Ids that skip are ids that look like dropped events to whoever reads the log later.

Conversion, not volume

The last method is the thesis:

conversionRate = remixCount / searchCount;

The query people type most is not the query that works. crm searched two hundred times and remixed twice is a discovery failure wearing a popularity costume; a query searched twice and remixed twice is the thing to put in the type-ahead. Ranking autocomplete by query frequency ships the first one to the top of everyone's screen.

Same idea one level down: DISCOVERY_V2 differs from control by exactly one term, +15 per remix. That is the entire experiment, and it is enough to reorder the gallery.

Windows are half open — [start, end) — so back-to-back periods tile without double counting, same as the billing drill. Inverted or empty windows return nothing rather than throwing; a dashboard that crashes on a bad date picker is a worse bug than one that shows an empty table.

What they will ask after

The follow-ups are the interview, not the code:

• What stops spam tags from owning the vocabulary?
• What happens to a brand new app with no conversion data — and how long does it get the benefit of the doubt?
• Which of these indexes becomes a Postgres index, and which becomes a materialized view?
• Would you optimize clicks, remixes, or retention, and what does each one do to the gallery a year out?

Have an answer for the cold-start one. Ranking by conversion means an app with no traffic can never earn traffic, and noticing that before it is pointed out is the difference between a pass and a strong pass.