Typeahead and Nearby Search

Autocomplete with tries, plus geospatial nearby search (Yelp / Uber).

• Advanced
• 38 min read
• 3 objectives

Before this lessonLesson 13: Web Crawler

Two related designs: search autocomplete (suggestions as you type) and nearby search (businesses or drivers around a point). Both are read-heavy prefix or radius queries that must return in about 100 ms.

Part A — Typeahead

Clarify

• Top N suggestions per prefix. Personalized?
• Languages / Unicode? Typo tolerance?
• How fast must a trending query appear (minutes vs a day)?

Target: p99 well under 100 ms, high QPS, ranked by popularity and recency, personal history mixed in at the edge, denylist for terms you will not suggest.

flowchart LR U[Keystroke] --> GW[API / edge] GW --> C[(Prefix cache)] C -->|miss| T[Trie in memory] T --> Rank[Ranker] Rank --> U Logs[Query logs] --> Agg[Aggregator] Agg --> T

Hot prefixes are cached at the edge. The trie is built offline from aggregated logs and loaded into memory on each box.

Index

A trie of characters. Each node stores the current top K completions so a request does not walk the whole subtree. Shard by first character (or first two) across machines. Rebuild from query logs on an hourly job; push a new snapshot to the boxes. Cache the first 1–2 character prefixes in Redis/CDN — they are tiny and extremely hot.

class Node:
    def __init__(self):
        self.children = {}
        self.top = []   # [(freq, phrase)]

def add(root, phrase, freq):
    n = root
    for ch in phrase:
        n = n.children.setdefault(ch, Node())
        n.top.append((freq, phrase))
        n.top = sorted(n.top, reverse=True)[:3]

root = Node()
for p, f in [("paris", 90), ("park", 40), ("parent", 20), ("tokyo", 80)]:
    add(root, p, f)
print([p for _, p in root.children["p"].top])

['paris', 'park', 'parent']

Ranking and abuse

• Global frequency × recency, plus the user's recent searches (a small personal cache).
• If the prefix misses, try edit-distance 1 as a fallback (spell correction).
• Apply a denylist at assemble time so the trie never suggests terms you do not want.

Part B — Nearby search

Directory: businesses in a map viewport, filter by category, rank by distance and rating. Matching: given a rider, find nearby idle drivers and offer one. Both need a geo index — not a full table scan.

• Partition by city first. Never query the whole planet.
• Geohash / S2 / H3: encode lat/lng into a cell id. Index documents by cell. A radius query becomes 'cells that overlap this circle' plus a precise distance filter on the candidates.
• Quadtrees and R-trees are the textbook structures; a geo index in Redis or Elasticsearch is an acceptable production answer if you explain cells.
• Live locations (drivers): update every few seconds in an in-memory grid per city. Disk is for trip history, not the match loop. Matching: candidates in nearby cells → ETA from routing → offer one driver with compare-and-set so two riders cannot get the same car. Surge is demand/supply counts per cell, a pricing layer.

# Cell size vs geohash length (illustrative)
# 5 chars ~ 2.4 km, 6 chars ~ 0.6 km, 7 chars ~ 76 m
def cells_for_radius(center_hash: str, precision: int):
    prefix = center_hash[:precision]
    return [prefix]  # plus 8 neighbors in a real library

print(cells_for_radius("tdr1w8y", 5))

// Write your solution here