Table of Contents

1. Introduction
2. Functional and Non-Functional Requirements
3. Capacity Estimation
4. Data Model
5. High-Level Architecture
6. Trie Data Structure Deep Dive
7. Ranking and Scoring Algorithms
8. Real-Time Query Collection
9. Aggregation Pipeline
10. Serving Layer Design
11. Caching Strategy
12. Read/Write Paths
13. Consistency and Freshness
14. Failure Scenarios
15. Monitoring and Metrics
16. Cost Estimation
17. Interview Questions and Answers

1. Introduction

Search autocomplete — also known as typeahead or search suggestions — is one of the most ubiquitous features in modern applications. Every time you type a query into Google, Amazon, YouTube, or any search bar, a dropdown of suggested completions appears within milliseconds. This seemingly simple feature is one of the hardest distributed systems problems at scale, requiring careful engineering to deliver sub-50ms latency while processing billions of queries and adapting to trending topics in near real-time.

The challenge is multifaceted: you need a data structure that can efficiently match prefixes against billions of possible queries, a ranking algorithm that surfaces the most relevant and popular suggestions, a real-time pipeline that collects and aggregates query frequencies, and a serving layer that can handle millions of concurrent requests with extreme low-latency requirements. A 100ms delay in autocomplete can measurably reduce user engagement and search revenue.

Real-World Examples

Key Performance Metrics

2. Functional and Non-Functional Requirements

Functional Requirements

1. Prefix matching: Given a prefix string, return the top-K most relevant query suggestions sorted by relevance score.
2. Real-time updates: New queries should appear in suggestions within minutes of being typed by users across the system.
3. Multi-language support: Handle suggestions for queries in different languages and character sets (UTF-8, CJK, Arabic, etc.).
4. Fuzzy matching (optional): Handle typos and approximate matches (e.g., "restarant" → "restaurant").
5. Safe suggestions: Filter out offensive, inappropriate, or policy-violating suggestions.

Non-Functional Requirements

3. Capacity Estimation

Traffic Estimation

public class AutocompleteCapacityEstimator
{
    public static void Estimate()
    {
        // Assumptions
        long dailySearches = 5_000_000_000L;   // 5B searches per day
        double avgKeystrokesPerSearch = 20.0;   // Avg characters typed
        double uniquePrefixesPerSearch = 10.0;  // One suggestion request per keystroke
        int avgSuggestionsPerPrefix = 5;
        int avgSuggestionSizeBytes = 50;        // Average suggestion text size

        // Traffic calculations
        double requestsPerDay = dailySearches * uniquePrefixesPerSearch;
        double requestsPerSecond = requestsPerDay / 86400.0;

        Console.WriteLine($"Search requests per day: {dailySearches:N0}");
        Console.WriteLine($"Autocomplete requests per day: {requestsPerDay:N0}");
        Console.WriteLine($"Autocomplete requests per second: {requestsPerSecond:N0}");

        // Bandwidth per request (response)
        double responseSizeBytes = avgSuggestionsPerPrefix * avgSuggestionSizeBytes;
        double totalBandwidthGB = (requestsPerDay * responseSizeBytes) / (1024.0 * 1024 * 1024);
        Console.WriteLine($"Response size per request: {responseSizeBytes} bytes");
        Console.WriteLine($"Total daily bandwidth: {totalBandwidthGB:N1} GB");

        // Storage for query log (raw input)
        long queryLogRetentionDays = 30;
        double avgQuerySizeBytes = 40;
        double dailyLogStorageGB = (dailySearches * avgQuerySizeBytes) / (1024.0 * 1024 * 1024);
        double totalLogStorageGB = dailyLogStorageGB * queryLogRetentionDays;
        Console.WriteLine($"Daily query log storage: {dailyLogStorageGB:N1} GB");
        Console.WriteLine($"30-day log storage: {totalLogStorageGB:N1} GB");

        // Trie storage estimation
        long uniquePrefixes = 500_000_000L;    // Estimated unique prefixes
        int bytesPerTrieNode = 24;               // Pointer + score + metadata
        double trieStorageGB = (uniquePrefixes * bytesPerTrieNode) / (1024.0 * 1024 * 1024);
        Console.WriteLine($"Trie in-memory storage: {trieStorageGB:N1} GB");
    }
}

