Useful roadmap and resources https://roadmap.sh/datastructures-and-algorithms
study plan
Data Structures and Algorithms Study Plan¶
Core Data Structures¶
1. Arrays¶
- Static vs. Dynamic Arrays
- Key operations:
- Insertion
- Deletion
- Searching (linear, binary)
- Time complexities
- Common problems:
- Two-pointer techniques
- Sliding window
- Prefix sum
- Practice problems:
- Maximum subarray sum
- Rotate array
- Merge sorted arrays
2. Linked Lists¶
- Singly vs. Doubly Linked Lists
- Operations:
- Insertion
- Deletion
- Reversal
- Types:
- Circular linked lists
- Dummy node techniques
- Time complexities
- Common problems:
- Detect cycle
- Find middle element
- Merge two sorted lists
- Implement LRU cache
3. Stacks¶
- LIFO principle
- Implementation methods
- Use cases:
- Expression evaluation
- Parsing
- Backtracking
- Key problems:
- Valid parentheses
- Implement queue using stacks
- Monotonic stack problems
4. Queues¶
- FIFO principle
- Types:
- Simple queue
- Circular queue
- Priority queue
- Implementation techniques
- Use cases:
- BFS
- Job scheduling
- Key problems:
- Implement stack using queues
- First unique character
- Sliding window maximum
5. Hash Tables¶
- Hash function principles
- Collision resolution:
- Chaining
- Open addressing
- Time complexities
- Key problems:
- Two sum
- Group anagrams
- First recurring character
- Implement cache
6. Trees¶
Binary Trees¶
- Traversals:
- Inorder
- Preorder
- Postorder
- Balance concepts
- Key operations:
- Height calculation
- Depth calculation
Binary Search Trees (BST)¶
- Insertion
- Deletion
- Searching
- Balancing techniques
- Key problems:
- Validate BST
- Lowest common ancestor
- Kth smallest element
Advanced Tree Structures¶
- AVL Trees
- Red-Black Trees
- Trie
- Heap
7. Graphs¶
- Representation methods:
- Adjacency list
- Adjacency matrix
- Traversal algorithms:
- DFS
- BFS
- Shortest path algorithms:
- Dijkstra's
- Bellman-Ford
- Minimum spanning tree:
- Kruskal's
- Prim's algorithm
- Key problems:
- Course schedule
- Number of islands
- Detect cycle
- Topological sorting
Algorithmic Paradigms¶
1. Sorting Algorithms¶
- Comparison sorts:
- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
- Non-comparison sorts:
- Counting sort
- Radix sort
- Time and space complexities
- Stability concepts
2. Searching Algorithms¶
- Linear search
- Binary search
- Depth-first search
- Breadth-first search
3. Dynamic Programming¶
- Recursive vs. iterative approaches
- Memoization techniques
- Key problem types:
- Knapsack
- Longest common subsequence
- Coin change
- Maximum subarray
4. Greedy Algorithms¶
- Problem-solving approach
- Optimization techniques
- Key problems:
- Activity selection
- Fractional knapsack
- Huffman coding