High-Level Design: Autocomplete/Typeahead System

Table of Contents

1. Problem Statement & Requirements
2. High-Level Architecture
3. Component Architecture (Frontend)
4. Data Flow (Search As You Type)
5. API Design & Communication Protocols
6. Database Design
7. Caching Strategy
8. State Management
9. Performance Optimization
10. Error Handling & Edge Cases
11. Interview Cross-Questions
12. Accessibility (A11y)
13. Mobile & Touch Considerations
14. Internationalization (i18n)
15. Offline Support & PWA
16. Web Workers for Heavy Computations
17. Comprehensive Testing Strategy
18. Analytics & Observability
19. Build vs Buy Analysis
20. Memory Management
21. Interview Questions - Additional Topics

---

1. Problem Statement & Requirements

Problem Statement

Design an autocomplete/typeahead system that suggests search queries or items as users type, providing real-time suggestions with minimal latency.

Functional Requirements

Must Have:

• Suggest top K (5-10) results as user types
• Support prefix-based matching
• Display suggestions within 100-200ms
• Handle 1000+ QPS (Queries Per Second)
• Store millions of searchable terms
• Update suggestions in real-time as user types

Should Have:

• Rank suggestions by popularity/frequency
• Support recent searches (user-specific)
• Handle typos and fuzzy matching
• Show trending/popular searches
• Personalized suggestions based on user history
• Category-based filtering

Nice to Have:

• Rich autocomplete with images/metadata
• Multi-language support
• Voice input support
• Highlighting matched portions

Non-Functional Requirements

1. Performance

   • Sub 200ms latency for suggestions
   • Handle high read throughput (read-heavy system)
   • Minimal network payload

2. Scalability

   • Support millions of users
   • Handle billions of queries per day
   • Scale horizontally

3. Availability

   • 99.9% uptime
   • Graceful degradation on failures

4. User Experience

   • Smooth typing experience (no lag)
   • Progressive enhancement
   • Keyboard navigation support

Capacity Estimation

Assumptions:

• 500M daily active users
• 10 searches per user per day
• Average query length: 50 bytes
• Suggestion list size: 10 items

Calculations:

Daily Queries: 500M × 10 = 5B queries/day
QPS (peak): 5B / 86400 × 3 = ~170K QPS
Storage for queries: 5B × 50 bytes = 250 GB/day
Bandwidth: 170K × 500 bytes (response) = 85 MB/s

---

2. High-Level Architecture

System Architecture Diagram

┌─────────────────────────────────────────────────────────────────────┐
│                          CLIENT LAYER                               │
│  ┌──────────────────────────────────────────────────────────────┐  │
│  │  Browser                                                      │  │
│  │  ┌────────────┐  ┌──────────────┐  ┌─────────────────┐     │  │
│  │  │ Input Box  │──│  Debouncer   │──│ Local Cache     │     │  │
│  │  └────────────┘  └──────────────┘  └─────────────────┘     │  │
│  │         │               │                    │               │  │
│  │         └───────────────┼────────────────────┘               │  │
│  │                         ▼                                    │  │
│  │              ┌──────────────────────┐                        │  │
│  │              │  HTTP REST Client    │                        │  │
│  │              └──────────────────────┘                        │  │
│  └────────────────────────│─────────────────────────────────────┘  │
└────────────────────────────┼─────────────────────────────────────┬─┘
                             │                                     │
                             ▼                                     │
┌─────────────────────────────────────────────────────────────────┴─┐
│                       NETWORK LAYER                                │
│                    CDN / Edge Network                              │
│                  (Geographically Distributed)                      │
└────────────────────────────┬───────────────────────────────────────┘
                             │
                             ▼
┌─────────────────────────────────────────────────────────────────┐
│                      API GATEWAY LAYER                          │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │  Load Balancer (L7)                                       │  │
│  │  - Rate Limiting                                          │  │
│  │  - Request Routing                                        │  │
│  │  - SSL Termination                                        │  │
│  └────────────────────────┬─────────────────────────────────┘  │
└───────────────────────────┼─────────────────────────────────────┘
                            │
        ┌───────────────────┼───────────────────┐
        │                   │                   │
        ▼                   ▼                   ▼
┌──────────────┐   ┌──────────────┐   ┌──────────────┐
│ Autocomplete │   │ Autocomplete │   │ Autocomplete │
│  Service 1   │   │  Service 2   │   │  Service N   │
└──────┬───────┘   └──────┬───────┘   └──────┬───────┘
       │                  │                  │
       └──────────────────┼──────────────────┘
                          │
         ┌────────────────┼────────────────┐
         │                │                │
         ▼                ▼                ▼
┌─────────────────────────────────────────────────────────────────┐
│                    CACHING LAYER                                │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │  Redis Cluster (Distributed Cache)                       │  │
│  │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐     │  │
│  │  │  LRU Cache  │  │ Hot Queries │  │ User Cache  │     │  │
│  │  │  (prefix->  │  │  (trending) │  │  (recent)   │     │  │
│  │  │suggestions) │  │             │  │             │     │  │
│  │  └─────────────┘  └─────────────┘  └─────────────┘     │  │
│  └──────────────────────────────────────────────────────────┘  │
└────────────────────────────┬─────────────────────────────────────┘
                             │
                             ▼
┌─────────────────────────────────────────────────────────────────┐
│                     DATA LAYER                                  │
│                                                                 │
│  ┌─────────────────────┐        ┌──────────────────────┐      │
│  │  Elasticsearch      │        │  PostgreSQL/MongoDB  │      │
│  │  ┌───────────────┐ │        │  ┌────────────────┐ │      │
│  │  │ Inverted Index│ │        │  │ User History   │ │      │
│  │  │ Fuzzy Matching│ │        │  │ Analytics Data │ │      │
│  │  │ Full-text     │ │        │  │ Metadata       │ │      │
│  │  └───────────────┘ │        │  └────────────────┘ │      │
│  └─────────────────────┘        └──────────────────────┘      │
│                                                                 │
│  ┌─────────────────────────────────────────────────────────┐  │
│  │  Trie Data Structure (In-Memory for Fast Lookups)       │  │
│  │  ┌──────────┐  ┌──────────┐  ┌──────────┐             │  │
│  │  │ Trie DB  │  │ Trie DB  │  │ Trie DB  │             │  │
│  │  │ Shard 1  │  │ Shard 2  │  │ Shard N  │             │  │
│  │  └──────────┘  └──────────┘  └──────────┘             │  │
│  └─────────────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────────────┘
                             │
                             ▼
┌─────────────────────────────────────────────────────────────────┐
│                   ANALYTICS & INDEXING                          │
│  ┌──────────────────────┐      ┌──────────────────────┐        │
│  │  Kafka Stream        │      │  Offline Processor   │        │
│  │  (Query Logs)        │──────│  - Update Frequencies│        │
│  │                      │      │  - Rebuild Trie      │        │
│  └──────────────────────┘      │  - ML Ranking        │        │
│                                └──────────────────────┘        │
└─────────────────────────────────────────────────────────────────┘

Component Responsibilities

Client Layer:

• User input handling
• Debouncing user input
• Local caching
• Rendering suggestions

API Gateway:

• Load balancing
• Rate limiting (prevent abuse)
• Request routing
• Authentication/Authorization

Autocomplete Service:

• Query processing
• Prefix matching
• Ranking logic
• Response formatting

Caching Layer:

• Hot query caching
• User-specific cache
• Reduce database load

Data Layer:

• Persistent storage
• Trie data structure
• Search index
• User history

Analytics:

• Query logging
• Popularity tracking
• Trie updates
• ML-based ranking

---

3. Component Architecture (Frontend)

Frontend Component Breakdown

┌─────────────────────────────────────────────────────────────────┐
│                    AutocompleteComponent                        │
│  ┌───────────────────────────────────────────────────────────┐ │
│  │  State Management                                         │ │
│  │  - inputValue: string                                     │ │
│  │  - suggestions: Array<Suggestion>                         │ │
│  │  - selectedIndex: number                                  │ │
│  │  - loading: boolean                                       │ │
│  │  - error: Error | null                                    │ │
│  └───────────────────────────────────────────────────────────┘ │
│                                                                 │
│  ┌───────────────────────────────────────────────────────────┐ │
│  │  Input Handler                                            │ │
│  │  ┌─────────────┐      ┌──────────────┐                   │ │
│  │  │ onChange()  │──────│ Debouncer    │                   │ │
│  │  └─────────────┘      │ (300ms)      │                   │ │
│  │                       └──────┬───────┘                   │ │
│  │  ┌─────────────┐            │                            │ │
│  │  │ onKeyDown() │            ▼                            │ │
│  │  │ - Arrow Up  │      ┌──────────────┐                   │ │
│  │  │ - Arrow Down│      │ fetchSuggest │                   │ │
│  │  │ - Enter     │      │  ions()      │                   │ │
│  │  │ - Escape    │      └──────────────┘                   │ │
│  │  └─────────────┘                                          │ │
│  └───────────────────────────────────────────────────────────┘ │
│                                                                 │
│  ┌───────────────────────────────────────────────────────────┐ │
│  │  Caching Layer (Client-side)                              │ │
│  │  ┌──────────────────────────────────────────────────────┐│ │
│  │  │  LRU Cache (Map)                                     ││ │
│  │  │  Key: query prefix                                   ││ │
│  │  │  Value: { suggestions, timestamp, ttl: 5min }        ││ │
│  │  │  Max Size: 100 entries                               ││ │
│  │  └──────────────────────────────────────────────────────┘│ │
│  │  ┌──────────────────────────────────────────────────────┐│ │
│  │  │  Session Storage                                     ││ │
│  │  │  - Recent searches (last 10)                         ││ │
│  │  │  - User preferences                                  ││ │
│  │  └──────────────────────────────────────────────────────┘│ │
│  └───────────────────────────────────────────────────────────┘ │
│                                                                 │
│  ┌───────────────────────────────────────────────────────────┐ │
│  │  API Service                                              │ │
│  │  ┌──────────────────────────────────────────────────────┐│ │
│  │  │  async fetchSuggestions(query, abortSignal)         ││ │
│  │  │  - Check cache first                                 ││ │
│  │  │  - Make HTTP request                                 ││ │
│  │  │  - Handle cancellation (AbortController)             ││ │
│  │  │  - Update cache on success                           ││ │
│  │  │  - Error handling                                    ││ │
│  │  └──────────────────────────────────────────────────────┘│ │
│  └───────────────────────────────────────────────────────────┘ │
│                                                                 │
│  ┌───────────────────────────────────────────────────────────┐ │
│  │  Rendering Layer                                          │ │
│  │  ┌────────────────────────────────────────┐              │ │
│  │  │  <SearchInput />                       │              │ │
│  │  │  - Controlled input                    │              │ │
│  │  │  - Autocomplete="off"                  │              │ │
│  │  │  - ARIA attributes                     │              │ │
│  │  └────────────────────────────────────────┘              │ │
│  │  ┌────────────────────────────────────────┐              │ │
│  │  │  <SuggestionList />                    │              │ │
│  │  │  - Virtual scrolling (if needed)       │              │ │
│  │  │  - Highlighted text matching           │              │ │
│  │  │  - Keyboard navigation                 │              │ │
│  │  │  - Click/Enter selection               │              │ │
│  │  └────────────────────────────────────────┘              │ │
│  │  ┌────────────────────────────────────────┐              │ │
│  │  │  <LoadingSpinner />                    │              │ │
│  │  └────────────────────────────────────────┘              │ │
│  │  ┌────────────────────────────────────────┐              │ │
│  │  │  <ErrorMessage />                      │              │ │
│  │  └────────────────────────────────────────┘              │ │
│  └───────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Key Frontend Components

1. AutocompleteInput Component

// Core state and logic
{
  inputValue: "",
  suggestions: [],
  selectedIndex: -1,
  loading: false,
  error: null,
  showDropdown: false
}

2. Custom Hooks

• useDebounce(value, delay) - Debounce input changes
• useAutocomplete(apiEndpoint) - Core autocomplete logic
• useCache(cacheKey, ttl) - Client-side caching
• useKeyboardNavigation() - Arrow keys, Enter, Escape

3. Utilities

• highlightMatch(text, query) - Highlight matching portions
• fetchWithTimeout(url, timeout) - Network request with timeout
• LRUCache - Client-side cache implementation

---

4. Data Flow (Search As You Type)

Complete User Journey

User Types "face" → Want to search "facebook"
═══════════════════════════════════════════════

Step 1: User Input "f"
──────────────────────
┌──────────┐
│  User    │  Types: "f"
└────┬─────┘
     │
     ▼
┌─────────────────┐
│  Input Handler  │  onChange("f")
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│   Debouncer     │  Wait 300ms... (user still typing)
└─────────────────┘  Cancel if new input


Step 2: User Input "fa"
──────────────────────
┌──────────┐
│  User    │  Types: "fa"
└────┬─────┘
     │
     ▼
┌─────────────────┐
│  Input Handler  │  onChange("fa")
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│   Debouncer     │  Reset timer, Wait 300ms...
└─────────────────┘  Cancel previous request


