DSA with Python

6 subjects · 14 chapters · 56 topics

1. 01

   Foundations

   1.1 Python for problem solving

   • Lists, tuples, sets and dictionaries
   • Slicing, comprehensions and generators
   • Classes and magic methods
   • Reading input fast

   1.2 Complexity

   • Big-O, big-theta and big-omega
   • Time versus space trade-offs
   • Amortised analysis
   • Estimating before you code
2. 02

   Linear Data Structures

   2.1 Arrays and strings

   • Two pointers
   • Sliding window
   • Prefix sums
   • In-place manipulation

   2.2 Linked lists

   • Singly and doubly linked lists
   • Reversal and cycle detection
   • Merging and partitioning
   • Fast and slow pointers

   2.3 Stacks and queues

   • Stack applications
   • Monotonic stack
   • Queues and deques
   • Priority queues with heapq
3. 03

   Recursion and Searching

   3.1 Recursion

   • Base cases and recurrence
   • Backtracking
   • Subsets and permutations
   • Recursion to iteration

   3.2 Searching and sorting

   • Binary search and its variants
   • Search on the answer
   • Merge sort and quick sort
   • Counting and bucket sort
4. 04

   Non-linear Structures

   4.1 Trees

   • Binary trees and traversals
   • Binary search trees
   • Balanced trees and heaps
   • Tries

   4.2 Graphs

   • Representation: list and matrix
   • BFS and DFS
   • Topological sort
   • Shortest paths: Dijkstra and Bellman-Ford

   4.3 Union-Find

   • Disjoint set union
   • Path compression and union by rank
   • Cycle detection
   • Minimum spanning trees
5. 05

   Dynamic Programming and Greedy

   5.1 Dynamic programming

   • Memoisation and tabulation
   • 1D problems: climbing stairs, house robber
   • 2D problems: grids and edit distance
   • Knapsack family

   5.2 Greedy

   • When greedy is correct
   • Interval scheduling
   • Huffman coding
   • Exchange argument proofs
6. 06

   Interview Practice

   6.1 Patterns

   • Recognising the pattern behind a problem
   • Choosing the right structure
   • Handling edge cases
   • Explaining your approach aloud

   6.2 Mock rounds

   • Timed problem sets
   • Optimising a working solution
   • Common follow-up questions
   • A final assessment