4. Data Model

Query Log Schema

public class QueryLogEntry
{
    public string QueryId { get; set; }           // Unique identifier
    public string QueryText { get; set; }         // The raw query string
    public string NormalizedQuery { get; set; }   // Lowercased, trimmed, deduplicated
    public string UserId { get; set; }            // Anonymized user ID
    public string Country { get; set; }           // User's country code
    public string Language { get; set; }          // User's language preference
    public DateTimeOffset Timestamp { get; set; } // When the query was typed
    public long SessionId { get; set; }           // Session identifier
    public int KeystrokePosition { get; set; }    // Position in the search input
    public bool WasCompleted { get; set; }        // Did the user press enter or click suggestion
    public string ClickedSuggestion { get; set; } // Which suggestion was clicked (if any)
}

Aggregated Suggestion Schema

public class SuggestionEntry
{
    public string Prefix { get; set; }            // The prefix key (e.g., "how to cook")
    public string FullQuery { get; set; }         // Complete suggestion text
    public double Score { get; set; }             // Computed relevance score
    public long Frequency { get; set; }           // Total query count
    public double RecencyWeightedScore { get; set; } // Time-decayed score
    public string Category { get; set; }          // Optional: category label
    public DateTimeOffset LastUpdated { get; set; }  // When this entry was last updated
    public int LanguageCode { get; set; }         // Encoded language
}

public class TrieNode
{
    public char Character { get; set; }
    public Dictionary<char, TrieNode> Children { get; set; } = new();
    public bool IsEndOfWord { get; set; }
    public List<SuggestionEntry> TopSuggestions { get; set; } = new(); // Top-K at this node
    public long TotalFrequency { get; set; }
}

5. High-Level Architecture

Component Responsibilities

6. Trie Data Structure Deep Dive

The prefix tree (Trie) is the foundational data structure for autocomplete. Each node represents a character, and paths from root to leaf represent complete query strings. The key optimization: each node stores the top-K suggestions for its prefix, enabling O(prefix_length) lookup time regardless of the number of total queries.

Trie Implementation with Top-K Caching

public class AutocompleteTrie
{
    private readonly TrieNode _root = new(' ');
    private readonly int _topK;
    private readonly object _lock = new();
    private long _totalQueries;

    public AutocompleteTrie(int topK = 10)
    {
        _topK = topK;
    }

    public void Insert(string query, long frequency = 1)
    {
        lock (_lock)
        {
            var node = _root;
            var normalized = query.ToLowerInvariant().Trim();

            foreach (char c in normalized)
            {
                if (!node.Children.ContainsKey(c))
                    node.Children[c] = new TrieNode(c);

                node = node.Children[c];

                // Update top-K suggestions at each node along the path
                UpdateTopSuggestions(node, query, frequency);
            }

            node.IsEndOfWord = true;
            Interlocked.Add(ref _totalQueries, frequency);
        }
    }

    private void UpdateTopSuggestions(TrieNode node, string query, long frequency)
    {
        var existing = node.TopSuggestions.FirstOrDefault(s =>
            string.Equals(s.FullQuery, query, StringComparison.OrdinalIgnoreCase));

        if (existing != null)
        {
            existing.Frequency += frequency;
            existing.Score = ComputeScore(existing.Frequency, existing.LastUpdated);
        }
        else
        {
            node.TopSuggestions.Add(new SuggestionEntry
            {
                FullQuery = query,
                Frequency = frequency,
                Score = ComputeScore(frequency, DateTimeOffset.UtcNow),
                LastUpdated = DateTimeOffset.UtcNow
            });
        }

        // Keep only top-K, sorted by score descending
        node.TopSuggestions = node.TopSuggestions
            .OrderByDescending(s => s.Score)
            .Take(_topK)
            .ToList();
    }