Step 3: User Input "fac"
──────────────────────
┌──────────┐
│  User    │  Types: "fac"
└────┬─────┘
     │
     ▼
┌─────────────────┐
│  Input Handler  │  onChange("fac")
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│   Debouncer     │  Reset timer, Wait 300ms...
└─────────────────┘


Step 4: User Input "face" (stops typing)
──────────────────────────────────────────
┌──────────┐
│  User    │  Types: "face" → Stops
└────┬─────┘
     │
     ▼
┌─────────────────┐
│  Input Handler  │  onChange("face")
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│   Debouncer     │  300ms elapsed! Trigger fetch
└────┬────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Check Client Cache                     │
│  LRUCache.get("face")                   │
│  - If found & not expired → Return      │
│  - If not found → Continue              │
└────┬────────────────────────────────────┘
     │ (Cache Miss)
     ▼
┌─────────────────────────────────────────┐
│  API Request                            │
│  GET /api/autocomplete?q=face&limit=10  │
│  Headers: { userId, sessionId }         │
└────┬────────────────────────────────────┘
     │
     │  ╔══════════════════════════════════╗
     │  ║      NETWORK TRANSMISSION        ║
     │  ╚══════════════════════════════════╝
     │
     ▼
┌─────────────────────────────────────────┐
│  Load Balancer                          │
│  - Route to available server            │
│  - Check rate limit                     │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Autocomplete Service                   │
│  Step 1: Normalize query                │
│    - "face" → lowercase                 │
│    - Trim whitespace                    │
│    - Remove special chars               │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Step 2: Check Redis Cache              │
│  Key: "autocomplete:face"               │
│  - If found → Return (90% hit rate)     │
│  - If not found → Query data layer      │
└────┬────────────────────────────────────┘
     │ (Cache Miss)
     ▼
┌─────────────────────────────────────────┐
│  Step 3: Query Data Layer               │
│                                         │
│  Option A: Trie Lookup                  │
│  ┌─────────────────────────────────┐   │
│  │  root                           │   │
│  │   └─ f (freq: 10000)            │   │
│  │       └─ a (freq: 8000)         │   │
│  │           └─ c (freq: 6000)     │   │
│  │               └─ e (freq: 5000) │   │
│  │  - Traverse to "face"           │   │
│  │  - Get all children nodes       │   │
│  │  - Return top K by frequency    │   │
│  └─────────────────────────────────┘   │
│                                         │
│  Option B: Elasticsearch Query          │
│  {                                      │
│    "query": {                           │
│      "prefix": { "term": "face" }       │
│    },                                   │
│    "sort": [{"frequency": "desc"}],     │
│    "size": 10                           │
│  }                                      │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Step 4: Ranking & Personalization      │
│  - Base score: frequency                │
│  - Boost: user history match            │
│  - Boost: trending queries              │
│  - Boost: location relevance            │
│  - Apply business rules                 │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Step 5: Format Response                │
│  {                                      │
│    "suggestions": [                     │
│      {                                  │
│        "text": "facebook",              │
│        "score": 9500,                   │
│        "type": "popular"                │
│      },                                 │
│      {                                  │
│        "text": "face recognition",      │
│        "score": 7200,                   │
│        "type": "trending"               │
│      },                                 │
│      ...                                │
│    ],                                   │
│    "query": "face",                     │
│    "latency": 45                        │
│  }                                      │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Step 6: Update Redis Cache             │
│  SET "autocomplete:face" [...]          │
│  EXPIRE 3600 (1 hour)                   │
└────┬────────────────────────────────────┘
     │
     │  ╔══════════════════════════════════╗
     │  ║      NETWORK TRANSMISSION        ║
     │  ╚══════════════════════════════════╝
     │
     ▼
┌─────────────────────────────────────────┐
│  Client Receives Response               │
│  - Latency: ~50-150ms                   │
│  - Status: 200 OK                       │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Update Client Cache                    │
│  LRUCache.set("face", {                 │
│    suggestions: [...],                  │
│    timestamp: Date.now(),               │
│    ttl: 300000                          │
│  })                                     │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Update UI State                        │
│  setState({                             │
│    suggestions: [...],                  │
│    loading: false,                      │
│    showDropdown: true                   │
│  })                                     │
└────┬────────────────────────────────────┘
     │
     ▼
┌─────────────────────────────────────────┐
│  Render Suggestions                     │
│  ┌───────────────────────────────────┐ │
│  │ 🔍 Search: face                   │ │
│  ├───────────────────────────────────┤ │
│  │ 📱 facebook                       │ │
│  │ 🔥 face recognition               │ │
│  │ 👤 facebook login                 │ │
│  │ 📸 face filters                   │ │
│  │ 🎭 face swap                      │ │
│  └───────────────────────────────────┘ │
└─────────────────────────────────────────┘

Subsequent Request Flow (Cache Hit)

User types "faceb"
─────────────────

Client Cache Check
─────────────────
Query: "faceb"
Previous cached: "face" → ["facebook", ...]

Strategy:
1. Check exact match cache: "faceb" → Not found
2. Check prefix cache: "face" → Found!
3. Filter client-side: suggestions starting with "faceb"
4. If filtered results >= 3 → Show immediately
5. Still make API call in background (for fresher results)

Time saved: ~100-150ms (no network roundtrip)

---

5. API Design & Communication Protocols

API Endpoints

1. Get Autocomplete Suggestions

GET /api/v1/autocomplete

Query Parameters:

{
  q: string,              // Query string (required)
  limit: number,          // Max results (default: 10, max: 20)
  type?: string,          // Filter type: 'query' | 'product' | 'user'
  userId?: string,        // For personalization
  sessionId?: string,     // Track user session
  location?: string,      // Geographic location
  language?: string       // Preferred language (default: 'en')
}

Request Example:

GET /api/v1/autocomplete?q=face&limit=10&userId=user123&type=query

Response Schema:

{
  "success": true,
  "data": {
    "query": "face",
    "suggestions": [
      {
        "text": "facebook",
        "displayText": "Facebook",
        "score": 9500,
        "type": "popular",        // 'popular' | 'trending' | 'recent' | 'personalized'
        "metadata": {
          "category": "social-media",
          "icon": "https://cdn.example.com/facebook-icon.png"
        }
      },
      {
        "text": "face recognition",
        "displayText": "Face Recognition",
        "score": 7200,
        "type": "trending"
      }
    ],
    "total": 10,
    "latency": 45              // Server processing time (ms)
  },
  "metadata": {
    "timestamp": "2025-12-22T10:30:45Z",
    "version": "v1",
    "cached": false
  }
}

Error Response:

{
  "success": false,
  "error": {
    "code": "INVALID_QUERY",
    "message": "Query must be at least 1 character",
    "details": {}
  },
  "metadata": {
    "timestamp": "2025-12-22T10:30:45Z"
  }
}

2. Track User Selection

POST /api/v1/autocomplete/track

Request Body:

{
  "query": "face",
  "selectedSuggestion": "facebook",
  "position": 0,              // Position in suggestion list
  "userId": "user123",
  "sessionId": "session456",
  "timestamp": "2025-12-22T10:30:45Z"
}

Purpose: Track click-through rate, improve ranking

3. Get Recent Searches

GET /api/v1/autocomplete/recent?userId=user123&limit=10

Response:

{
  "success": true,
  "data": {
    "searches": [
      {
        "query": "facebook",
        "timestamp": "2025-12-22T10:30:45Z"
      },
      {
        "query": "twitter",
        "timestamp": "2025-12-22T09:15:30Z"
      }
    ]
  }
}

4. Get Trending Searches

GET /api/v1/autocomplete/trending?location=US&limit=10

Communication Protocol: Why REST over WebSocket?

REST API Choice:

✓ Advantages:
  - Simpler implementation
  - Better caching (HTTP cache, CDN)
  - Stateless (easier to scale)
  - Request cancellation (AbortController)
  - Standard error handling
  - Works with all browsers
  - CDN compatible

✗ WebSocket Disadvantages:
  - Overkill for autocomplete
  - Complex connection management
  - Harder to cache
  - No HTTP caching benefits
  - Connection overhead
  - State management complexity

When to use WebSocket:

• Real-time collaborative editing
• Live chat applications
• Streaming updates (stock prices)
• Gaming with continuous data flow

Autocomplete is request-response → REST is ideal

Debouncing Strategy

Why Debouncing?

Without Debouncing:
User types "facebook" (8 chars) = 8 API calls
- f
- fa
- fac
- face
- faceb
- facebo
-aceboo
- facebook

With Debouncing (300ms):
User types "facebook" in 1.5s = 1-2 API calls
- Only when user pauses/stops typing

Debounce Implementation:

// Custom hook
function useDebounce(value, delay = 300) {
  const [debouncedValue, setDebouncedValue] = useState(value);

  useEffect(() => {
    const timer = setTimeout(() => {
      setDebouncedValue(value);
    }, delay);

    return () => {
      clearTimeout(timer);  // Cleanup on value change
    };
  }, [value, delay]);

  return debouncedValue;
}

// Usage
const searchQuery = "face";
const debouncedQuery = useDebounce(searchQuery, 300);

useEffect(() => {
  if (debouncedQuery.length >= minChars) {
    fetchSuggestions(debouncedQuery);
  }
}, [debouncedQuery]);

Debounce Timing Trade-offs:

Adaptive Debouncing:

// Adjust based on network speed
const getDebounceDelay = (networkSpeed) => {
  if (networkSpeed === 'slow') return 500;
  if (networkSpeed === 'fast') return 200;
  return 300;  // default
};

When to Fetch Suggestions

Fetch Triggers:

1. Minimum Character Length

   const MIN_CHARS = 2;
   if (query.length >= MIN_CHARS) {
     fetchSuggestions(query);
   }
   

   • Reduces noise
   • 1-char queries too broad
   • Better UX

2. After Debounce Delay

   // Wait 300ms after user stops typing
   const debouncedQuery = useDebounce(query, 300);
   

3. On Input Change (not on every keystroke)

   • Debounced onChange handler
   • Not onKeyDown/onKeyPress

4. Skip Fetch Conditions:

   // Don't fetch if:
   - query.length < MIN_CHARS
   - query === previousQuery (duplicate)
   - query is empty string
   - query contains only whitespace
   - Previous request for same query is pending
   

5. Request Cancellation

   useEffect(() => {
     const abortController = new AbortController();
   
     const fetchData = async () => {
       try {
         const response = await fetch(url, {
           signal: abortController.signal
         });
         // Handle response
       } catch (error) {
         if (error.name === 'AbortError') {
           // Request was cancelled (user typed more)
           return;
         }
       }
     };
   
     fetchData();
   
     return () => {
       abortController.abort();  // Cancel on cleanup
     };
   }, [debouncedQuery]);
   

Fetch Optimization Flow:

User Input → Validate → Debounce → Cache Check → Fetch
                                        ↓
                                    Cache Hit?
                                    ├─ Yes → Return
                                    └─ No → API Call

---

6. Database Design

Comparison: Trie vs Elasticsearch vs Redis

Recommended Architecture: Hybrid Approach

┌─────────────────────────────────────────────────────────────┐
│                     Query Flow                              │
└─────────────────────────────────────────────────────────────┘

Request: "face"
     │
     ▼
┌─────────────────────┐
│  Layer 1: Redis     │  Check hot cache (90% hit rate)
│  (Distributed Cache)│  - Popular queries
└────┬────────────────┘  - Recent queries
     │                   - TTL: 1 hour
     │ Cache Miss
     ▼
┌─────────────────────┐
│  Layer 2: Trie      │  Fast prefix matching
│  (In-Memory Index)  │  - Top 10M queries
└────┬────────────────┘  - Updated daily
     │                   - Sharded by first char
     │ Not Found / Long Tail
     ▼
┌─────────────────────┐
│ Layer 3: Elastic    │  Full-text search
│ (Distributed Search)│  - All queries
└─────────────────────┘  - Fuzzy matching
                         - Complex ranking

Data Model: Trie Structure

Trie Node Structure:

class TrieNode {
  constructor() {
    this.children = new Map();      // Map<char, TrieNode>
    this.isEndOfWord = false;
    this.frequency = 0;              // How many times searched
    this.suggestions = [];           // Top K suggestions from this node
    this.metadata = {
      lastUpdated: Date,
      category: String,
      trending: Boolean
    };
  }
}

Trie Example:

Query: "face" → ["facebook", "face recognition", "facebook login"]

Trie Structure:
                    root
                     |
                     f (freq: 10000, suggestions: ["facebook",...])
                     |
                     a (freq: 8000)
                     |
                     c (freq: 6000)
                     |
                     e (freq: 5000, isEnd: true)
                    /|\
                   / | \
                  b  r  s
                  |  |  |
                  o  e  w
                  |  |  |
                  o  c  a
                  |  |  |
                  k  o  p
                  |  |
                  * (facebook)
                     |
                     g
                     |
                  (face recognition)

Optimized Trie: Store Top K at Each Node

