Rank a Search Result Set

A single-phase practical. No escalations, no class to design — one function body, forty minutes, and a dozen judgment calls stacked on top of each other. Time it to 25 minutes cold.

The prompt

A launcher has a search box and a row of tag chips. Return ordered results for apps based on some combination of tags, prefix matching, popularity, and typo tolerance.

type App = {
  // queries and names are always matched case-insensitively
  name: string;
  // higher is better
  popularity: number;
  tags: string[];
};

function searchApps(query: string, tags: string[], n: number = 5): App[];

Edit distance is provided. The catalog is seeded and small. Everything else is yours to decide — which is the actual exercise. The prompt deliberately says "some combination of" and stops there.

The one decision that reorganizes everything

Before any code: is this a filter or a ranking?

A filter narrows. The user types s, three apps survive, and the shelf holds three items. They add a tag chip and it drops to one. They typo and it drops to zero — an empty screen, from a box that had eight apps in it a second ago.

A ranking never narrows. It scores all eight, sorts, and hands back the top n — every time, no matter how weak the signal. A prefix hit that matches one app still returns five: the hit, then the four best of everything else. Zero hits still returns five, ordered by popularity, because "we have nothing for you" is the worst answer a launcher can give.

Pick ranking, and say why out loud. That sentence is the answer to "we want the best experience for the user — what does that mean to you here?" Everything below follows from it:

• Tags become a booster, not a gate. A gate can empty the shelf; a booster can only reorder it.
• Backfill stops being a feature. There is no "pad the leftovers back in from a second list" pass, because nothing was ever removed. The padding is the tail of the same ranking.
• Every input, however useless, is still a signal to sort by. An empty query is not a match on everything — it is no signal, which flattens the query dimension and lets tags and popularity decide.

The filter reading is defensible in a product where an empty result set is honest — a compliance audit, an inbox search. Say which reading you took and why. Taking one silently is the only wrong answer.

The tier ladder

Match quality is ordinal, not a weight. Exact beats prefix beats substring beats fuzzy beats nothing, and no amount of popularity may promote across a boundary.

Tier	Meaning
EXACT	The name is the query
PREFIX	The name starts with the query
SUBSTRING	The query appears somewhere inside
FUZZY	Within the typo budget
NONE	No signal — including every app when the query is empty

The moment you flatten these into score += 10 and score += 4, a popular no-match can outweigh an unpopular exact hit, and you will not notice until someone types a full app name and gets something else first. Ordinal tiers make that failure structurally impossible instead of numerically unlikely.

The sort key

One comparator, five clauses, in strict priority order:

1. tier ↓ — match quality, always first
2. matched tag count ↓ — tags refine inside a tier, never across one
3. popularity ↓ — the tiebreak, never the lead
4. shorter name — a tighter match on the same prefix
5. name ascending — deterministic to the end

Clause 3 is the one interviewers listen for. Popularity is the most tempting signal in the problem and the most dangerous: it is the only one that is always present, so any formula that lets it accumulate will eventually let it win. Demote it to a tiebreak and it can only ever order things that are already equal.

Clauses 4 and 5 look like padding. They are not: without them, two apps with equal tier, equal tags, and equal popularity sort by whatever order the engine happened to walk, and the same query returns different lists on different days.

The fuzzy budget

Typo tolerance is where naive implementations fall over, in two ways.

Scale the budget to the query. A one-character query has nothing to be wrong about — with a budget of 1, q is within edit distance of half the alphabet and the fuzzy tier means nothing. Three characters or fewer gets no budget at all; 4 to 6 gets one edit; longer gets two.

Measure against the leading slice of the name, not the whole name. This is the subtle one. levenshtein("s", "discord") is 7, so whole-name distance punishes anyone who is still typing — the shorter the query, the worse every app scores. Compare the query against the first query.length + budget characters instead, and a prefix-in-progress is measured against the part of the name it is actually trying to be.

The implementation

const TIER = { EXACT: 4, PREFIX: 3, SUBSTRING: 2, FUZZY: 1, NONE: 0 } as const;

function typoBudget(length: number): number {
  return length <= 3 ? 0 : length <= 6 ? 1 : 2;
}

function matchTier(name: string, query: string): number {
  // An empty query is no signal, not a match on everything.
  if (!query) return TIER.NONE;
  const n = name.toLowerCase();
  const q = query.toLowerCase();
  if (n === q) return TIER.EXACT;
  if (n.startsWith(q)) return TIER.PREFIX;
  if (n.includes(q)) return TIER.SUBSTRING;
  const budget = typoBudget(q.length);
  if (budget > 0 && levenshteinDistance(n.slice(0, q.length + budget), q) <= budget) {
    return TIER.FUZZY;
  }
  return TIER.NONE;
}

function searchApps(query: string, tags: string[], n: number = 5): App[] {
  if (n <= 0) return [];
  const wanted = new Set(tags.map((tag) => tag.trim().toLowerCase()).filter(Boolean));

  return apps
    .map((app) => ({
      app,
      tier: matchTier(app.name, query),
      tagHits: app.tags.filter((tag) => wanted.has(tag.toLowerCase())).length,
    }))
    .sort(
      (a, b) =>
        b.tier - a.tier ||
        b.tagHits - a.tagHits ||
        b.app.popularity - a.app.popularity ||
        a.app.name.length - b.app.name.length ||
        a.app.name.localeCompare(b.app.name)
    )
    .slice(0, n)
    .map((row) => row.app);
}

Score once, sort once, slice once. The whole thing is O(catalog · query) and the shape is a map → sort → slice pipeline that reads top to bottom.

Note what the leading .map buys beyond readability: it builds a new array of scored rows, so the .sort never touches apps. Sorting the source catalog in place ranks correctly on the first call and quietly corrupts every call after it — the kind of bug that passes a cold test run and fails in a live session.

Edge cases, and what each one is really testing

Input	Answer	The rule it proves
Query matches one app	Still n results	Ranking, not filtering
Query matches nothing	Still n, by popularity	No signal is not no answer
Empty query, tags set	Tagged apps first, then popularity	Empty query = no constraint
Two tags, one app matches both	That app leads the tagged group	Tag count ranks, not tag presence
Prefix hit vs tagged non-hit	Prefix hit wins	Tags cannot cross a tier
n of 0 or less	[]	Guard before you sort
n past the end of the catalog	The whole catalog, ranked	Slice, don't index
SPOT with tag SOCIAL	Same as spot / social	Case folding on both inputs

What to say out loud

The code is twenty lines and the interview is forty minutes. The remaining thirty-five are spent narrating decisions, so have these ready:

• "I'm treating this as ranking rather than filtering, so I'll always return n — an empty shelf is the worst outcome for a launcher."
• "Tiers are ordinal. Popularity is a tiebreak, so it can reorder equals but can never beat relevance."
• "Tags boost inside a tier rather than gating, which follows from always returning n."
• "Fuzzy matching is measured against the leading slice of the name, because whole-name distance punishes a query that's still being typed."
• "I'm scoring into a new array so the catalog itself is never reordered."

Then offer the extension you did not build: per-tier weights tuned on click-through, recency of last launch as a sixth clause, or a real inverted index once the catalog stops fitting in a loop. Naming the next move is worth more than building it.