    public List<string> GetSuggestions(string prefix, int k = 10)
    {
        var node = _root;
        var normalized = prefix.ToLowerInvariant().Trim();

        // Traverse to the prefix node
        foreach (char c in normalized)
        {
            if (!node.Children.ContainsKey(c))
                return new List<string>();

            node = node.Children[c];
        }

        return node.TopSuggestions
            .OrderByDescending(s => s.Score)
            .Take(k)
            .Select(s => s.FullQuery)
            .ToList();
    }

    private double ComputeScore(long frequency, DateTimeOffset lastUpdated)
    {
        // Exponential time decay: recent queries are weighted more
        var hoursSinceUpdate = (DateTimeOffset.UtcNow - lastUpdated).TotalHours;
        var recencyFactor = Math.Exp(-0.01 * hoursSinceUpdate); // Half-life ~69 hours

        // Popularity score with logarithmic scaling
        var popularityScore = Math.Log10(frequency + 1);

        return popularityScore * recencyFactor;
    }

    public long GetTotalQueries() => Interlocked.Read(ref _totalQueries);
}

Trie Sharding Strategy

At 5B queries/day, a single trie (~4.7 GB) fits in memory, but the write throughput for updates may become a bottleneck. We shard the trie by prefix hash to distribute writes across multiple machines.

public class ShardedTrieService
{
    private readonly List<AutocompleteTrie> _shards;
    private readonly int _shardCount;

    public ShardedTrieService(int shardCount = 32)
    {
        _shardCount = shardCount;
        _shards = Enumerable.Range(0, shardCount)
            .Select(_ => new AutocompleteTrie())
            .ToList();
    }

    public int GetShard(string prefix)
    {
        return Math.Abs(prefix.GetHashCode()) % _shardCount;
    }

    public void Insert(string query)
    {
        // Insert into the shard determined by the first 3 characters
        var shardKey = query.Length >= 3 ? query[..3] : query;
        var shardIndex = GetShard(shardKey);
        _shards[shardIndex].Insert(query);
    }

    public List<string> GetSuggestions(string prefix, int k = 10)
    {
        // Query the shard that owns this prefix
        var shardIndex = GetShard(prefix);
        return _shards[shardIndex].GetSuggestions(prefix, k);
    }
}

7. Ranking and Scoring Algorithms

Multi-Signal Ranking

Raw frequency alone produces poor suggestions. Popular but irrelevant queries (like "a" or "the") dominate. A production ranking system combines multiple signals:

public class SuggestionRanker
{
    private readonly double _frequencyWeight = 0.35;
    private readonly double _recencyWeight = 0.25;
    private readonly double _completionRateWeight = 0.15;
    private readonly double _clickThroughWeight = 0.15;
    private readonly double _personalizationWeight = 0.10;

    public double Rank(SuggestionSignals signals)
    {
        var frequencyScore = NormalizeFrequency(signals.Frequency);
        var recencyScore = ComputeRecencyScore(signals.LastQueriedAt);
        var completionScore = signals.CompletionRate;
        var clickScore = signals.ClickThroughRate;
        var personalScore = signals.UserPersonalScore;

        var totalScore = (_frequencyWeight * frequencyScore)
            + (_recencyWeight * recencyScore)
            + (_completionRateWeight * completionScore)
            + (_clickThroughWeight * clickScore)
            + (_personalizationWeight * personalScore);

        // Apply global filters
        if (signals.IsNSFW) totalScore *= 0.1;   // Demote NSFW content
        if (signals.IsTrending) totalScore *= 1.5; // Boost trending queries

        return totalScore;
    }

    private double NormalizeFrequency(long frequency)
    {
        // Log-normalize to prevent extreme popularity from dominating
        return Math.Log10(frequency + 1) / Math.Log10(1_000_000);
    }