// At node 'face':
node.suggestions = [
  { text: "facebook", score: 9500 },
  { text: "face recognition", score: 7200 },
  { text: "facebook login", score: 6800 },
  // ... top 10 suggestions
];

// Benefit: O(1) retrieval instead of full traversal

Data Model: Elasticsearch

Index Schema:

{
  "settings": {
    "number_of_shards": 5,
    "number_of_replicas": 2,
    "analysis": {
      "analyzer": {
        "autocomplete_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "edge_ngram"]
        }
      },
      "filter": {
        "edge_ngram": {
          "type": "edge_ngram",
          "min_gram": 2,
          "max_gram": 20
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "query": {
        "type": "text",
        "analyzer": "autocomplete_analyzer",
        "fields": {
          "keyword": {
            "type": "keyword"
          }
        }
      },
      "frequency": {
        "type": "long"
      },
      "score": {
        "type": "float"
      },
      "category": {
        "type": "keyword"
      },
      "trending": {
        "type": "boolean"
      },
      "created_at": {
        "type": "date"
      },
      "last_searched": {
        "type": "date"
      },
      "user_count": {
        "type": "long"
      },
      "metadata": {
        "type": "object",
        "enabled": false
      }
    }
  }
}

Query Example:

{
  "query": {
    "bool": {
      "must": [
        {
          "prefix": {
            "query": "face"
          }
        }
      ],
      "should": [
        {
          "term": {
            "trending": {
              "value": true,
              "boost": 2.0
            }
          }
        }
      ]
    }
  },
  "sort": [
    { "_score": "desc" },
    { "frequency": "desc" }
  ],
  "size": 10
}

Data Model: PostgreSQL (User Data)

Schema:

-- User Search History
CREATE TABLE user_search_history (
  id BIGSERIAL PRIMARY KEY,
  user_id VARCHAR(255) NOT NULL,
  query VARCHAR(500) NOT NULL,
  selected_suggestion VARCHAR(500),
  position INTEGER,
  session_id VARCHAR(255),
  created_at TIMESTAMP DEFAULT NOW(),

  INDEX idx_user_id (user_id),
  INDEX idx_created_at (created_at),
  INDEX idx_user_created (user_id, created_at DESC)
);

-- Query Analytics
CREATE TABLE query_analytics (
  id BIGSERIAL PRIMARY KEY,
  query VARCHAR(500) NOT NULL UNIQUE,
  frequency BIGINT DEFAULT 1,
  user_count BIGINT DEFAULT 1,
  click_through_rate DECIMAL(5,4),
  last_searched TIMESTAMP,
  trending_score DECIMAL(10,2),
  category VARCHAR(100),
  metadata JSONB,

  INDEX idx_frequency (frequency DESC),
  INDEX idx_trending (trending_score DESC),
  INDEX idx_category (category)
);

-- Optimize for read-heavy workload
-- Use read replicas for analytics
-- Partition by time for search history

Data Update Strategy

Real-time Updates (Hot Path):

User Search → Log to Kafka → Update Redis (increment frequency)
                           → Update Elasticsearch (async)

Batch Updates (Cold Path):

Every Hour:
  - Aggregate query frequencies from Kafka
  - Update trending scores
  - Rebuild top suggestions in Trie

Every Day:
  - Full Trie rebuild from aggregated data
  - Update Elasticsearch index
  - Clean up old data

Trie Update Flow:

┌──────────────┐      ┌──────────────┐      ┌──────────────┐
│ Query Logs   │──────│ Aggregation  │──────│ Trie Builder │
│ (Kafka)      │      │ (Spark/Flink)│      │ (Background) │
└──────────────┘      └──────────────┘      └──────┬───────┘
                                                    │
                                                    ▼
                                            ┌──────────────┐
                                            │ New Trie     │
                                            │ Snapshot     │
                                            └──────┬───────┘
                                                    │
                                            Atomic Swap
                                                    │
                                                    ▼
                                            ┌──────────────┐
                                            │ Active Trie  │
                                            │ (Serving)    │
                                            └──────────────┘

---

7. Caching Strategy

Multi-Layer Caching Architecture

┌─────────────────────────────────────────────────────────────┐
│                    Caching Layers                           │
└─────────────────────────────────────────────────────────────┘

Request: "facebook"

Layer 1: Browser Memory Cache (Client-side)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ LRU Cache (JavaScript Map/Object)   │
│ - Size: 100 entries                 │
│ - TTL: 5 minutes                    │
│ - Hit Rate: 30-40%                  │
│ - Latency: <1ms                     │
└─────────────────────────────────────┘
         │
         │ Cache Miss
         ▼
Layer 2: Service Worker Cache (Client-side)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ Cache API (IndexedDB)               │
│ - Size: 50MB                        │
│ - TTL: 1 hour                       │
│ - Hit Rate: 10-15%                  │
│ - Latency: 5-10ms                   │
└─────────────────────────────────────┘
         │
         │ Cache Miss
         ▼
Layer 3: CDN Cache (Edge)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ CloudFlare / Akamai                 │
│ - Geographic distribution           │
│ - TTL: 10 minutes                   │
│ - Hit Rate: 20-30%                  │
│ - Latency: 10-50ms                  │
└─────────────────────────────────────┘
         │
         │ Cache Miss
         ▼
Layer 4: Redis Cache (Application)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ Redis Cluster                       │
│ - Size: Unlimited (LRU eviction)    │
│ - TTL: 1 hour (hot), 24h (warm)     │
│ - Hit Rate: 85-90%                  │
│ - Latency: 1-5ms                    │
└─────────────────────────────────────┘
         │
         │ Cache Miss
         ▼
Layer 5: In-Memory Trie (Application)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ Trie Data Structure                 │
│ - Size: Top 10M queries             │
│ - No expiry (updated daily)         │
│ - Hit Rate: 80-90%                  │
│ - Latency: <1ms                     │
└─────────────────────────────────────┘
         │
         │ Not in Top 10M
         ▼
Layer 6: Elasticsearch (Database)
──────────────────────────────────────────
┌─────────────────────────────────────┐
│ Full Query Index                    │
│ - All queries                       │
│ - Latency: 20-100ms                 │
└─────────────────────────────────────┘

Client-Side Cache Implementation

LRU Cache Class:

class LRUCache {
  constructor(maxSize = 100) {
    this.maxSize = maxSize;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return null;
    }

    const value = this.cache.get(key);

    // Check TTL
    if (Date.now() - value.timestamp > value.ttl) {
      this.cache.delete(key);
      return null;
    }

    // Move to end (most recently used)
    this.cache.delete(key);
    this.cache.set(key, value);

    return value.data;
  }

  set(key, data, ttl = 300000) {  // 5 min default
    // Remove oldest if at capacity
    if (this.cache.size >= this.maxSize) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }

    this.cache.set(key, {
      data,
      timestamp: Date.now(),
      ttl
    });
  }

  clear() {
    this.cache.clear();
  }

  size() {
    return this.cache.size;
  }
}

// Usage
const cache = new LRUCache(100);

async function fetchSuggestions(query) {
  // Check cache first
  const cached = cache.get(query);
  if (cached) {
    console.log('Cache hit!');
    return cached;
  }

  // Fetch from API
  const response = await fetch(`/api/autocomplete?q=${query}`);
  const data = await response.json();

  // Store in cache
  cache.set(query, data.suggestions, 300000);  // 5 min

  return data.suggestions;
}

Prefix Cache Strategy:

// Smart caching: Use prefix results for longer queries
function getFromCacheWithPrefix(query) {
  // Exact match
  let cached = cache.get(query);
  if (cached) return cached;

  // Try prefixes (from longest to shortest)
  for (let i = query.length - 1; i >= 2; i--) {
    const prefix = query.substring(0, i);
    cached = cache.get(prefix);

    if (cached) {
      // Filter results client-side
      const filtered = cached.filter(item =>
        item.text.startsWith(query)
      );

      if (filtered.length >= 3) {
        return filtered;  // Good enough
      }
    }
  }

  return null;
}

// Example:
// Cache has: "face" → ["facebook", "face recognition", ...]
// User types: "faceb"
// Instead of API call, filter cached "face" results
// Result: ["facebook"]

Server-Side Cache Strategy (Redis)

Cache Key Design:

// Basic cache key
const cacheKey = `autocomplete:${query}`;

// With parameters
const cacheKey = `autocomplete:${query}:${type}:${location}`;

// User-specific cache
const userCacheKey = `autocomplete:user:${userId}:recent`;
const trendingCacheKey = `autocomplete:trending:${location}:${date}`;

Redis Caching Pattern:

async function getSuggestions(query, options = {}) {
  const cacheKey = `autocomplete:${query}`;

  // Try Redis cache first
  const cached = await redis.get(cacheKey);
  if (cached) {
    return JSON.parse(cached);
  }

  // Cache miss - query database
  const results = await queryDatabase(query, options);

  // Determine TTL based on query popularity
  let ttl = 3600;  // 1 hour default

  if (results.frequency > 10000) {
    ttl = 86400;  // 24 hours for very popular
  } else if (results.frequency < 100) {
    ttl = 600;    // 10 minutes for rare queries
  }

  // Store in Redis
  await redis.setex(cacheKey, ttl, JSON.stringify(results));

  return results;
}

Cache Warming Strategy:

// Warm cache on startup with popular queries
async function warmCache() {
  const popularQueries = await getTopQueries(1000);

  for (const query of popularQueries) {
    const results = await queryDatabase(query.text);
    await redis.setex(
      `autocomplete:${query.text}`,
      86400,  // 24 hours
      JSON.stringify(results)
    );
  }
}

// Schedule cache warming
cron.schedule('0 */6 * * *', warmCache);  // Every 6 hours

Cache Invalidation Strategy:

Strategies:
1. TTL-based (Time to Live)
   - Simple, automatic
   - May serve stale data
   - Good for autocomplete

2. Event-based invalidation
   - Invalidate on data update
   - Complex to implement
   - Needed for critical data

3. Versioned cache keys
   - Include version in key
   - Easy rollback
   - Higher memory usage

Recommended for Autocomplete: TTL-based
- Queries don't change frequently
- Stale data acceptable for minutes
- Simple implementation

Redis Cache Structure:

Redis Keys:

1. Suggestion Cache
   Key: "autocomplete:{query}"
   Value: JSON array of suggestions
   TTL: 1-24 hours (based on popularity)

2. User Recent Searches
   Key: "user:{userId}:recent"
   Type: List (LPUSH/LRANGE)
   Value: ["query1", "query2", ...]
   TTL: 30 days
   Max size: 50 items

3. Trending Queries
   Key: "trending:{location}:{date}"
   Type: Sorted Set
   Value: {query: score}
   TTL: 1 hour

4. Query Frequency
   Key: "frequency:{query}"
   Type: String (counter)
   Value: Number
   TTL: Never (updated continuously)

Cache Consistency

Write-Through Cache:

async function incrementQueryFrequency(query) {
  // Update database
  await db.query(
    'UPDATE query_analytics SET frequency = frequency + 1 WHERE query = ?',
    [query]
  );

  // Update cache
  await redis.incr(`frequency:${query}`);

  // Invalidate suggestion cache (will be regenerated)
  await redis.del(`autocomplete:${query}`);
}

Cache Stampede Prevention:

async function getSuggestionsWithLock(query) {
  const cacheKey = `autocomplete:${query}`;
  const lockKey = `lock:${cacheKey}`;

  // Try cache first
  let cached = await redis.get(cacheKey);
  if (cached) return JSON.parse(cached);

  // Acquire lock to prevent stampede
  const lockAcquired = await redis.set(
    lockKey,
    '1',
    'EX', 10,  // 10 second expiry
    'NX'       // Only if not exists
  );

  if (lockAcquired) {
    try {
      // This request will compute the value
      const results = await queryDatabase(query);
      await redis.setex(cacheKey, 3600, JSON.stringify(results));
      return results;
    } finally {
      await redis.del(lockKey);
    }
  } else {
    // Another request is computing, wait and retry
    await sleep(100);
    cached = await redis.get(cacheKey);
    if (cached) return JSON.parse(cached);

    // Fallback to database
    return await queryDatabase(query);
  }
}

---

8. State Management

Component State Architecture

Local State (React Component):

function AutocompleteComponent() {
  // UI State
  const [inputValue, setInputValue] = useState('');
  const [selectedIndex, setSelectedIndex] = useState(-1);
  const [showDropdown, setShowDropdown] = useState(false);

  // Data State
  const [suggestions, setSuggestions] = useState([]);
  const [loading, setLoading] = useState(false);
  const [error, setError] = useState(null);

  // Cache State
  const cacheRef = useRef(new LRUCache(100));
  const abortControllerRef = useRef(null);

  // Debounced value
  const debouncedQuery = useDebounce(inputValue, 300);

  // Effects and handlers...
}

State Flow Diagram:

┌─────────────────────────────────────────────────────────┐
│                   State Management                      │
└─────────────────────────────────────────────────────────┘

User Input
    │
    ▼
┌─────────────────┐
│ inputValue      │  "face"
│ (controlled)    │
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│ useDebounce     │  Wait 300ms...
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│ debouncedQuery  │  "face" (after delay)
└────┬────────────┘
     │
     ▼
