DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Build a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.
Project Overview
You know that dropdown that appears when you start typing in Google or your IDE? That is an autocomplete system. At its core, it needs to:
- Store a dictionary of valid words/phrases
- Given a prefix, find all words starting with that prefix
- Rank results by relevance (usually frequency)
- Return results fast enough for real-time use (under 50ms)
A trie (prefix tree) is the perfect data structure for this. Let me show you how to build one from scratch.
The Trie Data Structure
A trie stores strings character by character, sharing common prefixes. The word "cat" and "car" share the path c→a, then branch to t and r.
Example
root
/ | \
c d h
| | |
a o e
/ \ | |
t r g l
| | |
(s) (s) p
Each node contains:
- A dictionary of children (character → child node)
- A boolean marking if this node completes a word
- Optional: frequency count, the full word
Implementation
TrieNode and Trie Base
Example
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # marks complete word
self.frequency = 0 # how often this word was searched
self.word = None # store full word at terminal nodes
class AutocompleteSystem:
def __init__(self):
self.root = TrieNode()
def insert(self, word, frequency=1):
"""Insert a word with its frequency."""
node = self.root
for char in word.lower():
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
node.frequency += frequency
node.word = word.lower()
def search(self, word):
"""Check if exact word exists."""
node = self._traverse(word.lower())
return node is not None and node.is_end
def _traverse(self, prefix):
"""Navigate to the node representing this prefix."""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
Autocomplete: Find All Words with Prefix
Example
def autocomplete(self, prefix, max_results=5):
"""Return top suggestions for a given prefix."""
prefix = prefix.lower()
node = self._traverse(prefix)
if node is None:
return [] # No words with this prefix
# Collect all words under this prefix node
suggestions = []
self._collect_words(node, suggestions)
# Sort by frequency (descending) and return top results
suggestions.sort(key=lambda x: -x[1])
return [word for word, freq in suggestions[:max_results]]
def _collect_words(self, node, results):
"""DFS to collect all complete words under a node."""
if node.is_end:
results.append((node.word, node.frequency))
for char, child in node.children.items():
self._collect_words(child, results)
Usage Example
Example
# Build the autocomplete system
ac = AutocompleteSystem()
# Insert words with frequencies (simulating search history)
words_with_freq = [
("python", 100), ("programming", 85), ("project", 60),
("promise", 40), ("process", 55), ("problem", 90),
("practice", 70), ("print", 45), ("private", 30),
("data", 80), ("database", 65), ("dataframe", 50),
]
for word, freq in words_with_freq:
ac.insert(word, freq)
# Get suggestions
print(ac.autocomplete("pro"))
# Output: ['programming', 'problem', 'practice', 'project', 'process']
print(ac.autocomplete("dat"))
# Output: ['data', 'database', 'dataframe']
print(ac.autocomplete("pri"))
# Output: ['print', 'private']
Optimization: Heap for Top-K
Instead of collecting ALL words and sorting, use a min-heap to maintain only the top K results during DFS:
Example
import heapq
def autocomplete_optimized(self, prefix, k=5):
"""Use heap for efficient top-K retrieval."""
prefix = prefix.lower()
node = self._traverse(prefix)
if not node:
return []
# Min-heap of size k: (frequency, word)
heap = []
self._collect_top_k(node, heap, k)
# Extract results sorted by frequency (descending)
results = []
while heap:
freq, word = heapq.heappop(heap)
results.append(word)
results.reverse()
return results
def _collect_top_k(self, node, heap, k):
if node.is_end:
if len(heap) < k:
heapq.heappush(heap, (node.frequency, node.word))
elif node.frequency > heap[0][0]:
heapq.heapreplace(heap, (node.frequency, node.word))
for child in node.children.values():
self._collect_top_k(child, heap, k)
Real-Time Updates: Recording Searches
A real autocomplete system updates frequencies based on actual user behavior:
python example
def record_search(self, query):
"""User performed this search — increase its frequency."""
self.insert(query, frequency=1) # Increment by 1
def input_character(self, typed_so_far):
"""Called on every keystroke for real-time suggestions."""
if not typed_so_far:
return []
return self.autocomplete(typed_so_far, max_results=5)LeetCode Problem 642: Design Search Autocomplete System
This is based on the classic interview problem. The system tracks sentence history and user input character by character:
python example
class AutocompleteSystem642:
def __init__(self, sentences, times):
self.root = TrieNode()
self.current_input = ""
for sentence, count in zip(sentences, times):
self.insert(sentence, count)
def input(self, c):
if c == '#':
# End of sentence — record it
self.insert(self.current_input, 1)
self.current_input = ""
return []
self.current_input += c
return self.autocomplete(self.current_input, 3)Complexity Analysis
| Operation | Time | Space |
|---|---|---|
| Insert word of length m | O(m) | O(m) per word |
| Search exact word | O(m) | O(1) |
| Autocomplete (all results) | O(n) where n = words with prefix | O(n) |
| Autocomplete (top-K with heap) | O(n log k) | O(k) |
| Total space for N words, avg length m | - | O(N × m) worst, usually much less |
Extensions for Production
- Fuzzy matching: Allow typos using edit distance at each trie node
- Personalization: Maintain per-user frequency tables
- Recency bias: Weight recent searches higher with time decay
- Phrase completion: Store full sentences, not just words
- Caching: Cache results for common prefixes (top 1000 prefixes cover 90% of queries)
Key Takeaways
- Tries excel at prefix matching — O(m) to reach any prefix regardless of dictionary size
- Frequency-ranked results require either sorting after collection or a heap during collection
- The trie shares prefixes, so "programming" and "program" share 7 nodes — very space-efficient for English
- Real autocomplete systems combine tries with caching, personalization, and machine learning ranking
Performance Testing
Let's benchmark our autocomplete system with realistic data:
Example
import time
def benchmark():
ac = AutocompleteSystem()
# Simulate indexing 10,000 words
import string
import random
words = []
for _ in range(10000):
length = random.randint(3, 12)
word = ''.join(random.choices(string.ascii_lowercase, k=length))
freq = random.randint(1, 100)
words.append((word, freq))
# Measure insertion time
start = time.time()
for word, freq in words:
ac.insert(word, freq)
insert_time = time.time() - start
print(f"Inserted 10,000 words in {insert_time:.3f}s")
# Measure query time (average over 1000 queries)
prefixes = [w[0][:3] for w in random.sample(words, 1000)]
start = time.time()
for prefix in prefixes:
ac.autocomplete(prefix, max_results=5)
query_time = (time.time() - start) / 1000
print(f"Average query time: {query_time*1000:.2f}ms")
benchmark()
# Typical output:
# Inserted 10,000 words in 0.045s
# Average query time: 0.12ms (well under 50ms requirement)
Handling Special Cases
Case-Insensitive Search
Our implementation already lowercases everything. But what about preserving display case?
Example
def insert_preserve_case(self, word, frequency=1):
"""Index lowercase but store original case for display."""
node = self.root
for char in word.lower():
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
node.frequency += frequency
node.word = word # Store ORIGINAL case for display
Multi-Word Queries
For sentence completion (like Google), store entire sentences as paths:
python example
# Instead of character-by-character, you can also store word-by-word
# "how to cook" -> trie path: "how" -> "to" -> "cook"
# This gives word-level autocomplete for search queriesMemory Optimization with Compressed Tries (Radix Trees)
If memory is a concern, compress single-child chains into single nodes:
Example
Standard trie: r -> o -> m -> a -> n -> c -> e
Compressed: "romance" (single node)
This reduces node count significantly for long words with unique suffixes. The tradeoff is slightly more complex insertion and search logic.
Real-World Autocomplete Architecture
Production systems like Google Search add layers beyond a simple trie:
- Distributed trie: Sharded across servers by prefix (a-f on server 1, g-m on server 2)
- Machine learning ranking: TF-IDF replaced by neural models that consider context, recency, location
- Personalization: Your search history weighs suggestions differently than others'
- Caching layer: Top 10,000 prefixes are pre-computed and cached in CDN edge servers
- Fallback: If no trie match, fall back to spell correction + popular searches
Our project implements the core algorithmic foundation that all these systems build upon.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Autocomplete System Using Trie.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, projects, autocomplete, system
Related Data Structures & Algorithms Topics
Continue learning this concept
ProjectsLibrary Management System Using DSABuild a library management system that demonstrates practical use of hash tables for book lookup, BST for sorted catalogs, queues for waitlists, stacks for undo operations, and linked lists for borrow history.ProjectsRoute Finder Using GraphsBuild a route-finding application using graph data structures, Dijkstra\ProjectsMini Search Engine ProjectBuild a mini search engine from scratch using an inverted index (hash map), TF-IDF scoring for relevance ranking, and a trie for autocomplete suggestions.ProjectsSocial Network Analysis Using GraphsModel social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.Advanced TopicsTrie - Prefix Tree for Efficient SearchingMaster trie data structures for autocomplete and prefix-based searching.HeapsPriority Queue using HeapUnderstand the Priority Queue abstract data type, implement it with a binary heap, and explore real-world applications from task scheduling to graph algorithms.