Type-Ahead Search in TypeScript, Built with My DAA Course

Picture the finish line of a run. A runner is out of breath, hands on knees, and says the most useless sentence in event management: "I'm Aditi, I think my number is 12-something?" Now picture that you are the only person at the desk, and the club has hundreds of runners. That was the problem I set out to fix for Verve Run Club, and this is the story of how a college algorithms lab ended up inside a check-in box.

The problem: a finish line and a bib nobody remembers

The admin page for a run had one manual check-in box, and it wanted the whole bib number, typed exactly, like V-1234. That is fine when a QR code scans, and the scanner is the main path. But scanners fail sometimes: glare, a cracked screen, a dead battery. And when they do, the fallback has to be fast, because there is a queue behind every runner.

Nobody remembers a four-digit number they were handed an hour ago. They remember their name, and maybe the start of their bib. So I wanted the box to meet them halfway: type part of a name or part of a number, and the right person should already be on screen.

When you are the only person at the desk, every second of searching is a second a queue grows.

What it does now: type 12, see 1234 and 1235

Type 12 and every bib containing it appears, best matches first. Type adi and you get everyone whose name has adi in it. Each suggestion shows the name, bib, distance and whether they are already checked in, running or finished. I left email out on purpose: it is not something a runner says out loud at the finish line. Try the same logic below. The runners are made up, and the ranking code is the real thing.

Where DAA actually showed up

Here is the honest part, because I would rather you trust this post than be impressed by it: I did not write merge sort or a heap for this. JavaScript already has a sort. What my Design and Analysis of Algorithms lab (CS39001, ten days of programs in C) gave me was the habit of looking at a problem and asking which tool it is, what that tool costs, and where it breaks. A few days from the lab carried straight into this box:

• Day 1, one pass and keep track: score every runner in a single scan instead of filtering, then sorting, then filtering again.
• Day 3, divide and conquer: merge sort never varies, while quick sort depends entirely on the data. That is the whole reason I trust the built-in sort with a list I cannot predict.
• Day 4, the heap: the honest way to keep only the best eight results while scanning. I ended up not needing it, and I will explain why below.
• Day 8, dynamic programming: edit distance is the standard way to forgive typos, and it is the natural next step for this box.

Step 1: score every runner in one pass

Instead of a yes or no, every runner gets a score, where lower is better. A bib that exactly matches what you typed scores 0. A bib that merely contains it scores 2. Names get their own scale, starting at 3. The scale is what turns a pile of matches into a ranked list.

// V-1234 and 1234 are the same thing when typing.
const bibDigits = (bib: string) => bib.toLowerCase().replace(/^v-?/, "");

const qBib = bibDigits(q);
const isBibQuery = /^v-?\d*$/.test(q) || /^\d+$/.test(q);

for (const runner of runners) {
  let score = -1;

  if (isBibQuery && qBib) {
    const digits = bibDigits(runner.bib_number);
    if (digits === qBib) score = 0;
    else if (digits.startsWith(qBib)) score = 1;
    else if (digits.includes(qBib)) score = 2;
  } else if (!isBibQuery) {
    const name = runner.name.toLowerCase();
    const tokens = q.split(/\s+/).filter(Boolean);
    if (tokens.every((t) => name.includes(t))) {
      const words = name.split(/\s+/);
      if (name.startsWith(q)) score = 3;
      else if (tokens.every((t) => words.some((w) => w.startsWith(t)))) score = 4;
      else score = 5;
    }
  }

  if (score >= 0) scored.push({ runner, score });
}

One detail does a lot of work: the text you type decides whether it is a bib search or a name search, and the two never compete. Digits or a leading V mean bib. Anything with letters means name. That keeps a runner called Twelve from outranking bib 12, and it means the loop touches each runner exactly once. That is O(n), a single pass.

Step 2: sort by three keys

Scores alone leave ties, and a list that reshuffles between keystrokes feels broken. So the comparator looks at three things in order: score, then name, then bib. Only the matches are sorted, and then the list is cut to eight.

return scored
  .sort(
    (a, b) =>
      a.score - b.score ||
      a.runner.name.localeCompare(b.runner.name) ||
      a.runner.bib_number.localeCompare(b.runner.bib_number)
  )
  .slice(0, MAX_SUGGESTIONS)
  .map((s) => s.runner);