┌─────────────────┐
│ useEffect       │  Trigger on debouncedQuery change
└────┬────────────┘
     │
     ├─► setLoading(true)
     │   setError(null)
     │
     ▼
┌─────────────────┐
│ fetchSuggestions│
└────┬────────────┘
     │
     ├─► Success
     │   ├─► setSuggestions([...])
     │   ├─► setLoading(false)
     │   └─► setShowDropdown(true)
     │
     └─► Error
         ├─► setError(error)
         ├─► setLoading(false)
         └─► setShowDropdown(false)

Global State (Context/Redux)

Context API Approach:

// AutocompleteContext.js
const AutocompleteContext = createContext();

function AutocompleteProvider({ children }) {
  const [recentSearches, setRecentSearches] = useState([]);
  const [userPreferences, setUserPreferences] = useState({
    maxSuggestions: 10,
    enableFuzzy: true,
    showRecent: true
  });

  const addRecentSearch = useCallback((query) => {
    setRecentSearches(prev => {
      const updated = [query, ...prev.filter(q => q !== query)];
      return updated.slice(0, 50);  // Keep last 50
    });

    // Persist to localStorage
    localStorage.setItem('recentSearches', JSON.stringify(updated));
  }, []);

  const value = {
    recentSearches,
    addRecentSearch,
    userPreferences,
    setUserPreferences
  };

  return (
    <AutocompleteContext.Provider value={value}>
      {children}
    </AutocompleteContext.Provider>
  );
}

// Hook
function useAutocomplete() {
  const context = useContext(AutocompleteContext);
  if (!context) {
    throw new Error('useAutocomplete must be used within AutocompleteProvider');
  }
  return context;
}

Redux Approach (for complex apps):

// store/autocompleteSlice.js
const autocompleteSlice = createSlice({
  name: 'autocomplete',
  initialState: {
    queries: {},           // { "face": { suggestions: [...], timestamp: ... } }
    recentSearches: [],
    trending: [],
    loading: {},           // { "face": true }
    errors: {}
  },
  reducers: {
    fetchSuggestionsStart: (state, action) => {
      const { query } = action.payload;
      state.loading[query] = true;
      state.errors[query] = null;
    },
    fetchSuggestionsSuccess: (state, action) => {
      const { query, suggestions } = action.payload;
      state.queries[query] = {
        suggestions,
        timestamp: Date.now()
      };
      state.loading[query] = false;
    },
    fetchSuggestionsFailure: (state, action) => {
      const { query, error } = action.payload;
      state.errors[query] = error;
      state.loading[query] = false;
    },
    addRecentSearch: (state, action) => {
      const query = action.payload;
      state.recentSearches = [
        query,
        ...state.recentSearches.filter(q => q !== query)
      ].slice(0, 50);
    }
  }
});

// Thunk for async logic
export const fetchSuggestions = (query) => async (dispatch, getState) => {
  // Check if already loading
  if (getState().autocomplete.loading[query]) {
    return;
  }

  dispatch(fetchSuggestionsStart({ query }));

  try {
    const response = await api.getSuggestions(query);
    dispatch(fetchSuggestionsSuccess({
      query,
      suggestions: response.data.suggestions
    }));
  } catch (error) {
    dispatch(fetchSuggestionsFailure({ query, error: error.message }));
  }
};

Persistence Strategy

localStorage for Recent Searches:

// Save to localStorage
function saveRecentSearches(searches) {
  try {
    localStorage.setItem('recentSearches', JSON.stringify(searches));
  } catch (error) {
    console.error('Failed to save recent searches:', error);
  }
}

// Load from localStorage
function loadRecentSearches() {
  try {
    const stored = localStorage.getItem('recentSearches');
    return stored ? JSON.parse(stored) : [];
  } catch (error) {
    console.error('Failed to load recent searches:', error);
    return [];
  }
}

// Clear old data (older than 30 days)
function cleanupOldSearches() {
  const searches = loadRecentSearches();
  const thirtyDaysAgo = Date.now() - (30 * 24 * 60 * 60 * 1000);

  const cleaned = searches.filter(item =>
    item.timestamp > thirtyDaysAgo
  );

  saveRecentSearches(cleaned);
}

SessionStorage for Temporary Data:

// Store current session suggestions
sessionStorage.setItem('currentSuggestions', JSON.stringify(suggestions));

// Cleared when browser tab closes

State Synchronization

Sync with Server:

// Periodically sync recent searches with server
useEffect(() => {
  const syncInterval = setInterval(async () => {
    const recentSearches = loadRecentSearches();

    if (recentSearches.length > 0) {
      await api.syncRecentSearches({
        userId,
        searches: recentSearches
      });
    }
  }, 5 * 60 * 1000);  // Every 5 minutes

  return () => clearInterval(syncInterval);
}, [userId]);

Optimistic Updates:

function handleSelectSuggestion(suggestion) {
  // Update UI immediately (optimistic)
  setRecentSearches(prev => [suggestion, ...prev]);

  // Sync with server in background
  api.trackSelection(suggestion)
    .catch(error => {
      // Rollback on error
      setRecentSearches(prev => prev.filter(s => s !== suggestion));
      console.error('Failed to track selection:', error);
    });
}

---

9. Performance Optimization

Frontend Optimizations

1. Debouncing (Already Covered)

// Reduce API calls by 80-90%
const debouncedQuery = useDebounce(inputValue, 300);

2. Request Cancellation

useEffect(() => {
  const abortController = new AbortController();

  async function fetchData() {
    try {
      const response = await fetch(url, {
        signal: abortController.signal
      });
      // Process response
    } catch (error) {
      if (error.name === 'AbortError') {
        console.log('Request cancelled');
        return;
      }
      setError(error);
    }
  }

  if (debouncedQuery.length >= 2) {
    fetchData();
  }

  // Cleanup: Cancel previous request
  return () => {
    abortController.abort();
  };
}, [debouncedQuery]);

3. Memoization

// Memoize expensive computations
const highlightedSuggestions = useMemo(() => {
  return suggestions.map(suggestion => ({
    ...suggestion,
    highlighted: highlightMatch(suggestion.text, inputValue)
  }));
}, [suggestions, inputValue]);

// Memoize callback functions
const handleSelectSuggestion = useCallback((suggestion) => {
  setInputValue(suggestion.text);
  setShowDropdown(false);
  addRecentSearch(suggestion.text);
  onSearch(suggestion.text);
}, [onSearch, addRecentSearch]);

4. Virtual Scrolling (for large lists)

import { FixedSizeList } from 'react-window';

function SuggestionList({ suggestions }) {
  const Row = ({ index, style }) => (
    <div style={style} className="suggestion-item">
      {suggestions[index].text}
    </div>
  );

  return (
    <FixedSizeList
      height={400}
      itemCount={suggestions.length}
      itemSize={50}
      width="100%"
    >
      {Row}
    </FixedSizeList>
  );
}

5. Lazy Loading Icons/Images

function SuggestionItem({ suggestion }) {
  const [imageSrc, setImageSrc] = useState(null);

  useEffect(() => {
    // Load image only when needed
    const img = new Image();
    img.src = suggestion.icon;
    img.onload = () => setImageSrc(suggestion.icon);
  }, [suggestion.icon]);

  return (
    <div className="suggestion">
      {imageSrc ? (
        <img src={imageSrc} alt="" loading="lazy" />
      ) : (
        <div className="placeholder" />
      )}
      <span>{suggestion.text}</span>
    </div>
  );
}

6. Code Splitting

// Lazy load autocomplete component
const Autocomplete = lazy(() => import('./Autocomplete'));

function App() {
  return (
    <Suspense fallback={<div>Loading...</div>}>
      <Autocomplete />
    </Suspense>
  );
}

7. Throttle Rendering

// Limit re-renders during rapid typing
const [renderKey, setRenderKey] = useState(0);

const throttledRender = useCallback(
  throttle(() => {
    setRenderKey(k => k + 1);
  }, 100),
  []
);

useEffect(() => {
  throttledRender();
}, [suggestions, throttledRender]);

Backend Optimizations

1. Database Query Optimization

// Bad: Full table scan
SELECT * FROM queries WHERE query LIKE 'face%' ORDER BY frequency DESC LIMIT 10;

// Good: Index on query + frequency
CREATE INDEX idx_query_frequency ON queries(query, frequency DESC);
SELECT query, frequency FROM queries
WHERE query >= 'face' AND query < 'facf'  -- Range scan
ORDER BY frequency DESC
LIMIT 10;

2. Elasticsearch Optimization

{
  "query": {
    "prefix": {
      "query": {
        "value": "face",
        "boost": 1.0
      }
    }
  },
  "sort": [{ "frequency": "desc" }],
  "size": 10,
  "_source": ["query", "frequency"],  // Only fetch needed fields
  "track_total_hits": false,          // Don't count total
  "timeout": "100ms"                  // Fail fast
}

3. Trie Optimization

// Store top K at each node (avoid deep traversal)
class OptimizedTrieNode {
  constructor() {
    this.children = new Map();
    this.topSuggestions = [];  // Pre-computed top 10
  }
}

// O(1) lookup instead of O(n) traversal
function getSuggestions(query) {
  const node = findNode(query);
  return node ? node.topSuggestions : [];
}

4. Parallel Processing

async function getSuggestions(query, userId) {
  // Fetch from multiple sources in parallel
  const [
    globalSuggestions,
    personalizedSuggestions,
    trendingSuggestions
  ] = await Promise.all([
    fetchGlobalSuggestions(query),
    fetchPersonalizedSuggestions(query, userId),
    fetchTrendingSuggestions(query)
  ]);

  // Merge and rank
  return mergeAndRank([
    ...globalSuggestions,
    ...personalizedSuggestions,
    ...trendingSuggestions
  ]);
}

5. Connection Pooling

// Redis connection pool
const redis = new Redis.Cluster([
  { host: 'redis-1', port: 6379 },
  { host: 'redis-2', port: 6379 }
], {
  redisOptions: {
    pool: {
      min: 10,
      max: 50
    }
  }
});

6. Compression

// Compress large responses
app.use(compression({
  filter: (req, res) => {
    if (req.headers['x-no-compression']) {
      return false;
    }
    return compression.filter(req, res);
  },
  level: 6  // Compression level (1-9)
}));

7. Response Pagination

// Instead of returning 100 suggestions
// Return top 10, allow pagination
GET /api/autocomplete?q=face&limit=10&offset=0
GET /api/autocomplete?q=face&limit=10&offset=10

Network Optimizations

1. HTTP/2 Server Push

// Push common resources
app.get('/autocomplete', (req, res) => {
  res.push('/api/trending', { /* headers */ });
  res.send(/* autocomplete response */);
});

2. Keep-Alive Connections

// Reuse TCP connections
const agent = new https.Agent({
  keepAlive: true,
  keepAliveMsecs: 1000,
  maxSockets: 50
});

fetch(url, { agent });

3. CDN for Static Assets

- Host icons/images on CDN
- Reduce latency for global users
- Offload traffic from origin servers

4. Gzip/Brotli Compression

// Enable Brotli for better compression
app.use(shrinkRay());  // Brotli compression middleware

Monitoring & Profiling

1. Performance Metrics

// Track autocomplete performance
const metrics = {
  p50: 45,   // 50th percentile latency
  p95: 120,  // 95th percentile
  p99: 250,  // 99th percentile
  cacheHitRate: 0.87,
  errorRate: 0.002
};

// Log slow requests
if (latency > 200) {
  logger.warn('Slow autocomplete request', {
    query,
    latency,
    cacheHit: false
  });
}

2. React Profiler

<Profiler id="Autocomplete" onRender={onRenderCallback}>
  <Autocomplete />
</Profiler>

function onRenderCallback(id, phase, actualDuration) {
  if (actualDuration > 16) {  // 60fps = 16ms per frame
    console.warn('Slow render:', id, actualDuration);
  }
}

3. Lighthouse Audit

- Time to Interactive (TTI) < 3s
- First Contentful Paint (FCP) < 1s
- Cumulative Layout Shift (CLS) < 0.1

---

10. Error Handling & Edge Cases

Error Scenarios & Handling

1. Network Errors

async function fetchSuggestions(query) {
  try {
    const controller = new AbortController();
    const timeoutId = setTimeout(() => controller.abort(), 5000);

    const response = await fetch(url, {
      signal: controller.signal
    });

    clearTimeout(timeoutId);

    if (!response.ok) {
      throw new Error(`HTTP ${response.status}: ${response.statusText}`);
    }

    return await response.json();

  } catch (error) {
    if (error.name === 'AbortError') {
      console.log('Request timeout');
      return { error: 'TIMEOUT', suggestions: [] };
    }

    if (!navigator.onLine) {
      console.log('No internet connection');
      return { error: 'OFFLINE', suggestions: getCachedSuggestions(query) };
    }

    console.error('Network error:', error);
    return { error: 'NETWORK_ERROR', suggestions: [] };
  }
}

2. Empty Results

