Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
Frontend System Design Roadmap
  1. 1.HTTP/1.1 vs HTTP/2 vs HTTP/3 (QUIC)
  2. 2.TCP and TLS Handshakes: Connection Setup Costs
  3. 3.Browser Network Stack and Connection Pooling
  4. 4.GET vs POST and Idempotency in HTTP
  5. 5.The Critical Rendering Path (CRP)
  6. 6.DOM, CSSOM and the Render Tree
  7. 7.Layout, Paint and Compositing
  8. 8.Reflows and Repaints Explained
  9. 9.Event Loop: Call Stack, Task and Microtask Queues
  10. 10.Async JavaScript: Promises and async/await
  11. 11.Web Workers: Multi-threading in the Browser
  12. 12.Browser Storage: Cookies, Web Storage, IndexedDB
  13. 13.Client-Side Storage: Limits and Security Risks
  14. 14.Choosing the Right Client-Side Storage
  15. 15.HTTP Caching: Cache-Control, ETag, Last-Modified
  16. 16.Browser-Level Caching Mechanisms
  17. 17.Cache Invalidation for Frontend Apps
  18. 18.Structuring a Large Single-Page App
  19. 19.Component-Based Architecture Principles
  20. 20.Props, State and Component Lifecycle
  21. 21.Module Bundling Basics
  22. 22.Core Web Vitals: LCP, INP and CLS
  23. 23.FCP and Time to Interactive (TTI) Explained
  24. 24.Measuring Performance: Lighthouse and WebPageTest
  25. 25.Asset Compression and Minification Basics
  26. 26.What Is a CDN and How Does It Work?
  27. 27.CDN Benefits: Latency, Availability, Offload
  28. 28.CDN Cache Behavior and Invalidation
  29. 29.Global State vs Local Component State
  30. 30.State Patterns: Redux, Zustand and Context
  31. 31.Data Fetching: React Query and SWR
  32. 32.Immutable Data in Frontend State
  33. 33.SSR vs CSR: Rendering Trade-offs
  34. 34.Hydration and Time to First Byte (TTFB)
  35. 35.Static Site Generation (SSG) for Speed and SEO
  36. 36.Incremental Static Regeneration (ISR)
  37. 37.Micro-Frontends: Core Principles
  38. 38.Micro-Frontend Integration Strategies
  39. 39.Communication Between Micro-Frontends
  40. 40.Micro-Frontends: Pros and Cons for Large Teams
  41. 41.Real-Time: Polling, SSE and WebSockets
  42. 42.Real-Time Use Cases: Chat, Alerts, Live Data
  43. 43.Designing a Real-Time Data Flow
  44. 44.Scaling WebSocket Connections
  45. 45.Responsive Images: srcset, sizes and picture
  46. 46.Modern Image Formats: WebP, AVIF, JPEG XL
  47. 47.Lazy Loading Images and Videos
  48. 48.Video Streaming: HLS, DASH, Adaptive Bitrate
  49. 49.REST and GraphQL for Frontend Engineers
  50. 50.Batching, Throttling and Debouncing API Calls
  51. 51.Handling API Errors in the Frontend
  52. 52.Authentication Flows: OAuth and JWT
  53. 53.Global Error Boundaries in React
  54. 54.Error Reporting: Sentry and LogRocket
  55. 55.Graceful Degradation and Fallback UIs
  56. 56.Real User Monitoring (RUM)
  57. 57.CORS: Cross-Origin Resource Sharing
  58. 58.Preventing XSS (Cross-Site Scripting)
  59. 59.CSRF Protection for Frontend Apps
  60. 60.Content Security Policy (CSP)
  61. 61.Storing Auth Tokens: Cookies vs localStorage
  62. 62.PWA Manifest and Installability
  63. 63.Service Workers: Lifecycle and Caching Strategies
  64. 64.Offline Support and Background Sync
  65. 65.Push Notifications for Web Apps
  66. 66.Webpack vs Vite vs Parcel
  67. 67.Code Splitting, Tree Shaking, Asset Optimization
  68. 68.Module Resolution and Hot Module Replacement
  69. 69.Monorepo Tooling: Nx and Lerna
  70. 70.Atomic Design for Component Libraries
  71. 71.Theming and Customization in Design Systems
  72. 72.Accessibility in Component Libraries
  73. 73.Component Library Docs, Testing and Versioning
  74. 74.Publishing and Consuming a Component Library
  75. 75.Full-Text Search: Levenshtein and Fuzzy Matching
  76. 76.Indexing Large Datasets in the Browser
  77. 77.Search Performance: Debouncing and Web Workers
  78. 78.Integrating Backend Search Services
  79. 79.Choosing a Chart Library: D3, Chart.js, Recharts
  80. 80.Rendering Large Datasets: Canvas vs SVG
  81. 81.Interactive, Responsive Data Visualizations
  82. 82.Data Fetching and Aggregation for Dashboards
  83. 83.A/B Test Design and Rollout Strategies
  84. 84.Client-Side vs Server-Side A/B Testing
  85. 85.Feature Flags and Remote Configuration
  86. 86.Experiment Data Collection and Analytics
Frontend System Design Roadmap
75

Frontend System Design · Lesson 75 of 86 · 4 min

Full-Text Search: Levenshtein and Fuzzy Matching

Knowing this lets you answer "design a typeahead" with specifics, not just hand-waving about "fuzzy search."