    private double ComputeRecencyScore(DateTimeOffset lastQueried)
    {
        var hoursSince = (DateTimeOffset.UtcNow - lastQueried).TotalHours;
        return Math.Exp(-0.05 * hoursSince); // Half-life ~14 hours
    }
}

public class SuggestionSignals
{
    public long Frequency { get; set; }
    public DateTimeOffset LastQueriedAt { get; set; }
    public double CompletionRate { get; set; }    // % of users who completed this query
    public double ClickThroughRate { get; set; }   // % of users who clicked this suggestion
    public double UserPersonalScore { get; set; }  // User-specific relevance
    public bool IsNSFW { get; set; }
    public bool IsTrending { get; set; }
}

Personalization Layer

public class PersonalizedRanker
{
    private readonly IUserProfileStore _profiles;
    private readonly IHistoryStore _history;

    public async Task<double> ComputePersonalScoreAsync(
        string userId, string suggestion)
    {
        var profile = await _profiles.GetAsync(userId);
        var searchHistory = await _history.GetRecentAsync(userId, limit: 100);

        double score = 0.0;

        // 1. Category affinity (e.g., user frequently searches "tech")
        var categories = ExtractCategories(suggestion);
        foreach (var cat in categories)
        {
            if (profile.CategoryAffinity.TryGetValue(cat, out var affinity))
                score += affinity * 0.4;
        }

        // 2. Query similarity to recent searches
        var recentQueries = searchHistory.Select(h => h.Query).ToList();
        var maxSimilarity = recentQueries
            .Select(q => JaccardSimilarity(q.Split(' '), suggestion.Split(' ')))
            .DefaultIfEmpty(0)
            .Max();
        score += maxSimilarity * 0.3;

        // 3. Language and region match
        if (profile.PreferredLanguage == GetLanguage(suggestion))
            score += 0.15;

        // 4. Avoid recently seen suggestions (diversity)
        if (searchHistory.Any(h => h.Query == suggestion))
            score -= 0.2; // Penalize already-seen suggestions

        return Math.Clamp(score, 0, 1);
    }

    private double JaccardSimilarity(string[] set1, string[] set2)
    {
        var intersection = set1.Intersect(set2).Count();
        var union = set1.Union(set2).Count();
        return union == 0 ? 0 : (double)intersection / union;
    }
}

8. Real-Time Query Collection

Query Log Pipeline

public class QueryEventCollector
{
    private readonly IMessageProducer _kafkaProducer;
    private readonly BatchQueue<QueryLogEntry> _batchQueue;
    private readonly int _batchSize;
    private readonly TimeSpan _flushInterval;

    public QueryEventCollector(IMessageProducer producer, int batchSize = 500,
        TimeSpan? flushInterval = null)
    {
        _kafkaProducer = producer;
        _batchSize = batchSize;
        _flushInterval = flushInterval ?? TimeSpan.FromSeconds(5);
        _batchQueue = new BatchQueue<QueryLogEntry>(OnFlush);
    }

    public async Task TrackQueryAsync(QueryLogEvent queryEvent)
    {
        // Client sends: query, timestamp, country, language, session info
        var entry = new QueryLogEntry
        {
            QueryId = Guid.NewGuid().ToString("N"),
            QueryText = queryEvent.Query,
            NormalizedQuery = NormalizeQuery(queryEvent.Query),
            UserId = AnonymizeUserId(queryEvent.UserId),
            Country = queryEvent.Country,
            Language = queryEvent.Language,
            Timestamp = DateTimeOffset.UtcNow,
            SessionId = queryEvent.SessionId,
            WasCompleted = queryEvent.WasCompleted,
            ClickedSuggestion = queryEvent.ClickedSuggestion
        };

        await _batchQueue.EnqueueAsync(entry);
    }