function handleEmptyResults(query) {
  return {
    suggestions: [
      {
        text: `No results found for "${query}"`,
        type: 'no-results',
        action: 'show-alternative'
      },
      {
        text: 'Try different keywords',
        type: 'suggestion',
        action: 'help'
      }
    ],
    fallback: true
  };
}

// Show recent searches as fallback
function getFallbackSuggestions() {
  const recent = getRecentSearches();
  if (recent.length > 0) {
    return {
      title: 'Recent Searches',
      suggestions: recent.map(q => ({
        text: q,
        type: 'recent'
      }))
    };
  }
  return getTrendingSuggestions();
}

3. Slow Network

function useAdaptiveDebounce(networkSpeed) {
  const [debounceDelay, setDebounceDelay] = useState(300);

  useEffect(() => {
    // Detect network speed
    if (navigator.connection) {
      const effectiveType = navigator.connection.effectiveType;

      switch (effectiveType) {
        case 'slow-2g':
        case '2g':
          setDebounceDelay(800);
          break;
        case '3g':
          setDebounceDelay(500);
          break;
        case '4g':
        default:
          setDebounceDelay(300);
      }
    }
  }, []);

  return debounceDelay;
}

// Show loading state for slow requests
function AutocompleteComponent() {
  const [showSlowWarning, setShowSlowWarning] = useState(false);

  useEffect(() => {
    if (loading) {
      const timer = setTimeout(() => {
        setShowSlowWarning(true);
      }, 1000);  // Show warning after 1s

      return () => clearTimeout(timer);
    }
  }, [loading]);

  return (
    <>
      {loading && showSlowWarning && (
        <div className="slow-warning">
          Still loading... You may have a slow connection
        </div>
      )}
    </>
  );
}

4. Rate Limiting

// Server-side rate limiting
const rateLimit = require('express-rate-limit');

const autocompleteRateLimiter = rateLimit({
  windowMs: 1 * 60 * 1000,  // 1 minute
  max: 60,                   // 60 requests per minute
  message: {
    error: 'RATE_LIMIT_EXCEEDED',
    message: 'Too many requests, please try again later'
  },
  standardHeaders: true,
  legacyHeaders: false,
  // Allow bypass for authenticated users with premium
  skip: (req) => req.user?.isPremium
});

app.get('/api/autocomplete', autocompleteRateLimiter, handler);

// Client-side handling
async function fetchWithRetry(url, options = {}, maxRetries = 3) {
  for (let i = 0; i < maxRetries; i++) {
    try {
      const response = await fetch(url, options);

      if (response.status === 429) {  // Rate limited
        const retryAfter = response.headers.get('Retry-After') || 5;
        await sleep(retryAfter * 1000);
        continue;
      }

      return response;
    } catch (error) {
      if (i === maxRetries - 1) throw error;
      await sleep(Math.pow(2, i) * 1000);  // Exponential backoff
    }
  }
}

5. Invalid Input

function validateQuery(query) {
  // Remove leading/trailing whitespace
  query = query.trim();

  // Empty query
  if (query.length === 0) {
    return { valid: false, reason: 'EMPTY_QUERY' };
  }

  // Too short
  if (query.length < 2) {
    return { valid: false, reason: 'TOO_SHORT' };
  }

  // Too long
  if (query.length > 200) {
    return { valid: false, reason: 'TOO_LONG' };
  }

  // Contains only special characters
  if (!/[a-zA-Z0-9]/.test(query)) {
    return { valid: false, reason: 'INVALID_CHARACTERS' };
  }

  // SQL injection attempt
  if (/['";\\]/.test(query)) {
    return { valid: false, reason: 'SUSPICIOUS_INPUT' };
  }

  return { valid: true, query };
}

// Usage
function handleInputChange(value) {
  const validation = validateQuery(value);

  if (!validation.valid) {
    setError(validation.reason);
    setSuggestions([]);
    return;
  }

  setError(null);
  setInputValue(validation.query);
}

6. Server Errors (5xx)

async function fetchSuggestionsWithFallback(query) {
  try {
    const response = await fetch(`/api/autocomplete?q=${query}`);

    if (response.status >= 500) {
      console.error('Server error:', response.status);
      // Fall back to cached or local data
      return getCachedSuggestions(query) || getLocalSuggestions(query);
    }

    return await response.json();
  } catch (error) {
    // Network error - use local fallback
    return getLocalSuggestions(query);
  }
}

// Client-side filtering as last resort
function getLocalSuggestions(query) {
  const allCachedQueries = getAllCachedQueries();
  return allCachedQueries
    .filter(q => q.startsWith(query.toLowerCase()))
    .slice(0, 10);
}

7. Concurrent Requests

// Prevent race conditions
let latestRequestId = 0;

async function fetchSuggestions(query) {
  const requestId = ++latestRequestId;

  const response = await fetch(`/api/autocomplete?q=${query}`);
  const data = await response.json();

  // Only update if this is still the latest request
  if (requestId === latestRequestId) {
    setSuggestions(data.suggestions);
  } else {
    console.log('Ignoring stale response');
  }
}

Edge Cases

1. Special Characters

// Handle special characters in search
function escapeRegex(string) {
  return string.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
}

// Example: User types "c++"
// Server: Escape and search for "c\+\+"

2. Unicode & Emoji

// Support emoji in search
function normalizeQuery(query) {
  // Remove emoji
  const withoutEmoji = query.replace(/[\u{1F600}-\u{1F64F}]/gu, '');

  // Normalize unicode
  return withoutEmoji.normalize('NFD')
    .replace(/[\u0300-\u036f]/g, '');  // Remove accents
}

// Example: "café" → "cafe"

3. Multiple Languages

// Detect language and use appropriate index
function detectLanguage(query) {
  // Simple detection based on character ranges
  if (/[\u4E00-\u9FFF]/.test(query)) return 'zh';  // Chinese
  if (/[\u0600-\u06FF]/.test(query)) return 'ar';  // Arabic
  if (/[\u0400-\u04FF]/.test(query)) return 'ru';  // Russian
  return 'en';  // Default
}

// Route to language-specific index
const language = detectLanguage(query);
const suggestions = await searchInIndex(query, language);

4. Very Long Queries

// Truncate very long queries
const MAX_QUERY_LENGTH = 200;

function handleLongQuery(query) {
  if (query.length > MAX_QUERY_LENGTH) {
    return {
      query: query.substring(0, MAX_QUERY_LENGTH),
      warning: 'Query truncated to 200 characters'
    };
  }
  return { query };
}

5. Duplicate Suggestions

// Remove duplicates
function deduplicateSuggestions(suggestions) {
  const seen = new Set();
  return suggestions.filter(item => {
    const key = item.text.toLowerCase();
    if (seen.has(key)) return false;
    seen.add(key);
    return true;
  });
}

6. Stale Cache

// Handle stale cache gracefully
function getCachedWithValidation(key) {
  const cached = cache.get(key);

  if (cached) {
    const age = Date.now() - cached.timestamp;

    if (age > cached.ttl) {
      // Serve stale but revalidate in background
      fetchFreshData(key);
      return { ...cached, stale: true };
    }

    return cached;
  }

  return null;
}

7. User Abandonment

// Track if user abandoned autocomplete
let abandonTimer;

function handleInputFocus() {
  abandonTimer = setTimeout(() => {
    analytics.track('autocomplete_abandoned', {
      lastQuery: inputValue,
      suggestionsShown: suggestions.length
    });
  }, 30000);  // 30 seconds
}

function handleInputBlur() {
  clearTimeout(abandonTimer);
}

function handleSelectSuggestion() {
  clearTimeout(abandonTimer);
  analytics.track('autocomplete_success');
}

Graceful Degradation

Progressive Enhancement Strategy:

function AutocompleteWithFallback() {
  const [enhanced, setEnhanced] = useState(false);

  useEffect(() => {
    // Check browser capabilities
    const hasRequiredAPIs =
      'fetch' in window &&
      'Promise' in window &&
      'localStorage' in window;

    setEnhanced(hasRequiredAPIs);
  }, []);

  if (!enhanced) {
    // Basic HTML form fallback
    return (
      <form action="/search" method="get">
        <input
          type="text"
          name="q"
          placeholder="Search..."
        />
        <button type="submit">Search</button>
      </form>
    );
  }

  // Full autocomplete experience
  return <EnhancedAutocomplete />;
}

Error Boundary:

class AutocompleteErrorBoundary extends React.Component {
  constructor(props) {
    super(props);
    this.state = { hasError: false };
  }

  static getDerivedStateFromError(error) {
    return { hasError: true };
  }

  componentDidCatch(error, errorInfo) {
    console.error('Autocomplete error:', error, errorInfo);
    // Log to error tracking service
    logError(error, errorInfo);
  }

  render() {
    if (this.state.hasError) {
      // Fallback to simple input
      return (
        <input
          type="text"
          placeholder="Search (autocomplete unavailable)"
        />
      );
    }

    return this.props.children;
  }
}

// Usage
<AutocompleteErrorBoundary>
  <Autocomplete />
</AutocompleteErrorBoundary>

---

11. Interview Cross-Questions

Architecture & Design Questions

Q1: Why use a Trie instead of a simple database query with LIKE?

Answer:

Trie Advantages:
✓ O(k) time complexity (k = query length)
✓ In-memory, extremely fast (<1ms)
✓ No network latency to database
✓ Efficient prefix matching
✓ Pre-computed top suggestions at each node

Database LIKE Disadvantages:
✗ O(n) full table scan (even with index)
✗ Network latency (5-50ms)
✗ Index on VARCHAR with wildcard is inefficient
✗ Doesn't scale for millions of queries

Trade-offs:
- Trie: High memory usage (~10GB for 10M queries)
- Trie: Complex updates (need rebuild)
- Database: Lower memory, easier updates
- Database: Slower queries

Hybrid Approach:
- Trie for top 10M popular queries (90% traffic)
- Elasticsearch for long-tail queries (10% traffic)
- Best of both worlds

Q2: How would you handle typos and fuzzy matching?

Answer:

Approaches:

1. Edit Distance (Levenshtein):
   - Calculate distance between query and suggestions
   - Allow 1-2 character difference
   - Example: "facbook" → "facebook" (distance 1)
   - Time: O(n*m) per comparison
   - Works but slow

2. N-gram Matching:
   - Split into n-grams: "facebook" → ["fa", "ac", "ce", ...]
   - Match based on common n-grams
   - Elasticsearch has built-in support
   - Example: "fcebook" → shares many bigrams with "facebook"

3. Phonetic Matching:
   - Soundex/Metaphone algorithms
   - "facebook" and "fasebook" sound similar
   - Good for names

4. Prefix Tries with Wildcards:
   - Store variations in Trie
   - "facebook" → also index "facbook", "facebuk"
   - Pre-compute common typos
   - Higher storage cost

5. Machine Learning:
   - Train model on query logs
   - Learn common typo patterns
   - Context-aware corrections
   - Most accurate but complex

Recommended for Autocomplete:
- Use Elasticsearch fuzzy query
- Set fuzziness: "AUTO"
- Combined with prefix matching
- Limit fuzzy to 2 character edits

Q3: Why REST API instead of WebSocket for autocomplete?

Answer:

REST Advantages:
✓ Simpler implementation
✓ Stateless (easier horizontal scaling)
✓ HTTP caching (CDN, browser cache)
✓ Request cancellation (AbortController)
✓ Standard error handling (HTTP status codes)
✓ No connection overhead
✓ Better for intermittent requests
✓ Works behind proxies/firewalls

WebSocket Disadvantages:
✗ Persistent connection overhead
✗ Harder to cache
✗ State management complexity
✗ Connection drops require reconnection
✗ No HTTP cache benefits
✗ Overkill for request-response pattern

When WebSocket Makes Sense:
- Real-time bidirectional communication
- Server-initiated updates
- Streaming data
- Collaborative editing
- Live notifications

Autocomplete Pattern:
- Client initiates requests
- Sporadic requests (after debounce)
- Each request is independent
- Perfect for REST

Optimization:
- HTTP/2 multiplexing
- Keep-Alive connections
- Connection pooling
→ Get near-WebSocket performance with REST simplicity

Q4: How do you rank and personalize autocomplete suggestions?

Answer:

Ranking Factors:

1. Base Score (Popularity):
   score = log(frequency) × 1.0
   - Higher frequency = higher rank
   - Logarithm prevents dominance

2. Recency Boost:
   if (lastSearched < 7 days):
     score += 2.0
   - Trending queries get boost

3. User History Boost:
   if (query in userHistory):
     score += 3.0
   - Personalized suggestions rank higher

4. Click-Through Rate (CTR):
   score += (clicks / impressions) × 1.5
   - Users actually select it

5. Location Relevance:
   if (location matches):
     score += 1.5
   - Geo-specific suggestions

6. Category Match:
   if (category in userPreferences):
     score += 1.0

Final Formula:
finalScore = baseScore + recencyBoost + personalBoost + ctrBoost + locationBoost

Example:
Query: "face"
User previously searched: "facebook"

Suggestion 1: "facebook"
- base: log(1000000) = 6.0
- personal: 3.0 (in history)
- ctr: (10000/50000) × 1.5 = 0.3
- Total: 9.3

Suggestion 2: "face masks"
- base: log(500000) = 5.7
- trending: 2.0
- ctr: (5000/30000) × 1.5 = 0.25
- Total: 7.95

Result: "facebook" ranks higher

Implementation:
- Pre-compute base scores offline
- Apply real-time boosts in service
- Cache personalized rankings per user

Q5: How do you handle millions of concurrent users?

Answer:

Scalability Strategy:

1. Horizontal Scaling:
   ┌─────────┐
   │ Load    │
   │ Balancer│
   └────┬────┘
        │
   ┌────┼────┬────┐
   ▼    ▼    ▼    ▼
  [API][API][API][API]  (Stateless services)
   │    │    │    │
   └────┴────┴────┘
        │
   [Redis Cluster]
   [Elasticsearch Cluster]

2. Caching at Multiple Layers:
   - CDN (edge): 20-30% hit rate
   - Redis: 85-90% hit rate
   - In-memory Trie: 80-90% hit rate

   Result: Only 1-5% hits database

3. Read Replicas:
   - Master for writes
   - Multiple read replicas
   - Autocomplete is 99% reads

4. Geographic Distribution:
   - Deploy in multiple regions
   - Route to nearest region
   - Reduce latency

5. Rate Limiting:
   - Per user: 60 requests/min
   - Per IP: 100 requests/min
   - Prevents abuse

6. Sharding:
   Trie Sharding by first character:
   - a-f → Shard 1
   - g-m → Shard 2
   - n-s → Shard 3
   - t-z → Shard 4

   Each shard handles 25% of traffic

7. Asynchronous Processing:
   - User requests → Sync (fast path)
   - Analytics → Async (Kafka)
   - Trie updates → Async (batch)

Capacity:
- Each API server: 5K QPS
- Need for 170K QPS: 34 servers
- With caching: 10-15 servers sufficient
- Cost-effective scaling

Q6: How do you update the Trie when new queries come in?

Answer:

Update Strategies:

1. Real-time Updates (Simple but Problematic):
   - Update Trie on every search
   - Pros: Always fresh
   - Cons: Lock contention, slow writes
   - Not recommended for high QPS

2. Async Batch Updates (Recommended):

   Flow:
   ┌──────────┐      ┌──────────┐      ┌──────────┐
   │ User     │─────▶│ API      │─────▶│ Kafka    │
   │ Search   │      │ Service  │      │ Stream   │
   └──────────┘      └──────────┘      └──────────┘
                                            │
                                            ▼
                                       ┌──────────┐
                                       │ Spark    │
                                       │ Job      │
                                       └────┬─────┘
                                            │
                                       Aggregate
                                            │
                                            ▼
                                       ┌──────────┐
                                       │ Trie     │
                                       │ Builder  │
                                       └────┬─────┘
                                            │
                                       New Trie
                                            │
                                            ▼
                                       ┌──────────┐
                                       │ Atomic   │
                                       │ Swap     │
                                       └──────────┘

   Schedule:
   - Hourly: Update trending scores
   - Daily: Full Trie rebuild
   - Weekly: Deep cleanup

3. Dual-Trie Pattern:
   - Trie A: Currently serving
   - Trie B: Building new version
   - Atomic pointer swap
   - Zero downtime updates

   Code:
   let activeTrie = trieA;

   // Build new trie
   const newTrie = buildTrie(latestData);

   // Atomic swap
   activeTrie = newTrie;  // trieB

   // Old trie garbage collected

4. Incremental Updates:
   - For trending queries only
   - Update top 1000 queries every hour
   - Full rebuild daily
   - Balance freshness vs. performance

Trade-offs:
- Real-time: Fresh but slow
- Batch: Fast but slight delay
- Hybrid: Best for most cases

Recommendation:
- Batch updates (hourly/daily)
- Cache popular queries in Redis
- Update Redis in real-time
- Users see fresh data from cache

Q7: What if a user types very fast? How do you prevent too many requests?

Answer:

Already covered in detail: Debouncing

Summary:
1. Debounce with 300ms delay
2. Cancel previous requests (AbortController)
3. Only fetch when user pauses typing

Additional Strategies:

1. Client-side Throttling:
   - Maximum 1 request per 200ms
   - Even if debounce triggers

2. Request Deduplication:
   const pendingRequests = new Map();

   if (pendingRequests.has(query)) {
     return pendingRequests.get(query);
   }

   const promise = fetch(...);
   pendingRequests.set(query, promise);

   return promise;

3. Minimum Query Length:
   if (query.length < 2) {
     return; // Don't fetch
   }

4. Smart Prefetching:
   // If user typed "face"
   // Prefetch "faceb", "facer", "faces"
   // 80% chance next char is one of these

5. Progressive Enhancement:
   - Show cached/recent searches immediately
   - Fetch in background
   - Update when ready

Example Flow:
User types: f-a-c-e-b-o-o-k

Without optimization:
8 requests

With debounce (300ms):
0-200ms: "f" → debounce
200-400ms: "fa" → debounce
400-600ms: "fac" → debounce
600-800ms: "face" → debounce
800-1000ms: "faceb" → debounce
... continues typing ...
1500ms: Stops at "facebook" → REQUEST SENT
Total: 1 request

Savings: 87.5% reduction

Q8: How do you test autocomplete performance?

Answer:

Testing Strategy:

1. Unit Tests:
   - Debounce logic
   - Cache hit/miss
   - Input validation
   - Error handling

2. Integration Tests:
   - API endpoint
   - Database queries
   - Cache integration
   - End-to-end flow

3. Load Testing:
   - Tool: Apache JMeter, k6, Artillery

   Scenarios:
   a) Normal Load:
      - 10K concurrent users
      - 50-100 QPS
      - Verify latency < 200ms

   b) Peak Load:
      - 100K concurrent users
      - 500-1K QPS
      - Verify latency < 500ms

   c) Spike Test:
      - Sudden 10x traffic increase
      - Test autoscaling
      - No errors

   d) Soak Test:
      - Sustained load for 24 hours
      - Check memory leaks
      - Verify cache doesn't grow unbounded

