Design Typeahead Suggestions

LinkedIn's "Design Typeahead Suggestions" is a system design interview question focused on building a scalable autocomplete feature for search bars, common in web/mobile apps. It emphasizes real-time suggestions using data structures like Tries, with considerations for caching, ML ranking, and backend scalability.[2][9]

Problem Statement

Design a typeahead (autocomplete) system that provides relevant search suggestions as users type in a search box, prioritizing popular or trending terms. The system must handle high query volumes from web and mobile clients, support daily data updates (e.g., new terms), and deliver top results quickly while incorporating caching for performance.[6][9][2]

Functional Requirements

• Return top 5-10 suggestions matching a partial query prefix (e.g., typing "san" suggests "San Francisco", "Santa Clara").[4][2]
• Suggestions ordered by relevance, such as query frequency, popularity, or ML-based scoring.[7][2]
• Support updates for new terms or popularity changes via batch jobs from query logs.[2]
• API: GET /suggestions?q={prefix} returning JSON like {"suggestions": ["term1", "term2"]} limited to 10 items.[2]

Non-Functional Requirements & Constraints

• Scale: 100M daily active users, 20 queries/user/day (~2B QPS peak possible, but realistically 1K-10K QPS with sharding).[2]
• Latency: <100-300ms per query.[2]
• Availability: 99.99%, with caching/replication for fault tolerance.[2]
• Storage: Trie for prefixes (memory-optimized), backed by persistent DB; handle millions of terms without exceeding RAM on app servers.[4][2]
• Updates: Daily batch rebuilds; no strong consistency needed for reads.[2]

Example Inputs/Outputs

Input: q="san"
Output:
{ "suggestions": [ "san francisco", "santa clara", "sandwich", "san diego" ] }
(Top 4 by frequency; actual count varies by design).[4][2]

Input: q="a" (broad prefix)
Output: Top 10 popular terms starting with "a" (e.g., "apple", "amazon"), fetched from cache.[2]

Key Design Elements

Uses a Trie where nodes store word completion counts/frequencies for ranking; cache popular prefixes in Redis. ML can refine via user history, but base on aggregate logs.[4][2]