    private string NormalizeQuery(string query)
    {
        return query.Trim()
            .ToLowerInvariant()
            .Normalize(NormalizationForm.FormKC) // Unicode normalization
            .Replace("\\s+", " ")               // Collapse whitespace
            .Replace("[^a-z0-9\\s]", "");        // Remove special chars
    }

    private string AnonymizeUserId(string userId)
    {
        using var sha = SHA256.Create();
        var hash = sha.ComputeHash(Encoding.UTF8.GetBytes(userId + _salt));
        return Convert.ToBase64String(hash)[..16];
    }

    private async Task OnFlush(List<QueryLogEntry> batch)
    {
        var messages = batch.Select(entry => new Message(
            key: entry.NormalizedQuery[..Math.Min(3, entry.NormalizedQuery.Length)],
            value: JsonSerializer.SerializeToUtf8Bytes(entry)
        )).ToList();

        await _kafkaProducer.SendBatchAsync("raw-query-logs", messages);
    }
}

Event Throttling and Sampling

9. Aggregation Pipeline

Time-Windowed Aggregation

The aggregation pipeline computes query frequencies over multiple time windows (1 hour, 24 hours, 7 days, 30 days) to balance recency and historical popularity. This is implemented as a streaming job using Apache Flink.

public class QueryAggregator
{
    // Multiple time windows for different time horizons
    private readonly Dictionary<string, CounterWindow> _windows = new()
    {
        ["1h"] = new CounterWindow(TimeSpan.FromHours(1), weight: 1.0),
        ["24h"] = new CounterWindow(TimeSpan.FromHours(24), weight: 0.5),
        ["7d"] = new CounterWindow(TimeSpan.FromDays(7), weight: 0.2),
        ["30d"] = new CounterWindow(TimeSpan.FromDays(30), weight: 0.1),
    };

    public async Task<AggregatedSuggestion> ProcessQueryAsync(string normalizedQuery)
    {
        var signals = new Dictionary<string, long>();

        foreach (var (windowName, window) in _windows)
        {
            var count = await window.GetCountAsync(normalizedQuery);
            signals[windowName] = count;
        }

        // Composite score combining all windows
        var compositeScore = signals.Sum(kvp =>
            kvp.Value * _windows[kvp.Key].weight);

        return new AggregatedSuggestion
        {
            Query = normalizedQuery,
            Frequency1h = signals["1h"],
            Frequency24h = signals["24h"],
            Frequency7d = signals["7d"],
            Frequency30d = signals["30d"],
            CompositeScore = compositeScore,
            LastUpdated = DateTimeOffset.UtcNow
        };
    }
}

public class CounterWindow
{
    private readonly TimeSpan _windowSize;
    private readonly double _weight;
    private readonly SortedDictionary<DateTimeOffset, long> _counts = new();

    public CounterWindow(TimeSpan windowSize, double weight)
    {
        _windowSize = windowSize;
        _weight = weight;
    }

    public async Task IncrementAsync(string query)
    {
        var windowStart = GetWindowStart(DateTimeOffset.UtcNow);
        if (_counts.ContainsKey(windowStart))
            _counts[windowStart]++;
        else
            _counts[windowStart] = 1;

        await EvictOldEntriesAsync();
    }

    public Task<long> GetCountAsync(string query)
    {
        var cutoff = DateTimeOffset.UtcNow - _windowSize;
        var total = _counts.Where(kvp => kvp.Key >= cutoff).Sum(kvp => kvp.Value);
        return Task.FromResult(total);
    }

    private DateTimeOffset GetWindowStart(DateTimeOffset now)
    {
        return new DateTimeOffset(now.Ticks - (now.Ticks % _windowSize.Ticks), now.Offset);
    }
}

Content Moderation Integration

public class ContentModerator
{
    private readonly IProfanityFilter _profanityFilter;
    private readonly IClassifyModel _nsfwClassifier;
    private readonly HashSet<string> _blockedPrefixes;