4. Latency Testing:
   Measure:
   - Client processing: <10ms
   - Network: 20-100ms
   - Server processing: 10-50ms
   - Database query: 10-100ms
   - Total: <200ms (p95)

5. Cache Performance:
   - Hit rate should be >85%
   - Eviction rate
   - Memory usage

6. A/B Testing:
   - Test different debounce delays
   - Test different ranking algorithms
   - Measure user engagement

Metrics to Track:
┌─────────────────────┬──────────┬──────────┐
│ Metric              │ Target   │ Alert    │
├─────────────────────┼──────────┼──────────┤
│ P50 Latency         │ <100ms   │ >150ms   │
│ P95 Latency         │ <200ms   │ >300ms   │
│ P99 Latency         │ <500ms   │ >1000ms  │
│ Error Rate          │ <0.1%    │ >1%      │
│ Cache Hit Rate      │ >85%     │ <70%     │
│ API Success Rate    │ >99.9%   │ <99%     │
│ CPU Usage           │ <70%     │ >90%     │
│ Memory Usage        │ <80%     │ >95%     │
└─────────────────────┴──────────┴──────────┘

7. Real User Monitoring (RUM):
   - Track actual user latencies
   - Different geographies
   - Different devices
   - Network conditions

8. Chaos Engineering:
   - Kill random API servers
   - Simulate Redis failure
   - Network partitions
   - Verify graceful degradation

Q9: Security considerations for autocomplete?

Answer:

Security Threats & Mitigations:

1. SQL Injection:
   Threat: "'; DROP TABLE users; --"

   Mitigation:
   - Use parameterized queries
   - Input validation
   - Escape special characters

   // Bad
   query = `SELECT * FROM queries WHERE q LIKE '${userInput}%'`;

   // Good
   query = db.prepare('SELECT * FROM queries WHERE q LIKE ?');
   query.run([userInput + '%']);

2. XSS (Cross-Site Scripting):
   Threat: "<script>alert('XSS')</script>"

   Mitigation:
   - Sanitize user input
   - Escape HTML in suggestions
   - Use Content Security Policy

   // React automatically escapes
   <div>{suggestion.text}</div>  // Safe

   // Manual escaping
   function escapeHtml(text) {
     const div = document.createElement('div');
     div.textContent = text;
     return div.innerHTML;
   }

3. Rate Limiting:
   Threat: DDoS attack, scraping

   Mitigation:
   - IP-based rate limiting
   - User-based rate limiting
   - CAPTCHA for suspicious activity
   - Ban abusive IPs

4. PII (Personal Identifiable Information):
   Threat: Exposing user searches

   Mitigation:
   - Don't show other users' searches
   - Encrypt user history
   - GDPR compliance (right to be forgotten)
   - Anonymize analytics data

5. Cache Poisoning:
   Threat: Malicious data in cache

   Mitigation:
   - Validate data before caching
   - Sign cached responses
   - Short TTL for sensitive data
   - Separate cache per user for personal data

6. API Key Exposure:
   Threat: Exposed API keys in client code

   Mitigation:
   - Use backend proxy
   - Rotate keys regularly
   - Rate limit by key
   - Monitor for abuse

7. Data Privacy:
   - Don't log sensitive searches (health, financial)
   - Anonymize logs
   - Comply with privacy laws
   - User consent for personalization

8. CORS (Cross-Origin Resource Sharing):
   - Whitelist allowed origins
   - Don't use wildcard (*)
   - Validate Origin header

