Design a Tag Registry

A practice problem in the escalating-screen format: a small phase one, then requirements that keep arriving. Time phase one to 15 minutes, and don't read an escalation until the previous one is green.

Phase 1 — the prompt

A creator platform lets people tag their projects so others can browse them. Build the registry that holds those tags.

Tags arrive from creators as free text, and they are messy: "AI", "ai", " A.I. " are all the same tag as far as browse is concerned.

Build a TagRegistry:

Method	Behavior
defineTag(canonical: string): void	Register a tag that browse is allowed to show
tagApp(appId: string, rawTag: string): void	Attach a tag to an app. rawTag is whatever the creator typed
tagsFor(appId: string): string[]	The canonical tags on one app, sorted
appsWithTag(rawTag: string): string[]	Every app carrying that tag, sorted

Rules:

• Normalize on the way in. Trim, case-fold, drop punctuation and internal spacing — " A.I. " and "ai" must resolve to the same tag as "AI".
• Tagging with a tag nobody defined does nothing, silently. Browse only shows what the taxonomy allows.
• Tagging the same app with the same tag twice is not an error and does not duplicate.
• Unknown app id returns an empty list rather than throwing.

Build it before reading on.

Phase 1 — the debrief

The design decision being auditioned: store canonical identity, display strings at the edge. Normalization is one pure function applied at every input door:

const normalize = (raw: string): string =>
  raw.toLowerCase().replace(/[^a-z0-9]/g, "");

class TagRegistry {
  private defined = new Map<string, string>();          // normalized -> canonical display
  private appTags = new Map<string, Set<string>>();     // appId -> normalized tags
  private tagApps = new Map<string, Set<string>>();     // normalized tag -> appIds

  defineTag(canonical: string): void {
    this.defined.set(normalize(canonical), canonical);
  }

  tagApp(appId: string, rawTag: string): void {
    const key = normalize(rawTag);
    if (!this.defined.has(key)) return;                 // undefined tag: silently ignored
    if (!this.appTags.has(appId)) this.appTags.set(appId, new Set());
    this.appTags.get(appId)!.add(key);                  // Set ⇒ re-tagging is free
    if (!this.tagApps.has(key)) this.tagApps.set(key, new Set());
    this.tagApps.get(key)!.add(appId);
  }

  tagsFor(appId: string): string[] {
    return [...(this.appTags.get(appId) ?? [])]
      .map((key) => this.defined.get(key)!)
      .sort();
  }

  appsWithTag(rawTag: string): string[] {
    return [...(this.tagApps.get(normalize(rawTag)) ?? [])].sort();
  }
}

Choices to narrate: sets everywhere make idempotence free; the two-directional index (appTags and tagApps) trades write amplification for O(1) reads in both directions — name that trade; and what's stored is the normalized key, with the display string resolved on the way out. That last one is about to be tested.

Escalation 1 — aliases

The taxonomy team wants explicit aliases, not just normalization: "ML" and "Artificial Intelligence" should both land on the canonical tag "AI" — and normalization alone can never get there, because they don't normalize to the same string.

Add addAlias(alias: string, canonical: string): void. Aliases normalize too. An alias pointing at an undefined tag is rejected. Existing tagged apps must be unaffected — an alias changes how tag text resolves, never what's already stored. That resolution applies at every input door, writes and lookups alike: after addAlias("ML", "AI"), appsWithTag("ML") returns the apps tagged AI. tagsFor still returns canonical tags only: aliases are input, never output.

If you stored display strings on apps rather than canonical keys, this is where it hurts — say whether your model absorbs it before you type. With canonical keys stored, the change is one resolution layer at the input door:

  private aliases = new Map<string, string>();          // normalized alias -> normalized canonical

  addAlias(alias: string, canonical: string): void {
    const target = normalize(canonical);
    if (!this.defined.has(target)) return;              // alias to nowhere: rejected
    this.aliases.set(normalize(alias), target);
  }

  private resolve(raw: string): string {
    const key = normalize(raw);
    return this.aliases.get(key) ?? key;
  }

…and tagApp / appsWithTag call resolve instead of normalize. Nothing stored changes, which is exactly what the requirement demanded.

Escalation 2 — merging two tags

The taxonomy has drifted and carries both "AI" and "MachineLearning" as separate canonical tags. Add mergeTags(from, into). Every app carrying from now carries into, no duplicates. Anything that used to resolve to from — including its aliases and its own name — now resolves to into. Merging is repeatable: after merging A into B, merging B into C must leave apps that started on A pointing at C. Merging a tag into itself is a no-op, not an infinite loop.

The last two rules are the real problem, and they should smell familiar: resolve-through-a-chain-of-redirects with repeatable merges is union-find. Each merged tag becomes a redirect pointer; resolve follows pointers to the root; path compression keeps chains short. The eager alternative — rewrite every app's tag set at merge time — also works, and the interviewer wants you to name the choice: rewrite cost O(apps with tag) once versus redirect cost on every future resolve, and which failure mode you prefer (a slow merge or a subtly-long chain).

The subtle bug being hunted: merging A→B and then B→C while A's redirect still points at B must land A on C — either compress paths on read (union-find) or re-point all existing redirects at merge time (eager). Handling merge(x, x) first, as a no-op guard, prevents the self-loop.

Escalation 3 — provenance

Tags now arrive from three sources — 'creator' | 'dependency' | 'readme' — and the UI needs to show which. Add provenanceFor(appId, rawTag): Source[] (sorted, deduped) and confirmedTagsFor(appId): a tag is confirmed if 'creator' is among its sources. Merging must union provenance across.

The principle worth quoting in the room: a tag system has three inputs — what the creator says, what the artifact contains, and what the taxonomy allows. Mechanically this upgrades appTags from Set<string> to Map<string, Set<Source>> — the value type grows, the keys and all the resolution logic stay put. If escalations keep changing only your value types, your keys were right.

Escalation 4 — counts, fast

Browse renders a sidebar with a live count next to every tag, over hundreds of thousands of apps. Add topTags(n): Array<{ tag, count }>, ties alphabetical. It must not walk every app per call.

Maintain the counts as you write: increment on first attach, decrement on detach, and — the part where naive counters go wrong — survive merges, where two counts combine but shared apps must not double-count. Since tagApps already holds the set per tag, the merged count is the size of the set union, not the sum. Then say the honest thing: for a sidebar over hundreds of thousands of apps, recomputing top-n from the maintained counts on read is O(tags log n) with a heap, and caching it behind a short TTL is what you'd actually ship.

What's being scored

• Canonical identity stored, display resolved at the edge — the phase-1 choice every escalation leans on.
• Input doors funneling through one resolve function, so each escalation is a change in one place.
• Recognizing merge semantics as union-find before writing a rewrite loop.
• Trade-offs said out loud: two-directional index, eager vs lazy merge, maintained counters vs recompute.