    public ModerationResult Moderate(string query)
    {
        // 1. Exact match blocklist
        if (_blockedPrefixes.Contains(query.ToLowerInvariant()))
            return new ModerationResult { Blocked = true, Reason = "Exact blocklist match" };

        // 2. Profanity filter
        if (_profanityFilter.ContainsProfanity(query))
            return new ModerationResult { Blocked = true, Reason = "Profanity detected" };

        // 3. NSFW classification
        var nsfwScore = _nsfwClassifier.Classify(query);
        if (nsfwScore > 0.8)
            return new ModerationResult { Blocked = true, Reason = "NSFW content" };

        // 4. Sensitive topic detection (violence, hate speech, etc.)
        if (DetectSensitiveContent(query))
            return new ModerationResult { Flagged = true, Reason = "Sensitive topic" };

        return new ModerationResult { Blocked = false, Approved = true };
    }
}

10. Serving Layer Design

Request Handling Flow

public class AutocompleteHandler
{
    private readonly ICacheService _cache;
    private readonly ShardedTrieService _trieService;
    private readonly IContentModerator _moderator;
    private readonly IMetricsCollector _metrics;
    private readonly ILogger<AutocompleteHandler> _logger;

    public async Task<SuggestionResponse> GetSuggestionsAsync(SuggestionRequest request)
    {
        var sw = Stopwatch.StartNew();
        var prefix = NormalizePrefix(request.Prefix);

        if (string.IsNullOrEmpty(prefix))
            return new SuggestionResponse { Suggestions = new List<string>() };

        try
        {
            // Layer 1: Check Redis cache
            var cacheKey = $"ac:{prefix}:{request.Language}:{request.Country}";
            var cached = await _cache.GetAsync<List<string>>(cacheKey);
            if (cached != null)
            {
                _metrics.IncrementCounter("autocomplete.cache_hit");
                return new SuggestionResponse
                {
                    Suggestions = ApplyModeration(cached),
                    Source = "cache",
                    LatencyMs = sw.ElapsedMilliseconds
                };
            }

            // Layer 2: Query the trie
            var suggestions = _trieService.GetSuggestions(prefix, request.MaxSuggestions ?? 10);

            // Layer 3: Apply content moderation
            var moderatedSuggestions = ApplyModeration(suggestions);

            // Layer 4: Cache the result
            await _cache.SetAsync(cacheKey, moderatedSuggestions, TimeSpan.FromMinutes(5));

            _metrics.IncrementCounter("autocomplete.cache_miss");
            _metrics.RecordLatency("autocomplete.trie_lookup", sw.ElapsedMilliseconds);

            return new SuggestionResponse
            {
                Suggestions = moderatedSuggestions,
                Source = "trie",
                LatencyMs = sw.ElapsedMilliseconds
            };
        }
        catch (Exception ex)
        {
            _logger.LogError(ex, "Error getting suggestions for prefix: {Prefix}", prefix);
            _metrics.IncrementCounter("autocomplete.errors");

            // Fallback: return cached generic suggestions
            return new SuggestionResponse
            {
                Suggestions = await GetFallbackSuggestions(request.Language),
                Source = "fallback",
                LatencyMs = sw.ElapsedMilliseconds
            };
        }
    }

    private List<string> ApplyModeration(List<string> suggestions)
    {
        return suggestions.Where(s => !_moderator.Moderate(s).Blocked).ToList();
    }
}

Latency Budget Breakdown

11. Caching Strategy

Multi-Layer Cache Architecture

Cache Key Design

public class CacheKeyBuilder
{
    public static string BuildKey(string prefix, string language, string country,
        int maxSuggestions = 10)
    {
        // Normalize the prefix for consistent caching
        var normalizedPrefix = prefix.ToLowerInvariant().Trim();

        // Use only first 30 chars for very long prefixes to improve cache hit rate
        var truncatedPrefix = normalizedPrefix.Length > 30
            ? normalizedPrefix[..30]
            : normalizedPrefix;

        return $"ac:{truncatedPrefix}:{language}:{country}:{maxSuggestions}";
    }