Security Checklist:
✓ Input validation
✓ Output encoding
✓ Rate limiting
✓ HTTPS only
✓ CSP headers
✓ Parameterized queries
✓ Error handling (don't expose internals)
✓ Logging & monitoring
✓ Regular security audits

Q10: How would you migrate from a simple LIKE query to a Trie-based system with zero downtime?

Answer:

Migration Strategy:

Phase 1: Preparation (Week 1)
─────────────────────────────
1. Build Trie infrastructure
   - Deploy Trie service (parallel to existing)
   - Don't route traffic yet

2. Sync data to Trie
   - Copy all queries from DB
   - Build initial Trie

3. Testing
   - Load test Trie service
   - Compare results with DB (accuracy)

Phase 2: Shadow Mode (Week 2-3)
──────────────────────────────
1. Dual execution
   - Send requests to both DB and Trie
   - Serve response from DB (existing behavior)
   - Compare results in background

   async function autocomplete(query) {
     const [dbResults, trieResults] = await Promise.all([
       queryDatabase(query),
       queryTrie(query)
     ]);

     // Log differences
     if (!areEqual(dbResults, trieResults)) {
       logger.warn('Results mismatch', { query });
     }

     // Still serve DB results (no user impact)
     return dbResults;
   }

2. Monitoring
   - Track accuracy (% matching)
   - Track latency improvements
   - Fix any discrepancies

Phase 3: Gradual Rollout (Week 4-5)
───────────────────────────────────
1. Canary Deployment (1% traffic)
   - Route 1% traffic to Trie
   - Monitor error rates, latency

2. Incremental increase
   - 1% → 5% → 10% → 25% → 50% → 100%
   - Each step: monitor for 24-48 hours
   - Rollback if issues detected

3. Feature Flag
   const USE_TRIE = featureFlags.get('use_trie', userId);

   if (USE_TRIE) {
     return queryTrie(query);
   } else {
     return queryDatabase(query);
   }

Phase 4: Full Migration (Week 6)
────────────────────────────────
1. 100% traffic to Trie
2. Keep DB as fallback

   async function autocomplete(query) {
     try {
       return await queryTrie(query);
     } catch (error) {
       logger.error('Trie failed, fallback to DB');
       return await queryDatabase(query);
     }
   }

3. Monitor for 1-2 weeks

Phase 5: Cleanup (Week 7-8)
──────────────────────────
1. Remove DB query code
2. Decommission old infrastructure
3. Update documentation

Rollback Plan:
─────────────
At any point, if issues:
1. Flip feature flag
2. Route 100% to DB
3. Investigate issues
4. Fix and retry

Key Principles:
- No big bang deployment
- Always have fallback
- Monitor closely
- Gradual rollout
- Quick rollback capability

Zero Downtime Achieved:
✓ No service interruption
✓ Smooth transition
✓ User doesn't notice
✓ Data consistency maintained

Behavioral & System Design Questions

Q11: How do you decide between building Trie in-house vs using Elasticsearch?

Answer:

Decision Matrix:

Build In-House Trie:
──────────────────
✓ Maximum performance (<1ms)
✓ Full control over data structure
✓ Lower operational cost (no ES license)
✓ Optimized for prefix matching
✓ Simpler for basic autocomplete

✗ Complex implementation
✗ Need to build ranking, scoring
✗ No fuzzy matching out-of-box
✗ Limited to single machine (or complex sharding)
✗ More engineering effort

Use Elasticsearch:
─────────────────
✓ Production-ready
✓ Built-in fuzzy matching
✓ Advanced ranking (BM25, custom scoring)
✓ Horizontal scaling
✓ Rich query capabilities
✓ Monitoring & tools

✗ Higher latency (10-100ms)
✗ More complex infrastructure
✗ Higher operational cost
✗ Learning curve

Decision Criteria:

1. Scale:
   - <10M queries → Trie
   - >10M queries → Elasticsearch or Hybrid

2. Features:
   - Simple prefix matching → Trie
   - Fuzzy, full-text, complex → Elasticsearch

3. Team:
   - Small team, limited time → Elasticsearch
   - Large team, custom needs → Trie

4. Latency Requirements:
   - <10ms → Trie
   - <100ms → Either
   - <500ms → Elasticsearch

5. Budget:
   - Limited → Trie (open source)
   - Good budget → Elasticsearch (Enterprise support)

Recommended Approach:
────────────────────
Hybrid:
- Trie for top 10M popular queries (in-memory)
- Elasticsearch for long-tail queries
- Best of both worlds
- 90% requests hit Trie (<1ms)
- 10% requests hit ES (20-100ms)
- Overall p95: <50ms

Implementation:
async function getSuggestions(query) {
  // Try Trie first (hot data)
  const trieResults = queryTrie(query);
  if (trieResults.length >= 5) {
    return trieResults;
  }

  // Fallback to Elasticsearch (long tail)
  const esResults = await queryElasticsearch(query);
  return esResults;
}

---

12. Accessibility (A11y)

Why Accessibility Matters

Business Impact:
- 15-20% of users have some form of disability
- Legal requirements (ADA, WCAG 2.1 AA)
- Better SEO (screen reader friendly = crawler friendly)
- Improved usability for ALL users

Autocomplete is HIGH RISK for accessibility:
- Dynamic content updates
- Keyboard navigation required
- Focus management complexity
- Screen reader announcements

ARIA Attributes & Semantic HTML

Complete ARIA Implementation:

function AccessibleAutocomplete() {
  const [inputValue, setInputValue] = useState('');
  const [suggestions, setSuggestions] = useState([]);
  const [isOpen, setIsOpen] = useState(false);
  const [activeIndex, setActiveIndex] = useState(-1);

  const inputId = 'autocomplete-input';
  const listboxId = 'autocomplete-listbox';
  const activeDescendantId = activeIndex >= 0
    ? `suggestion-${activeIndex}`
    : undefined;

  return (
    <div className="autocomplete-wrapper">
      {/* Live region for screen reader announcements */}
      <div
        role="status"
        aria-live="polite"
        aria-atomic="true"
        className="sr-only"
      >
        {isOpen && suggestions.length > 0 && (
          `${suggestions.length} suggestions available. Use up and down arrows to navigate.`
        )}
        {isOpen && suggestions.length === 0 && inputValue.length >= 2 && (
          'No suggestions found.'
        )}
      </div>

      {/* Label - always required */}
      <label htmlFor={inputId} className="autocomplete-label">
        Search
      </label>

      {/* Combobox container */}
      <div
        role="combobox"
        aria-expanded={isOpen}
        aria-haspopup="listbox"
        aria-owns={listboxId}
      >
        <input
          id={inputId}
          type="text"
          role="textbox"
          aria-autocomplete="list"
          aria-controls={listboxId}
          aria-activedescendant={activeDescendantId}
          aria-describedby="autocomplete-instructions"
          autoComplete="off"
          autoCorrect="off"
          autoCapitalize="off"
          spellCheck="false"
          value={inputValue}
          onChange={(e) => setInputValue(e.target.value)}
          onFocus={() => inputValue && setIsOpen(true)}
          onBlur={() => setTimeout(() => setIsOpen(false), 200)}
        />

        {/* Suggestions list */}
        {isOpen && (
          <ul
            id={listboxId}
            role="listbox"
            aria-label="Search suggestions"
          >
            {suggestions.map((suggestion, index) => (
              <li
                key={suggestion.id}
                id={`suggestion-${index}`}
                role="option"
                aria-selected={index === activeIndex}
                aria-posinset={index + 1}
                aria-setsize={suggestions.length}
                onClick={() => handleSelect(suggestion)}
              >
                {suggestion.text}
              </li>
            ))}
          </ul>
        )}
      </div>

      {/* Instructions for screen readers */}
      <div id="autocomplete-instructions" className="sr-only">
        When results are available, use up and down arrows to review and
        Enter to select. Touch device users, explore by touch.
      </div>
    </div>
  );
}

Screen Reader Only Styles:

/* Hide visually but keep accessible to screen readers */
.sr-only {
  position: absolute;
  width: 1px;
  height: 1px;
  padding: 0;
  margin: -1px;
  overflow: hidden;
  clip: rect(0, 0, 0, 0);
  white-space: nowrap;
  border: 0;
}

/* Focus visible for keyboard users */
.autocomplete-input:focus-visible {
  outline: 2px solid #0066cc;
  outline-offset: 2px;
}

/* High contrast mode support */
@media (prefers-contrast: high) {
  .suggestion-item[aria-selected="true"] {
    outline: 2px solid currentColor;
    background: Highlight;
    color: HighlightText;
  }
}

Keyboard Navigation

Complete Keyboard Handler:

function useKeyboardNavigation({
  suggestions,
  activeIndex,
  setActiveIndex,
  onSelect,
  onClose,
  inputRef
}) {
  const handleKeyDown = useCallback((event) => {
    const { key } = event;

    switch (key) {
      case 'ArrowDown':
        event.preventDefault();
        setActiveIndex(prev =>
          prev < suggestions.length - 1 ? prev + 1 : 0
        );
        break;

      case 'ArrowUp':
        event.preventDefault();
        setActiveIndex(prev =>
          prev > 0 ? prev - 1 : suggestions.length - 1
        );
        break;

      case 'Enter':
        if (activeIndex >= 0 && suggestions[activeIndex]) {
          event.preventDefault();
          onSelect(suggestions[activeIndex]);
        }
        break;

      case 'Escape':
        event.preventDefault();
        onClose();
        inputRef.current?.focus();
        break;

      case 'Tab':
        onClose();
        break;

      case 'Home':
        if (suggestions.length > 0) {
          event.preventDefault();
          setActiveIndex(0);
        }
        break;

      case 'End':
        if (suggestions.length > 0) {
          event.preventDefault();
          setActiveIndex(suggestions.length - 1);
        }
        break;

      default:
        if (key.length === 1) {
          setActiveIndex(-1);
        }
    }
  }, [suggestions, activeIndex, setActiveIndex, onSelect, onClose, inputRef]);

  return { handleKeyDown };
}

Keyboard Navigation Diagram:

┌─────────────────────────────────────────────────────────────┐
│                 Keyboard Navigation Map                      │
├─────────────────────────────────────────────────────────────┤
│  ┌─────────────────────────────────────────────────┐        │
│  │  Search: face█                                  │        │
│  └─────────────────────────────────────────────────┘        │
│                          │                                   │
│                          ▼                                   │
│  ┌─────────────────────────────────────────────────┐        │
│  │  ↓ Arrow Down                                   │        │
│  ├─────────────────────────────────────────────────┤        │
│  │  → facebook           ← Enter = Select          │        │
│  ├─────────────────────────────────────────────────┤        │
│  │    face recognition   ↑ Arrow Up                │        │
│  ├─────────────────────────────────────────────────┤        │
│  │    face filters                                 │        │
│  └─────────────────────────────────────────────────┘        │
│                                                              │
│  Escape = Close dropdown, return focus to input              │
│  Tab = Close dropdown, move to next focusable element        │
│  Home = Jump to first suggestion                             │
│  End = Jump to last suggestion                               │
└─────────────────────────────────────────────────────────────┘

Screen Reader Announcements

function useAnnouncer() {
  const [announcement, setAnnouncement] = useState('');

  const announce = useCallback((message) => {
    setAnnouncement('');
    requestAnimationFrame(() => {
      setAnnouncement(message);
    });
  }, []);

  const Announcer = useMemo(() => (
    <div
      role="status"
      aria-live="polite"
      aria-atomic="true"
      className="sr-only"
    >
      {announcement}
    </div>
  ), [announcement]);

  return { announce, Announcer };
}

Accessibility Testing Checklist

Manual Testing:
□ Navigate using only keyboard (Tab, Arrows, Enter, Escape)
□ Test with screen reader (NVDA, VoiceOver, JAWS)
□ Verify announcements on suggestion changes
□ Test with 200% browser zoom
□ Test with Windows High Contrast Mode
□ Verify focus is visible at all times

Automated Testing:
□ axe-core integration
□ WAVE browser extension
□ Lighthouse accessibility audit
□ pa11y CI integration

---

13. Mobile & Touch Considerations

Touch Target Sizing

WCAG Requirements:
- Minimum touch target: 44x44 pixels
- Spacing between targets: 8px minimum

Mobile-Specific Challenges:
- Virtual keyboard covers content
- Fat finger problem
- No hover states
- Slower network connections

Mobile-Optimized Styles:

.suggestion-item {
  min-height: 48px;
  padding: 12px 16px;
  display: flex;
  align-items: center;
  gap: 12px;
  -webkit-tap-highlight-color: transparent;
  user-select: none;
}

.suggestion-item:active {
  background: #e0e0e0;
  transform: scale(0.98);
}

@media (max-width: 768px) {
  .autocomplete-input {
    font-size: 16px;  /* Prevents iOS zoom on focus */
    height: 48px;
    padding: 12px 16px;
  }

  .suggestion-item {
    min-height: 56px;
    font-size: 16px;
  }
}

Virtual Keyboard Handling

function useVirtualKeyboard() {
  const [keyboardVisible, setKeyboardVisible] = useState(false);
  const [viewportHeight, setViewportHeight] = useState(window.innerHeight);

  useEffect(() => {
    if ('virtualKeyboard' in navigator) {
      navigator.virtualKeyboard.overlaysContent = true;
      navigator.virtualKeyboard.addEventListener('geometrychange', (e) => {
        setKeyboardVisible(e.target.boundingRect.height > 0);
      });
      return;
    }

    const handleResize = () => {
      const currentHeight = window.visualViewport?.height || window.innerHeight;
      const heightDiff = viewportHeight - currentHeight;
      setKeyboardVisible(heightDiff > 150);
      setViewportHeight(currentHeight);
    };

    window.visualViewport?.addEventListener('resize', handleResize);
    return () => window.visualViewport?.removeEventListener('resize', handleResize);
  }, [viewportHeight]);

  return { keyboardVisible };
}

Mobile Input Optimizations

function MobileSearchInput() {
  return (
    <input
      type="search"
      inputMode="search"
      enterKeyHint="search"
      autoComplete="off"
      autoCorrect="off"
      autoCapitalize="off"
      spellCheck="false"
      style={{ fontSize: '16px' }}
    />
  );
}

Adaptive Debouncing

function useAdaptiveDebounce(value, defaultDelay = 300) {
  const [delay, setDelay] = useState(defaultDelay);

  useEffect(() => {
    const isMobile = /iPhone|iPad|iPod|Android/i.test(navigator.userAgent);
    if (isMobile) setDelay(200);

    if (navigator.connection) {
      const { effectiveType } = navigator.connection;
      if (effectiveType === '4g') setDelay(200);
      else if (effectiveType === '3g') setDelay(400);
      else setDelay(600);
    }
  }, []);

  return useDebounce(value, delay);
}

---

14. Internationalization (i18n)

RTL (Right-to-Left) Support

.autocomplete-container {
  padding-inline-start: 16px;
  padding-inline-end: 16px;
  margin-inline-start: auto;
}

[dir="rtl"] .autocomplete-container {
  text-align: right;
}

[dir="rtl"] .suggestion-item {
  flex-direction: row-reverse;
}

.suggestion-text {
  unicode-bidi: plaintext;
  direction: inherit;
}

IME (Input Method Editor) Handling

IME is required for:
- Chinese (Pinyin, Wubi)
- Japanese (Hiragana, Katakana)
- Korean (Hangul)

Challenge:
- User types multiple keystrokes that compose into one character
- Should NOT trigger search on every keystroke during composition
- Only trigger when composition is complete

IME-Aware Input Handler:

function useIMEInput() {
  const [isComposing, setIsComposing] = useState(false);
  const [value, setValue] = useState('');

  const handleCompositionStart = useCallback(() => {
    setIsComposing(true);
  }, []);

  const handleCompositionEnd = useCallback((e) => {
    setIsComposing(false);
    setValue(e.target.value);
  }, []);

  const handleChange = useCallback((e) => {
    if (!isComposing) {
      setValue(e.target.value);
    }
  }, [isComposing]);

  return {
    value,
    isComposing,
    inputProps: {
      value,
      onChange: handleChange,
      onCompositionStart: handleCompositionStart,
      onCompositionEnd: handleCompositionEnd,
    }
  };
}

Locale-Aware Configuration

const MIN_CHARS_BY_LANGUAGE = {
  en: 2,      // English needs 2+ chars
  zh: 1,      // Chinese: 1 character is meaningful
  ja: 1,      // Japanese: 1 character is meaningful
  ko: 1,      // Korean: 1 character is meaningful
  de: 2,
  ar: 2,
};

function getMinChars(locale) {
  const language = locale.split('-')[0];
  return MIN_CHARS_BY_LANGUAGE[language] || 2;
}

---

15. Offline Support & PWA

Service Worker Caching Strategy

// sw.js
const API_CACHE_NAME = 'autocomplete-api-v1';

self.addEventListener('fetch', (event) => {
  const url = new URL(event.request.url);

  if (url.pathname.startsWith('/api/autocomplete')) {
    event.respondWith(handleAutocompleteRequest(event.request));
  }
});

async function handleAutocompleteRequest(request) {
  const query = new URL(request.url).searchParams.get('q');
  const cacheKey = `autocomplete:${query}`;

  try {
    const response = await fetch(request, { timeout: 3000 });
    if (response.ok) {
      const cache = await caches.open(API_CACHE_NAME);
      cache.put(cacheKey, response.clone());
      return response;
    }
    throw new Error('Network failed');
  } catch (error) {
    const cached = await caches.match(cacheKey);
    if (cached) {
      const data = await cached.json();
      data.stale = true;
      return new Response(JSON.stringify(data), {
        headers: { 'Content-Type': 'application/json' }
      });
    }
    return new Response(JSON.stringify({
      suggestions: [],
      error: 'OFFLINE'
    }), { status: 503 });
  }
}

Offline-First Pattern

function useOfflineFirstAutocomplete(query) {
  const [suggestions, setSuggestions] = useState([]);
  const [source, setSource] = useState(null);
  const [isOnline, setIsOnline] = useState(navigator.onLine);

  useEffect(() => {
    const handleOnline = () => setIsOnline(true);
    const handleOffline = () => setIsOnline(false);

    window.addEventListener('online', handleOnline);
    window.addEventListener('offline', handleOffline);

    return () => {
      window.removeEventListener('online', handleOnline);
      window.removeEventListener('offline', handleOffline);
    };
  }, []);

  useEffect(() => {
    if (!query || query.length < 2) return;

    const fetchData = async () => {
      // Show cached results immediately
      const cached = await cache.getSuggestions(query);
      if (cached) {
        setSuggestions(cached);
        setSource('cache');
      }

      // Fetch fresh data if online
      if (isOnline) {
        try {
          const response = await fetch(`/api/autocomplete?q=${query}`);
          const data = await response.json();
          setSuggestions(data.suggestions);
          setSource('network');
          await cache.cacheSuggestions(query, data.suggestions);
        } catch (error) {
          if (!cached) setSource('offline');
        }
      }
    };

    fetchData();
  }, [query, isOnline]);

  return { suggestions, source, isOnline };
}

---

16. Web Workers for Heavy Computations

Offloading Fuzzy Matching

// fuzzy-worker.js
self.onmessage = function(e) {
  const { type, payload } = e.data;

  switch (type) {
    case 'FUZZY_SEARCH':
      const results = fuzzySearch(payload.query, payload.items);
      self.postMessage({ type: 'RESULTS', results });
      break;

    case 'BUILD_TRIE':
      const trie = buildTrie(payload.items);
      self.postMessage({ type: 'TRIE_READY' });
      break;
  }
};

function levenshteinDistance(str1, str2) {
  const m = str1.length, n = str2.length;
  const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i-1] === str2[j-1]) {
        dp[i][j] = dp[i-1][j-1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
      }
    }
  }
  return dp[m][n];
}

