Merchant Search And Fuzzy Matching Indexes
Asked of: Software Engineer
Last updated
What's being tested
A strong answer demonstrates how to turn messy merchant names into fast, predictable search results using text normalization, inverted indexes, n-gram indexes, and bounded edit-distance matching. The interviewer is probing whether you can separate indexing-time work from query-time work, choose data structures based on latency and scale, and explain correctness tradeoffs rather than reaching immediately for brute-force string comparisons. Ramp cares because merchant search can sit on latency-sensitive expense, transaction, and enrichment workflows where false matches are costly and tail latency matters.
Core knowledge
-
Canonicalization reduces superficial variation before indexing: Unicode normalization, lowercasing, punctuation and whitespace normalization, legal-suffix handling such as
INCorLLC, and optional alias expansion. Preserve the original display name and avoid destructive transformations that erase meaningful distinctions. -
An inverted index maps tokens or character fragments to merchant IDs:
token -> postings list. Query processing intersects or unions postings, then ranks candidates; it avoids comparing a query with every merchant and typically scales far better than brute-force scans. -
Character n-grams are useful for misspellings, concatenation, and token-boundary errors. For a string of length and gram size , index roughly grams; trigrams are common, but short names need special handling because they produce few reliable grams.
-
Levenshtein distance counts insertions, deletions, and substitutions. Standard dynamic programming costs per comparison and memory with row reuse; use it only after candidate generation, not across millions of merchants.
-
Candidate generation and ranking should be separate phases. Retrieve a bounded candidate set using exact aliases, token search, n-grams, or a search engine’s fuzzy query, then rank with weighted signals such as edit distance, token overlap, prefix match, merchant popularity, and locale.
-
Approximate nearest-neighbor indexes such as HNSW are appropriate for vector or embedding similarity, but they are not a universal replacement for lexical search. They can miss exact identifiers, require model/version management, and make explainability harder; a hybrid lexical-plus-vector design is often safer.
-
Search analyzers in systems such as
LuceneorElasticsearchdefine tokenization, filters, stemming, synonyms, and n-grams. Keep index and query analyzers compatible, and version analyzer configuration because changing it generally requires a reindex. -
Ranking must protect precision. A fuzzy match for
Amazonshould not confidently select an unrelated merchant merely because it is popular. Require a minimum score or margin between the top two candidates, return “ambiguous” when confidence is insufficient, and expose candidate explanations for debugging. -
Index updates need an explicit consistency model. Immutable merchant attributes can be batch-indexed, while aliases and status changes may require near-real-time updates; use versioned documents, idempotent writes, and an alias swap or blue-green rebuild for safe reindexing.
-
Latency and memory trade off against recall. Increasing edit distance, n-gram expansion, synonym count, or candidate-set size improves recall but expands postings and query work. Define budgets such as
p99under 100 ms and cap fuzzy expansion rather than allowing pathological queries. -
Edge cases include empty or one-character queries, transliteration, Unicode confusables, diacritics, emojis, punctuation-only names, duplicate merchants, renamed businesses, and shared parent brands. Never let an empty normalized query match every document, and distinguish display names from stable merchant IDs.
Worked example
Representative scenario: “Design a merchant search and fuzzy matching index”
In the first 30 seconds, clarify whether the API returns one canonical merchant or ranked candidates, the expected merchant count and query rate, the freshness requirement, supported languages, acceptable p95/p99 latency, and the cost of false positives versus false negatives. I would state an initial assumption of tens of millions of merchant records, read-heavy traffic, sub-100-ms p99, and a requirement to abstain when confidence is low. I would organize the answer around canonicalization and alias data, index and query architecture, candidate generation plus ranking, and operational concerns such as reindexing and observability. I would store stable merchant IDs, original names, normalized fields, aliases, and status in a source of truth, then build a versioned Lucene-style inverted index with exact, token, and character n-gram fields. At query time, I would attempt exact alias lookup first, generate a bounded fuzzy candidate set second, and apply edit-distance and token-based ranking only to those candidates. A key tradeoff is whether to use larger n-gram coverage for recall or stricter expansion limits for predictable tail latency; I would prefer bounded search plus an explicit “no confident match” result. I would measure latency, candidate-set size, acceptance rate, and reviewed false-match rate, while logging analyzer and index versions for reproducibility. If I had more time, I would add multilingual normalization, tenant-specific aliases, staged reindexing, and adversarial tests for short or highly common merchant names.
A second angle
Representative scenario: “Debug a fuzzy merchant match that returns the wrong business”
The framing changes from designing the system to tracing a bad result through normalization, candidate retrieval, scoring, and final acceptance. First compare the raw query, normalized query, analyzer output, and indexed fields; a mismatch there can make ranking changes irrelevant. Then inspect whether the correct merchant entered the candidate set at all, separating recall failure from ranking failure. If it was retrieved but lost, examine token weights, edit-distance thresholds, popularity bias, and missing alias data. I would fix the narrowest layer responsible and add a regression fixture so the correction survives future analyzer or index changes.
Common pitfalls
Pitfall: Treating fuzzy matching as “compute Levenshtein distance against every merchant” is correct but operationally unusable at scale; generate candidates with an index first and use expensive scoring only on a bounded set.
Pitfall: Saying “return the highest-scoring result” ignores ambiguity and false-positive cost. A stronger answer defines thresholds, score margins, abstention behavior, and a review or fallback path.
Pitfall: Naming
ElasticsearchorLucenewithout explaining analyzers, postings, update consistency, and reindexing signals shallow knowledge. Describe what the system stores, how a query executes, and which knobs affect latency and recall.
Connections
An interviewer may pivot to distributed caching, blue-green index deployment, observability and tail-latency debugging, or idempotent event-driven updates. They may also ask how to test ranking quality with golden datasets without drifting into model-training design.
Further reading
-
Lucene Documentation: Indexing and Searching — details inverted indexes, analyzers, postings, and query execution.
-
Elasticsearch Fuzzy Query — concrete controls for edit distance and fuzzy expansion.
-
“Fast Approximate String Matching in a Dictionary” — Schulz and Mihov, 2002 — foundational techniques for dictionary-based approximate matching.
Related concepts
- ML Search, Embeddings, And Vector RetrievalML System Design
- Search Ranking And IndexingML System Design
- Search, Autocomplete And Restaurant DiscoverySystem Design
- A/B Testing for Retrieval and Ranking (Search/Feed)
- Meta Ads Ranking, Auction, And Relevance
- Google-Scale Search Indexing and Autocomplete System Design