    // Warm cache with popular prefixes
    public static List<string> GetWarmupPrefixes()
    {
        return new List<string>
        {
            // Single characters (highest traffic)
            "a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
            "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
            "u", "v", "w", "x", "y", "z",
            // Top 2-character prefixes
            "ho", "wh", "ho", "go", "be", "ne", "ho",
            // Common 3-character prefixes
            "how", "who", "wha", "bes", "goo", "ama",
        };
    }
}

Cache Performance

12. Read/Write Paths

Write Path (Query Logging → Trie Update)

Read Path (Prefix → Suggestions)

13. Consistency and Freshness

Eventual Consistency Model

The autocomplete system uses eventual consistency by design. The trie is rebuilt periodically from aggregated data, meaning new queries appear in suggestions with a delay of 1–5 minutes. This is acceptable because:

• The autocomplete system is a read-heavy system where perfect freshness is not required.
• A 5-minute delay is imperceptible to most users.
• Aggregating over time windows improves ranking quality (avoids noise from single events).
• Periodic rebuilds allow for global deduplication and content moderation before suggestions go live.

14. Failure Scenarios

Failure Mode Analysis

public class AutocompleteFallbackChain
{
    public async Task<List<string>> GetSuggestionsWithFallbackAsync(
        string prefix, string language, string country)
    {
        // Layer 1: Try the normal path
        try
        {
            return await GetSuggestionsFromTrie(prefix, language, country);
        }
        catch (TrieUnavailableException)
        {
            // Layer 2: Try Redis cache (may have slightly stale data)
            try
            {
                var cacheKey = CacheKeyBuilder.BuildKey(prefix, language, country);
                return await _redis.GetAsync<List<string>>(cacheKey)
                    ?? await GetGenericFallbackSuggestions(prefix, language);
            }
            catch (RedisException)
            {
                // Layer 3: Return pre-computed popular suggestions for this prefix length
                return await GetPrecomputedSuggestions(prefix.Length, language);
            }
        }
    }
}

15. Monitoring and Metrics

Key Metrics to Track

public class AutocompleteMetrics
{
    private readonly Counter _requestsTotal;
    private readonly Histogram _latencyHistogram;
    private readonly Counter _cacheHits;
    private readonly Counter _cacheMisses;
    private readonly Gauge _trieMemoryBytes;
    private readonly Gauge _trieAge;
    private readonly Counter _moderationBlocked;

    public AutocompleteMetrics(string serviceName = "autocomplete")
    {
        var factory = new MetricFactory();

        _requestsTotal = factory.CreateCounter(
            $"{serviceName}_requests_total", "Total requests",
            new[] { "status", "source" });

        _latencyHistogram = factory.CreateHistogram(
            $"{serviceName}_latency_ms", "Request latency in milliseconds",
            labels: new[] { "source" },
            buckets: new[] { 5.0, 10.0, 15.0, 20.0, 30.0, 50.0, 75.0, 100.0 });

        _cacheHits = factory.CreateCounter(
            $"{serviceName}_cache_hits_total", "Cache hits", new[] { "layer" });
        _cacheMisses = factory.CreateCounter(
            $"{serviceName}_cache_misses_total", "Cache misses", new[] { "layer" });

        _trieMemoryBytes = factory.CreateGauge(
            $"{serviceName}_trie_memory_bytes", "Trie memory usage in bytes");
        _trieAge = factory.CreateGauge(
            $"{serviceName}_trie_age_seconds", "Seconds since last trie rebuild");

        _moderationBlocked = factory.CreateCounter(
            $"{serviceName}_moderation_blocked_total", "Suggestions blocked");
    }

    public void RecordRequest(string status, string source, double latencyMs)
    {
        _requestsTotal.Inc(new[] { status, source });
        _latencyHistogram.Observe(latencyMs, new[] { source });
    }
}

16. Cost Estimation

17. Interview Questions and Answers