When a user types "iPhon" into a search bar, they expect to see "iPhone". Fuzzy matching makes this happen. Your job in an interview is to explain how you'd build it, what the performance costs are, and when to stop doing it on the client.

The core algorithm for this is usually Levenshtein distance.

How Levenshtein distance works

Levenshtein distance measures the difference between two strings. It's the minimum number of single-character edits (insertions, deletions, or substitutions) needed to change one string into the other.

"kitten" to "sitting" has a distance of 3:

  1. kitten → sitten (substitute 's' for 'k')
  2. sitten → sittin (substitute 'i' for 'e')
  3. sittin → sitting (insert 'g')

The standard way to calculate this is with dynamic programming, building a matrix of (s1.length + 1) x (s2.length + 1). The time and space complexity is O(m*n), where m and n are the lengths of the two strings.

This is fine for comparing two short strings. It is not fine for comparing a search query against a 10,000-item product list on every keystroke. That's the central trade-off.

Implementing a basic fuzzy search

You might be asked to code Levenshtein distance from scratch. It's a classic dynamic programming problem. The real goal is to see if you can then apply it.

Here’s a practical implementation that calculates the distance and then uses it to find suggestions from a list.

function levenshteinDistance(s1: string, s2: string): number {
    const m = s1.length;
    const n = s2.length;
    const dp = Array(n + 1).fill(null);

    for (let j = 0; j <= n; j++) {
        dp[j] = j;
    }

    for (let i = 1; i <= m; i++) {
        let prev = dp[0];
        dp[0] = i;
        for (let j = 1; j <= n; j++) {
            const temp = dp[j];
            const cost = s1[i - 1] === s2[j - 1] ? 0 : 1;
            dp[j] = Math.min(
                dp[j] + 1,          // Deletion
                dp[j - 1] + 1,      // Insertion
                prev + cost         // Substitution
            );
            prev = temp;
        }
    }
    return dp[n];
}

function getFuzzySuggestions(
    query: string,
    dictionary: string[],
    maxDistance: number = 2
): string[] {
    const suggestions: { word: string; distance: number }[] = [];
    const lowerCaseQuery = query.toLowerCase();

    for (const word of dictionary) {
        const distance = levenshteinDistance(lowerCaseQuery, word.toLowerCase());
        if (distance <= maxDistance) {
            suggestions.push({ word, distance });
        }
    }

    suggestions.sort((a, b) => a.distance - b.distance);
    return suggestions.map(s => s.word);
}

Note: The code above uses a space-optimized version of the DP algorithm (O(n) space instead of O(m*n)) by only keeping track of the previous row. This is a good optimization to mention if you're asked about complexity.

Knowing when to use a library (and why)

Implementing Levenshtein is a good exercise, but for a real app, you'd use a library.

The trap: Suggesting you'd run the function above over a large array on every keystroke. This will block the main thread and create a janky UI. For a 20-character query against 5,000 product names of average length 30, you're looking at millions of operations. This won't fit within a 16ms frame budget.

Libraries like Fuse.js are built for this. They don't just run Levenshtein in a loop. They pre-process the dataset to build an index, often using techniques like n-grams, to quickly narrow down the list of potential matches before running more expensive distance calculations.

This pre-computation is key. The initial indexing takes time, but subsequent searches are fast. This is the trade-off you make.

In an interview, your answer should be: "For a small, fixed list—say, under 500 items—a naive Levenshtein loop inside a debounced event handler might be acceptable. For anything larger, I'd use a dedicated library like Fuse.js to pre-build an index in memory, or I'd offload search to the backend."

Deciding between client-side and server-side search

This is a classic system design question that applies directly to fuzzy search.

Keep it on the client when:

  • The dataset is small and relatively static (e.g., country list, command palette options, a few hundred products).
  • You need instant, zero-latency feedback as the user types.
  • The search needs to work offline.

Move it to the server when:

  • The dataset is large (thousands to millions of items).
  • The data changes frequently.
  • The search logic is complex or needs to weigh results by other factors (e.g., popularity, user history, inventory).
  • You need to keep the client bundle size small.

For server-side, you wouldn't implement this yourself. You'd use a dedicated search engine like Elasticsearch or Algolia. They provide fuzzy matching capabilities out of the box, built on highly optimized data structures like inverted indexes.

Other fuzzy matching algorithms to know

Levenshtein is the most famous, but it's not the only one. Knowing the names of others shows you have a broader understanding.

  • N-grams: Breaks strings into chunks of N characters. "apple" as 3-grams (trigrams) is "app", "ppl", "ple". You find matches by comparing the set of n-grams between two strings. It's good for finding substring matches and is often used for indexing.
  • Phonetic Algorithms (Soundex, Metaphone): Index words by how they sound. Useful for matching names that are spelled differently but sound similar (e.g., "Smith" and "Smyth"). Less common for general-purpose frontend search, but good to be aware of.

You don't need to implement these. Just know what they're for: solving different kinds of "fuzziness" that Levenshtein might miss, like word order or phonetic similarity.

Try it

Take the getFuzzySuggestions function. Refactor it into a React hook, useFuzzySearch(query, list, { maxDistance: 2 }). Add debouncing to the query input so the calculation doesn't run on every single keystroke. Test it with a list of 100 city names.

Next: We'll discuss how to handle larger datasets on the client by creating your own search index in the browser in "Indexing Large Datasets in the Browser".

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice system design problems
Previous

Publishing and Consuming a Component Library

Next

Indexing Large Datasets in the Browser