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 mini search engine from scratch using an inverted index (hash map), TF-IDF scoring for relevance ranking, and a trie for autocomplete suggestions.
What We Are Building
A search engine does three things: (1) indexes documents so they are searchable, (2) finds relevant documents for a query, and (3) ranks them by relevance. We will build all three using fundamental data structures:
- Inverted Index (Hash Map): Maps each word to the list of documents containing it
- TF-IDF Scoring: Ranks results by how important a word is to a document
- Trie: Provides autocomplete suggestions as the user types
Part 1: The Inverted Index
An inverted index is the backbone of every search engine. Instead of scanning every document for every query (O(n × d) where n is documents and d is average doc length), we precompute a mapping: word → list of documents.
Example
import re
import math
from collections import defaultdict, Counter
class InvertedIndex:
def __init__(self):
self.index = defaultdict(set) # word -> set of doc_ids
self.documents = {} # doc_id -> original text
self.doc_word_counts = {} # doc_id -> Counter of words
self.doc_lengths = {} # doc_id -> total word count
self.num_docs = 0
def tokenize(self, text):
"""Split text into lowercase words, remove punctuation."""
text = text.lower()
words = re.findall(r'[a-z0-9]+', text)
# Remove common stop words
stop_words = {'the', 'a', 'an', 'is', 'are', 'was', 'were', 'in', 'on',
'at', 'to', 'for', 'of', 'and', 'or', 'but', 'it', 'this'}
return [w for w in words if w not in stop_words and len(w) > 1]
def add_document(self, doc_id, text):
"""Index a document."""
self.documents[doc_id] = text
tokens = self.tokenize(text)
self.doc_word_counts[doc_id] = Counter(tokens)
self.doc_lengths[doc_id] = len(tokens)
self.num_docs += 1
# Update inverted index
for word in set(tokens):
self.index[word].add(doc_id)
def search(self, query):
"""Find documents containing ALL query words."""
query_tokens = self.tokenize(query)
if not query_tokens:
return []
# Intersection of document sets for each query word
result_sets = [self.index.get(word, set()) for word in query_tokens]
if not result_sets:
return []
matching_docs = result_sets[0]
for s in result_sets[1:]:
matching_docs = matching_docs.intersection(s)
return list(matching_docs)
Why hash map? Looking up which documents contain a word is O(1) with a hash map. Without an index, we would need to scan every document for every query — unusable at scale.
Part 2: TF-IDF Relevance Scoring
Not all matches are equally relevant. A document mentioning "algorithm" 10 times is more relevant to the query "algorithm" than one mentioning it once. TF-IDF captures this:
- TF (Term Frequency): How often does the word appear in THIS document?
- IDF (Inverse Document Frequency): How rare is this word across ALL documents?
A word that appears in every document (like "the") has low IDF. A word that appears in few documents (like "quicksort") has high IDF.
Example
class TFIDFRanker:
def __init__(self, index):
self.index = index
def tf(self, word, doc_id):
"""Term frequency: word count / total words in document."""
count = self.index.doc_word_counts[doc_id].get(word, 0)
total = self.index.doc_lengths[doc_id]
return count / total if total > 0 else 0
def idf(self, word):
"""Inverse document frequency: log(total_docs / docs_containing_word)."""
doc_freq = len(self.index.index.get(word, set()))
if doc_freq == 0:
return 0
return math.log(self.index.num_docs / doc_freq)
def tf_idf(self, word, doc_id):
"""TF-IDF score for a word in a document."""
return self.tf(word, doc_id) * self.idf(word)
def rank_documents(self, query, doc_ids):
"""Rank documents by relevance to query using TF-IDF."""
query_tokens = self.index.tokenize(query)
scores = []
for doc_id in doc_ids:
score = sum(self.tf_idf(word, doc_id) for word in query_tokens)
scores.append((doc_id, score))
# Sort by score descending
scores.sort(key=lambda x: -x[1])
return scores
Part 3: Trie for Query Autocomplete
As the user types, we suggest completions based on previously indexed words:
Example
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
self.doc_frequency = 0 # How many documents contain this word
class SearchTrie:
def __init__(self):
self.root = TrieNode()
def insert(self, word, doc_freq=1):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
node.doc_frequency = doc_freq
def suggest(self, prefix, max_results=5):
"""Get word suggestions for a prefix."""
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
# DFS to find all words under this prefix
suggestions = []
self._collect(node, prefix, suggestions)
# Sort by document frequency (popularity)
suggestions.sort(key=lambda x: -x[1])
return [word for word, freq in suggestions[:max_results]]
def _collect(self, node, current_word, results):
if node.is_word:
results.append((current_word, node.doc_frequency))
for char, child in node.children.items():
self._collect(child, current_word + char, results)
Putting It All Together: The Search Engine
Example
class MiniSearchEngine:
def __init__(self):
self.index = InvertedIndex()
self.ranker = TFIDFRanker(self.index)
self.trie = SearchTrie()
def index_document(self, doc_id, text):
"""Add a document to the search engine."""
self.index.add_document(doc_id, text)
# Update trie with words from this document
for word in set(self.index.tokenize(text)):
doc_freq = len(self.index.index[word])
self.trie.insert(word, doc_freq)
def search(self, query, top_k=5):
"""Search for documents matching the query, ranked by relevance."""
matching_docs = self.index.search(query)
if not matching_docs:
return []
ranked = self.ranker.rank_documents(query, matching_docs)
results = []
for doc_id, score in ranked[:top_k]:
results.append({
'doc_id': doc_id,
'score': round(score, 4),
'snippet': self.index.documents[doc_id][:150] + '...'
})
return results
def autocomplete(self, prefix):
"""Suggest query completions."""
return self.trie.suggest(prefix.lower())
# Demo
engine = MiniSearchEngine()
docs = {
1: "Binary search is an efficient algorithm for finding items in sorted arrays. It works by repeatedly dividing the search interval in half.",
2: "Merge sort is a divide and conquer algorithm that splits arrays into halves, sorts each half, then merges them back together.",
3: "Hash tables provide constant time average lookup by mapping keys to indices using a hash function. Collisions are handled with chaining or open addressing.",
4: "Graph algorithms like BFS and DFS traverse nodes systematically. BFS uses a queue for level-order traversal while DFS uses a stack.",
5: "Dynamic programming solves problems by breaking them into overlapping subproblems and storing results to avoid redundant computation."
}
for doc_id, text in docs.items():
engine.index_document(doc_id, text)
# Search
results = engine.search("algorithm sort")
for r in results:
print(f"Doc {r['doc_id']} (score: {r['score']}): {r['snippet']}")
# Autocomplete
print(engine.autocomplete("sor")) # ['sort', 'sorted', 'sorting']
Complexity Analysis
| Operation | Time Complexity | Data Structure Used |
|---|---|---|
| Index a document | O(d) where d = doc length | Hash Map |
| Search (find matches) | O(q) where q = query words | Hash Map (intersection) |
| Rank results | O(r × q) where r = result count | TF-IDF computation |
| Autocomplete | O(p + w) where p = prefix, w = words with prefix | Trie |
Extensions for Real-World Use
- Phrase search: Store word positions in the index to match exact phrases
- Stemming: Reduce "running," "runs," "ran" to common root "run"
- Spell correction: Use edit distance on trie nodes for "did you mean?"
- PageRank: For web search, combine TF-IDF with link-based authority
- Distributed indexing: Shard the inverted index across machines for billions of documents
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Mini Search Engine Project.
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, search, engine
Related Data Structures & Algorithms Topics
Continue learning this concept
ProjectsAutocomplete System Using TrieBuild a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.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\ProjectsSocial Network Analysis Using GraphsModel social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.SearchingBinary Search - Efficient SearchingMaster binary search algorithm with variations, problems, and optimization techniques.SearchingInterpolation Search - Intelligent SearchingUnderstand interpolation search for uniformly distributed data with superior average performance.