Q1: How do you handle trending topics appearing in real-time?

Implement a two-tier system: a streaming pipeline (Flink) that detects sudden spikes in query volume within 1-minute windows and immediately injects them into a "trending cache," while the batch pipeline (every 5 minutes) rebuilds the trie with updated frequencies. The trending cache is checked first in the serving path, enabling sub-minute freshness for viral topics.

Q2: How would you handle multi-language autocomplete with a single trie?

You wouldn't — use separate tries per language, sharded by language code prefix. Each language has its own trie cluster because character sets differ dramatically (Latin vs. CJK vs. Arabic). The routing layer selects the correct trie based on the user's language preference (from browser headers or profile), and the aggregation pipeline maintains separate frequency counters per language.

Q3: How do you handle prefixes with billions of possible completions?

Every node in the trie stores only the top-K (e.g., top 10) suggestions. When a prefix has billions of completions, you show the top 10 ranked by score. This is the key optimization — you never enumerate all completions. The top-K list is precomputed and cached at each trie node during the rebuild process.

Q4: How do you prevent gaming/manipulation of autocomplete suggestions?

Multiple safeguards: (1) Require a minimum frequency threshold before a suggestion appears (prevents single-occurrence gaming). (2) Apply a "personalization penalty" — queries typed by the same user/session are weighted less. (3) Use a time-decay factor so artificially inflated bursts fade quickly. (4) Implement content moderation filters. (5) Human review queue for suspicious patterns (sudden spikes from concentrated IPs).

Q5: How do you handle typos and fuzzy prefix matching?

Use a combination of approaches: (1) Levenshtein distance calculation for the prefix against trie branches. (2) Phonetic matching (Soundex, Metaphone) for phonetically similar prefixes. (3) Keep a separate "correction index" mapping common misspellings to correct queries. (4) At serving time, if exact prefix yields fewer than K suggestions, expand to fuzzy matches with a relevance threshold.

Q6: How would you design autocomplete for a search engine with 100+ languages?

Shard by language family and region. Use Unicode CLDR data for language detection. Maintain separate trie clusters for each major script (Latin, CJK, Arabic, Cyrillic, Devanagari). The aggregation pipeline processes queries per-language using the user's language preference. For mixed-language queries, the system detects the dominant script and routes accordingly. Regional popular queries get boosted for users in that region.

Q7: How do you handle the cold start problem for new users?

For new users without personalization history: serve globally popular suggestions for their region and language. The system uses geo-IP to determine country and Accept-Language header for language. As the user types more queries, the personalization layer gradually tailors suggestions. The client SDK also caches prefix→suggestions mappings in localStorage for instant repeat lookups.

Q8: How would you test the quality of autocomplete suggestions?

Implement a multi-faceted testing framework: (1) Offline evaluation using click-through rate on historical data. (2) A/B testing with holdout groups — measure search success rate, time-to-first-result, and user satisfaction. (3) Human evaluation panels scoring suggestion relevance. (4) Regression testing for known-bad suggestions (offensive content, incorrect completions). (5) Latency testing with production traffic replay.

Q9: How do you ensure consistent suggestions across different devices for the same user?

The personalization layer stores user search history in a central profile store (e.g., DynamoDB). When a user types on mobile, the autocomplete service fetches their recent search history from this store to influence suggestions. For low-latency, the user profile is cached in Redis with a 5-minute TTL. Cross-device synchronization happens through the query logging pipeline — queries from any device update the same profile.

Q10: How would you scale this to handle 100x traffic growth?

Scale each layer independently: (1) Autocomplete service is stateless — add instances behind the load balancer. (2) Redis cache — increase cluster shards and replicas. (3) Trie — increase shard count from 32 to 320, rebalancing by prefix hash. (4) Aggregation — increase Flink parallelism. (5) CDN — the CDN absorbs the majority of read traffic growth. (6) Client-side caching — increase localStorage TTL for repeat prefixes. The system should scale linearly with horizontal additions at each layer.