High-Level Design: Autocomplete/Typeahead System
Table of Contents
- Problem Statement & Requirements
- High-Level Architecture
- Component Architecture (Frontend)
- Data Flow (Search As You Type)
- API Design & Communication Protocols
- Database Design
- Caching Strategy
- State Management
- Performance Optimization
- Error Handling & Edge Cases
- Interview Cross-Questions
- Accessibility (A11y)
- Mobile & Touch Considerations
- Internationalization (i18n)
- Offline Support & PWA
- Web Workers for Heavy Computations
- Comprehensive Testing Strategy
- Analytics & Observability
- Build vs Buy Analysis
- Memory Management
- 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
-
Performance
- Sub 200ms latency for suggestions
- Handle high read throughput (read-heavy system)
- Minimal network payload
-
Scalability
- Support millions of users
- Handle billions of queries per day
- Scale horizontally
-
Availability
- 99.9% uptime
- Graceful degradation on failures
-
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:
| Delay | User Experience | Network Calls | Use Case |
|---|---|---|---|
| 100ms | Very responsive | High (wasteful) | Real-time critical |
| 200ms | Responsive | Moderate | Good balance |
| 300ms | Standard | Optimal | Recommended |
| 500ms | Noticeable lag | Low | Slow networks |
| 1000ms | Frustrating | Very low | Avoid |
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:
- Minimum Character Length
const MIN_CHARS = 2;
if (query.length >= MIN_CHARS) {
fetchSuggestions(query);
}
- Reduces noise
- 1-char queries too broad
- Better UX
- After Debounce Delay
// Wait 300ms after user stops typing
const debouncedQuery = useDebounce(query, 300);
-
On Input Change (not on every keystroke)
- Debounced onChange handler
- Not onKeyDown/onKeyPress
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
- 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
| Feature | Trie | Elasticsearch | Redis |
|---|---|---|---|
| Speed | O(k) k=query length | O(log n) | O(1) for cache |
| Prefix Search | Excellent | Good (with prefix query) | Manual implementation |
| Memory | High (in-memory) | Moderate (disk+cache) | High (in-memory) |
| Scalability | Limited (single machine) | Excellent (distributed) | Good (cluster mode) |
| Fuzzy Match | Complex | Excellent (built-in) | Limited |
| Ranking | Manual | Excellent (scoring) | Manual |
| Persistence | Needs serialization | Yes | Yes (RDB/AOF) |
| Update Speed | Fast | Moderate (indexing lag) | Very Fast |
| Best For | Small datasets, fast prefix | Large datasets, complex queries | Caching, hot data |
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 │ │
│ └─────────────────┘ └─────────────────┘ └─────────────────┘ │
└─────────────────────────────────────────────────────────────────────┘
19. Build vs Buy Analysis
Comparison Matrix
┌─────────────────┬──────────────┬──────────────┬──────────────┬──────────────┐
│ Factor │ Custom Build │ Algolia │ Downshift │ React-Select │
├─────────────────┼──────────────┼──────────────┼──────────────┼──────────────┤
│ Setup Time │ 2-4 weeks │ 1-2 days │ 2-3 days │ 1 day │
│ Bundle Size │ Custom │ ~50KB │ ~12KB │ ~25KB │
│ Customization │ Unlimited │ Limited │ High │ Medium │
│ Backend │ Required │ Included │ Required │ Required │
│ Cost │ Dev time │ $$/month │ Free │ Free │
│ Accessibility │ Manual │ Good │ Excellent │ Good │
└─────────────────┴──────────────┴──────────────┴──────────────┴──────────────┘
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]);
Memory-Aware Cache
class MemoryAwareLRUCache {
constructor(options = {}) {
this.maxSize = options.maxSize || 100;
this.maxMemoryMB = options.maxMemoryMB || 10;
this.cache = new Map();
this.memoryUsage = 0;
}
set(key, value) {
const sizeMB = JSON.stringify(value).length * 2 / (1024 * 1024);
while (this.memoryUsage + sizeMB > this.maxMemoryMB && this.cache.size > 0) {
this.evictOldest();
}
this.cache.set(key, { value, sizeMB, timestamp: Date.now() });
this.memoryUsage += sizeMB;
}
evictOldest() {
const firstKey = this.cache.keys().next().value;
const entry = this.cache.get(firstKey);
this.memoryUsage -= entry.sizeMB;
this.cache.delete(firstKey);
}
}
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
- Architecture: Multi-layer caching (Client → CDN → Redis → Trie → Elasticsearch)
- Performance: Debouncing (300ms), client-side caching, request cancellation
- Scalability: Horizontal scaling, sharding, read replicas
- Data Structures: Hybrid approach (Trie + Elasticsearch)
- User Experience: Sub-200ms latency, graceful degradation
- Security: Input validation, rate limiting, XSS prevention
- Accessibility: ARIA attributes, keyboard navigation, screen reader support
- Mobile: Touch targets, virtual keyboard handling, adaptive debouncing
- Internationalization: RTL support, IME handling, locale-aware config
- Offline: Service Worker caching, IndexedDB, offline-first pattern
Trade-offs Summary
| Aspect | Choice | Trade-off |
|---|---|---|
| API Protocol | REST | Simple but no server push |
| Data Structure | Trie + ES | High memory but fast |
| Caching | Multi-layer | Complex but performant |
| Updates | Batch (hourly) | Slight delay but scalable |
| Personalization | User history | Privacy concerns |
| Debounce Delay | 300ms | Balance UX and network |
| Build vs Buy | Custom | Full control vs dev time |
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
Top comments (0)