That single .sort() is where the course pays off, even though I did not write the sort. V8, the engine in Chrome and Node, uses TimSort: a merge sort blended with insertion sort that is stable, guaranteed O(m log m), and clever enough to finish nearly instantly when the data is already in order. Stability is what makes the three-key comparator behave, because equal items keep their place. And a guaranteed bound is exactly what Day 3 taught me to want, since I cannot predict what a crowd will type.

Race them yourself

Talking about complexity is cheap, so here is a way to feel it. Below are five sorts, four of them written the way the course taught them and counting every comparison, plus the built-in one Verve actually ships. Drag the list size up, then flip the data between shuffled, already sorted and reversed.

Push the slider to 2,000 runners. On shuffled data, insertion sort needs about 991,000 comparisons while merge sort needs about 19,000 and the built-in sort about 19,000. That gap is O(n²) against O(n log n), and it is the single most important picture in the whole course. Now switch to already sorted. Quick sort with a last-element pivot jumps to roughly 2 million comparisons, exactly the worst case Day 3 warns about, while the built-in sort needs 1,999. It notices the order and does almost nothing.

Why it is practical, and when I would stop

Here is the thing the course does not shout: knowing Big-O is as useful for stopping as it is for optimising. With a few hundred runners, scanning every one on each keystroke costs microseconds. A person types a few characters a second. The code is never the slow part, the human is. So the right question is not "what is the fastest possible algorithm" but "what is the simplest one that is clearly fast enough, and easy to trust at 6 AM".

A complicated data structure is also more code to get wrong on the one morning it must not fail. The simple version has fewer places to hide a bug, and I could check it against a handful of cases by hand. If the club ever grows tenfold, the table above is my map for what to reach for next.

The part that is not an algorithm

The riskiest thing in this box is not speed, it is a wrong pick. Check-in in this system also starts and finishes the clock, so ending the wrong runner's race is a real mistake that someone has to notice and undo. A fast search makes it easier to click the wrong row quickly. So Enter does not check anyone in. It picks the runner, fills in their bib, and shows their name, bib and status underneath. A second Enter, or the button, performs the action. If you type a complete bib that exists, the list steps aside and one Enter is enough.

function handleBibKeyDown(e: React.KeyboardEvent<HTMLInputElement>) {
  if (e.key === "ArrowDown" && suggestions.length) {
    e.preventDefault();
    setSuggestOpen(true);
    setActiveIndex((i) => (i + 1) % suggestions.length);
  } else if (e.key === "Enter" && showSuggestions) {
    // Pick the highlighted (or top) runner, do not act on them yet.
    e.preventDefault();
    chooseRunner(suggestions[activeIndex >= 0 ? activeIndex : 0].bib_number);
  } else if (e.key === "Escape") {
    setSuggestOpen(false);
    setActiveIndex(-1);
  }
}

That extra keypress costs a fraction of a second and removes a whole class of mistakes. It is the same idea I keep coming back to on this project: the fastest tool is the one that stays out of your way, and the safest is the one that asks once before doing something you cannot take back.

How I checked it

I wrote a dozen quick checks for the ranking, including the one from the top of this post: typing 12 must list V-1234 and V-1235 before V-5123, adi must find Aditi and Aditya, guru sam must find Guru Samal, and an empty box must return nothing. Every one passes. I ran the five sorts in the race above on 1, 2, 10, 200 and 2,000 items in all three orders and confirmed every result really is sorted. A comparison count means nothing if the algorithm is wrong.

What I would tell anyone taking DAA

• Use the course as a lens, not a checklist. You will rarely write merge sort again, but you will constantly choose between things that behave like it.
• Measure before you optimise. A counter in a sort takes five minutes and ends most arguments.
• Prefer the simple algorithm you can explain out loud, and write down what would make you switch.
• Design the human step, not just the code. The second Enter mattered more than any Big-O.
• Test the boring cases: empty input, one item, ties, already sorted. That is where real data lives.

Frequently asked questions

Want a system like this for your own club or event?

I build the whole engine for clubs, communities and small businesses: registrations, payments, tickets, live results and the admin tools that keep an event running with one person at the desk. If that sounds like your problem, you can find me at smit.website.