Using the Worker

function useWorkerSearch() {
  const workerRef = useRef(null);
  const [isReady, setIsReady] = useState(false);

  useEffect(() => {
    workerRef.current = new Worker('/fuzzy-worker.js');
    workerRef.current.onmessage = (e) => {
      if (e.data.type === 'TRIE_READY') setIsReady(true);
    };
    return () => workerRef.current?.terminate();
  }, []);

  const search = useCallback((query) => {
    return new Promise((resolve) => {
      workerRef.current.onmessage = (e) => {
        if (e.data.type === 'RESULTS') resolve(e.data.results);
      };
      workerRef.current.postMessage({ type: 'FUZZY_SEARCH', payload: { query } });
    });
  }, []);

  return { isReady, search };
}

---

17. Comprehensive Testing Strategy

Unit Tests

import { render, screen, waitFor } from '@testing-library/react';
import userEvent from '@testing-library/user-event';

describe('Autocomplete', () => {
  it('debounces API calls by 300ms', async () => {
    jest.useFakeTimers();
    const mockFetch = jest.fn().mockResolvedValue({ suggestions: [] });

    render(<Autocomplete onFetch={mockFetch} />);
    const input = screen.getByRole('textbox');

    await userEvent.type(input, 'face');
    expect(mockFetch).not.toHaveBeenCalled();

    jest.advanceTimersByTime(300);
    await waitFor(() => {
      expect(mockFetch).toHaveBeenCalledTimes(1);
      expect(mockFetch).toHaveBeenCalledWith('face');
    });
  });

  it('navigates suggestions with arrow keys', async () => {
    render(<Autocomplete suggestions={['facebook', 'face recognition']} />);

    await userEvent.keyboard('{ArrowDown}');
    expect(screen.getByText('facebook').closest('li'))
      .toHaveAttribute('aria-selected', 'true');

    await userEvent.keyboard('{ArrowDown}');
    expect(screen.getByText('face recognition').closest('li'))
      .toHaveAttribute('aria-selected', 'true');
  });

  it('closes dropdown on Escape', async () => {
    render(<Autocomplete suggestions={['test']} />);
    await userEvent.keyboard('{Escape}');
    expect(screen.queryByRole('listbox')).not.toBeInTheDocument();
  });
});

E2E Tests (Playwright)

import { test, expect } from '@playwright/test';

test('basic search flow', async ({ page }) => {
  await page.goto('/');
  const input = page.getByRole('textbox', { name: /search/i });

  await input.fill('face');
  await expect(page.getByRole('listbox')).toBeVisible();
  await expect(page.getByRole('option').first()).toContainText('facebook');

  await page.getByRole('option', { name: 'facebook' }).click();
  await expect(input).toHaveValue('facebook');
});

test('keyboard navigation', async ({ page }) => {
  await page.goto('/');
  const input = page.getByRole('textbox');

  await input.fill('face');
  await input.press('ArrowDown');
  await expect(page.getByRole('option').first())
    .toHaveAttribute('aria-selected', 'true');

  await input.press('Enter');
  await expect(page.getByRole('listbox')).not.toBeVisible();
});

Accessibility Testing

import { axe, toHaveNoViolations } from 'jest-axe';

expect.extend(toHaveNoViolations);

it('has no accessibility violations', async () => {
  const { container } = render(<Autocomplete />);
  const results = await axe(container);
  expect(results).toHaveNoViolations();
});

---

18. Analytics & Observability

Key Metrics to Track

class AutocompleteAnalytics {
  trackQuery(query, suggestionCount, latency, source) {
    this.provider.track('autocomplete_query', {
      query,
      suggestionCount,
      latency,
      source,  // 'cache' | 'network'
      queryLength: query.length
    });
  }

  trackSelection(suggestion, position) {
    this.provider.track('autocomplete_selection', {
      selectedText: suggestion.text,
      position,
      sessionDuration: Date.now() - this.sessionStart
    });
  }

  trackAbandonment(reason) {
    this.provider.track('autocomplete_abandoned', {
      reason,  // 'timeout' | 'blur' | 'escape'
      lastQuery: this.lastQuery,
      hadSuggestions: this.suggestions.length > 0
    });
  }
}

Metrics Dashboard

┌─────────────────────────────────────────────────────────────────────┐
│                   Autocomplete Analytics Dashboard                   │
├─────────────────────────────────────────────────────────────────────┤
│  ┌─────────────────┐  ┌─────────────────┐  ┌─────────────────┐     │
│  │ Success Rate    │  │ Avg. Position   │  │ Avg. Latency    │     │
│  │     78.5%       │  │      2.3        │  │     145ms       │     │
│  └─────────────────┘  └─────────────────┘  └─────────────────┘     │
│                                                                      │
│  ┌─────────────────┐  ┌─────────────────┐  ┌─────────────────┐     │
│  │ Cache Hit Rate  │  │ Abandonment     │  │ Queries/Session │     │
│  │     87.2%       │  │     21.5%       │  │      3.2        │     │
│  └─────────────────┘  └─────────────────┘  └─────────────────┘     │
└─────────────────────────────────────────────────────────────────────┘

When to Build Custom

Build Custom When:
✓ Need complete control over UX
✓ Complex personalization requirements
✓ Unique data sources
✓ Offline-first is critical
✓ Bundle size is paramount
✓ You have the team expertise

When to Use Existing Solutions

Use Algolia When:
✓ Need full-text search infrastructure
✓ Budget for SaaS pricing
✓ Want analytics out of the box

Use Downshift When:
✓ Need headless, unstyled component
✓ Want full control over rendering
✓ Strong accessibility requirements

Use React-Select When:
✓ Select/dropdown use case
✓ Multi-select needed
✓ Quick implementation

---

20. Memory Management

Preventing Memory Leaks

// ❌ BAD: Event listener leak
useEffect(() => {
  window.addEventListener('resize', handleResize);
  // Missing cleanup!
}, []);

// ✓ GOOD: Proper cleanup
useEffect(() => {
  window.addEventListener('resize', handleResize);
  return () => window.removeEventListener('resize', handleResize);
}, []);

// ❌ BAD: Timer leak
useEffect(() => {
  setTimeout(() => fetchSuggestions(query), 300);
}, [query]);

// ✓ GOOD: Timer cleanup
useEffect(() => {
  const timer = setTimeout(() => fetchSuggestions(query), 300);
  return () => clearTimeout(timer);
}, [query]);

// ✓ GOOD: Request cancellation
useEffect(() => {
  const controller = new AbortController();
  fetch(url, { signal: controller.signal })
    .then(res => res.json())
    .then(setSuggestions)
    .catch(err => {
      if (err.name !== 'AbortError') setError(err);
    });
  return () => controller.abort();
}, [query]);

---

21. Interview Questions - Additional Topics

Mobile-Specific Questions

Q: How would you optimize autocomplete for mobile devices?

Key Optimizations:

1. Touch Targets: Minimum 48x48px, 8px spacing
2. Virtual Keyboard: Detect and adjust dropdown height
3. Performance: Shorter debounce (200ms), fewer suggestions
4. Network: Adaptive debounce based on connection speed
5. UX: Full-screen overlay on small screens, clear button visible

Accessibility Questions

Q: How do you make autocomplete accessible for screen reader users?

Complete Solution:

1. ARIA Structure:
   - role="combobox" on container
   - aria-expanded, aria-autocomplete="list"
   - aria-activedescendant for current selection
   - role="listbox" and role="option"

2. Live Regions:
   - aria-live="polite" for announcements
   - Announce suggestion count changes

3. Keyboard Navigation:
   - Arrow keys, Enter, Escape, Tab

4. Focus Management:
   - Keep focus on input during navigation
   - Visible focus indicator

Offline Questions

Q: How would you implement offline support for autocomplete?

Multi-Layer Strategy:

1. Service Worker: Cache API responses
2. IndexedDB: Store recent searches
3. Client-Side Trie: Fast local prefix search
4. Graceful Degradation: Show "offline" indicator

Implementation:
- Network-first with cache fallback
- Background sync for analytics
- Stale-while-revalidate pattern

---

Conclusion

This HLD document covers the complete architecture of an Autocomplete/Typeahead system, from high-level design to implementation details, optimizations, and interview preparation.

Key Takeaways

1. Architecture: Multi-layer caching (Client → CDN → Redis → Trie → Elasticsearch)
2. Performance: Debouncing (300ms), client-side caching, request cancellation
3. Scalability: Horizontal scaling, sharding, read replicas
4. Data Structures: Hybrid approach (Trie + Elasticsearch)
5. User Experience: Sub-200ms latency, graceful degradation
6. Security: Input validation, rate limiting, XSS prevention
7. Accessibility: ARIA attributes, keyboard navigation, screen reader support
8. Mobile: Touch targets, virtual keyboard handling, adaptive debouncing
9. Internationalization: RTL support, IME handling, locale-aware config
10. Offline: Service Worker caching, IndexedDB, offline-first pattern

Trade-offs Summary

Performance Targets

• Latency: P95 < 200ms, P99 < 500ms
• Availability: 99.9% uptime
• Throughput: 100K+ QPS
• Cache Hit Rate: >85%
• Error Rate: <0.1%

Comprehensive Checklist

Pre-Interview Preparation:

Architecture:
□ Explain Trie vs Elasticsearch trade-offs
□ Describe multi-layer caching strategy
□ Discuss horizontal scaling approach

Frontend:
□ Debouncing and request cancellation
□ Keyboard navigation implementation
□ Error handling and fallbacks

Accessibility:
□ ARIA attributes for combobox pattern
□ Screen reader announcements
□ Focus management

Mobile:
□ Touch targets and gestures
□ Virtual keyboard handling
□ Adaptive debouncing

Testing:
□ Unit tests, E2E tests, a11y tests