DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL 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 — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete 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 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.
Project Overview
This project shows how different data structures solve different problems within a single application. A library management system needs to:
- Look up books by ISBN instantly → Hash Table
- Browse books in sorted order (by title/author) → Binary Search Tree
- Manage waitlists for popular books → Queue
- Support undo/redo for librarian actions → Stack
- Track borrow history for each member → Linked List
Let's build each component and see why that specific data structure is the right choice.
Component 1: Hash Table for Book Lookup
When someone walks up with an ISBN, you need O(1) lookup. A hash table maps ISBN → book details:
Example
class BookRecord:
def __init__(self, isbn, title, author, copies_total, copies_available):
self.isbn = isbn
self.title = title
self.author = author
self.copies_total = copies_total
self.copies_available = copies_available
class BookCatalog:
def __init__(self):
self.books = {} # ISBN -> BookRecord
def add_book(self, isbn, title, author, copies=1):
if isbn in self.books:
self.books[isbn].copies_total += copies
self.books[isbn].copies_available += copies
else:
self.books[isbn] = BookRecord(isbn, title, author, copies, copies)
def lookup(self, isbn):
"""O(1) lookup by ISBN."""
return self.books.get(isbn)
def is_available(self, isbn):
book = self.books.get(isbn)
return book is not None and book.copies_available > 0
def checkout(self, isbn):
book = self.books.get(isbn)
if book and book.copies_available > 0:
book.copies_available -= 1
return True
return False
def return_book(self, isbn):
book = self.books.get(isbn)
if book and book.copies_available < book.copies_total:
book.copies_available += 1
return True
return False
Why hash table? Libraries have thousands of books. Searching by ISBN must be instant — O(1) average. No other data structure gives us this for key-value lookup.
Component 2: BST for Sorted Catalog Browsing
Users want to browse books alphabetically or find books in a title range. A BST gives us sorted order naturally:
Example
class BSTNode:
def __init__(self, title, isbn):
self.title = title
self.isbn = isbn
self.left = None
self.right = None
class SortedCatalog:
def __init__(self):
self.root = None
def insert(self, title, isbn):
self.root = self._insert(self.root, title, isbn)
def _insert(self, node, title, isbn):
if not node:
return BSTNode(title, isbn)
if title < node.title:
node.left = self._insert(node.left, title, isbn)
elif title > node.title:
node.right = self._insert(node.right, title, isbn)
return node
def browse_alphabetical(self):
"""In-order traversal gives sorted order."""
results = []
self._inorder(self.root, results)
return results
def _inorder(self, node, results):
if node:
self._inorder(node.left, results)
results.append((node.title, node.isbn))
self._inorder(node.right, results)
def find_range(self, start_title, end_title):
"""Find all books with titles in [start, end] alphabetically."""
results = []
self._range_search(self.root, start_title, end_title, results)
return results
def _range_search(self, node, start, end, results):
if not node:
return
if start < node.title:
self._range_search(node.left, start, end, results)
if start <= node.title <= end:
results.append((node.title, node.isbn))
if node.title < end:
self._range_search(node.right, start, end, results)
Why BST? We need sorted order AND dynamic insertions. A sorted array gives browsing but O(n) inserts. A BST gives O(log n) for both (when balanced).
Component 3: Queue for Book Waitlists
When all copies are checked out, members join a waitlist. First-come, first-served — this is exactly FIFO (queue):
Example
from collections import deque
class WaitlistManager:
def __init__(self):
self.waitlists = {} # ISBN -> deque of member IDs
def join_waitlist(self, isbn, member_id):
if isbn not in self.waitlists:
self.waitlists[isbn] = deque()
self.waitlists[isbn].append(member_id)
position = len(self.waitlists[isbn])
return position # "You are #3 in line"
def notify_next(self, isbn):
"""When a book is returned, notify the next person in line."""
if isbn in self.waitlists and self.waitlists[isbn]:
next_member = self.waitlists[isbn].popleft()
return next_member # Send notification
return None
def get_position(self, isbn, member_id):
if isbn not in self.waitlists:
return -1
try:
idx = list(self.waitlists[isbn]).index(member_id)
return idx + 1
except ValueError:
return -1
def leave_waitlist(self, isbn, member_id):
if isbn in self.waitlists:
self.waitlists[isbn] = deque(
m for m in self.waitlists[isbn] if m != member_id
)
Why queue? Fairness demands first-come-first-served. A queue guarantees O(1) enqueue and dequeue while maintaining insertion order.
Component 4: Stack for Undo/Redo
Librarians make mistakes — check out to wrong member, add wrong book, etc. An undo system uses a stack:
Example
class Action:
def __init__(self, action_type, data):
self.action_type = action_type # "checkout", "return", "add_book"
self.data = data # dict with relevant info
class UndoRedoManager:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
def perform_action(self, action):
"""Execute an action and push to undo stack."""
self.undo_stack.append(action)
self.redo_stack.clear() # New action invalidates redo history
return self._execute(action)
def undo(self):
"""Undo the last action."""
if not self.undo_stack:
return "Nothing to undo"
action = self.undo_stack.pop()
self.redo_stack.append(action)
return self._reverse(action)
def redo(self):
"""Redo the last undone action."""
if not self.redo_stack:
return "Nothing to redo"
action = self.redo_stack.pop()
self.undo_stack.append(action)
return self._execute(action)
def _execute(self, action):
if action.action_type == "checkout":
return f"Checked out {action.data['isbn']} to {action.data['member']}"
elif action.action_type == "return":
return f"Returned {action.data['isbn']} from {action.data['member']}"
def _reverse(self, action):
if action.action_type == "checkout":
return f"UNDO: Returned {action.data['isbn']} from {action.data['member']}"
elif action.action_type == "return":
return f"UNDO: Re-checked out {action.data['isbn']} to {action.data['member']}"
Why stack? Undo is always "reverse the most recent action" — that is LIFO. The stack naturally gives us the most recent action on top.
Component 5: Linked List for Borrow History
Each member has a chronological history of borrowed books. We frequently add to the front (newest first) and display recent history:
python example
class HistoryNode:
def __init__(self, isbn, title, borrow_date, return_date=None):
self.isbn = isbn
self.title = title
self.borrow_date = borrow_date
self.return_date = return_date
self.next = None
class BorrowHistory:
def __init__(self, member_id):
self.member_id = member_id
self.head = None # Most recent borrow
self.count = 0
def add_borrow(self, isbn, title, date):
"""Add new borrow record at the front (most recent first)."""
node = HistoryNode(isbn, title, date)
node.next = self.head
self.head = node
self.count += 1
def mark_returned(self, isbn, return_date):
"""Mark a book as returned."""
current = self.head
while current:
if current.isbn == isbn and current.return_date is None:
current.return_date = return_date
return True
current = current.next
return False
def get_recent(self, n=10):
"""Get the n most recent borrow records."""
records = []
current = self.head
while current and len(records) < n:
records.append({
'isbn': current.isbn,
'title': current.title,
'borrowed': current.borrow_date,
'returned': current.return_date
})
current = current.next
return records
def currently_borrowed(self):
"""List all books not yet returned."""
borrowed = []
current = self.head
while current:
if current.return_date is None:
borrowed.append((current.isbn, current.title))
current = current.next
return borrowedWhy linked list? History is append-heavy and traversal-based. We never need random access to "the 47th book borrowed." We always traverse from recent to old. Linked list gives O(1) prepend and natural sequential traversal.
Putting It All Together
Example
class LibrarySystem:
def __init__(self):
self.catalog = BookCatalog()
self.sorted_catalog = SortedCatalog()
self.waitlists = WaitlistManager()
self.undo_manager = UndoRedoManager()
self.member_history = {} # member_id -> BorrowHistory
def add_book(self, isbn, title, author, copies=1):
self.catalog.add_book(isbn, title, author, copies)
self.sorted_catalog.insert(title, isbn)
def checkout_book(self, isbn, member_id, date):
if self.catalog.checkout(isbn):
# Record history
if member_id not in self.member_history:
self.member_history[member_id] = BorrowHistory(member_id)
book = self.catalog.lookup(isbn)
self.member_history[member_id].add_borrow(isbn, book.title, date)
# Track for undo
action = Action("checkout", {"isbn": isbn, "member": member_id})
self.undo_manager.perform_action(action)
return True
else:
# Book not available — add to waitlist
position = self.waitlists.join_waitlist(isbn, member_id)
return f"Added to waitlist at position {position}"
Lessons Learned
This project demonstrates the right tool for the right job principle:
- Hash tables for key-based lookup
- BSTs for sorted access patterns
- Queues for fairness/ordering
- Stacks for reversal/undo
- Linked lists for sequential history
No single data structure does everything well. Good software engineering means choosing the right structure for each access pattern.
Continue the lesson path
Study next in this module
01ProjectsAutocomplete System Using TrieBuild a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.02ProjectsRoute Finder Using GraphsBuild a route-finding application using graph data structures, Dijkstra\03ProjectsMini 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.04ProjectsSocial Network Analysis Using GraphsModel social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.