Mastering data structures and algorithms is faster when you use a focused cheat sheet that highlights the most common patterns. This reference helps you compare, recall, and apply key concepts during interviews, daily coding, and system design.
A well organized reference turns scattered notes into a practical tool for brushing up on core topics. The following sections group the essentials by structures, techniques, and common problem areas to support efficient revision.
| Category | Structure or Technique | Best For | Time Complexity (Typical) |
|---|---|---|---|
| Linear Structures | Array | Random access, sliding windows | Access O(1), Search O(n) |
| Linear Structures | Linked List | Frequent insertions and deletions | Access O(n), Insert/Delete O(1) with pointer |
| Hierarchical Structures | Binary Tree | Divide and conquer, recursion | Traversal O(n) |
| Hierarchical Structures | Binary Search Tree | Ordered data with dynamic updates | Avg Search/Insert O(log n), Worst O(n) |
| Hierarchical Structures | Heap (Priority Queue) | Efficient min/max access | Insert O(log n), Extract Min/Max O(log n) |
| Hashing | Hash Map / Hash Set | Fast lookup and deduplication | Avg Insert/Search O(1), Worst O(n) |
| Graph Representations | Adjacency List | Sparse graphs, efficient edge traversal | Space O(V + E) |
| Graph Representations | Adjacency Matrix | Dense graphs, quick edge queries | Space O(V²) |
Arrays and Sliding Window Patterns
Arrays provide constant time access by index and are the foundation for many two pointer and sliding window techniques. Use them when data is ordered and random reads are frequent.
Sliding window helps reduce nested loops by maintaining a range that satisfies a condition. Typical use cases include maximum subarray sum, fixed or variable length substring problems, and optimizing brute force solutions.
Linked Lists and Pointer Manipulation
Linked lists excel at scenarios with frequent head or middle insertions and deletions. Unlike arrays, they do not require contiguous memory but sacrifice random access.
Common pointer manipulation patterns include reversing a list in place, detecting cycles with fast and slow pointers, and merging multiple sorted lists using a min heap.
Trees, Graphs, and DFS BFS Strategies
Binary trees support recursive divide and conquer strategies, while binary search trees maintain order for efficient searching. Understanding traversal orders is essential for tree problems.
Graph algorithms rely on depth first search and breadth first search to explore nodes systematically. Choose DFS for path existence and topology, and BFS for shortest paths in unweighted graphs.
Hashing and Frequency Counting Techniques
Hash maps and hash sets provide average constant time operations for lookups and deduplication. They are ideal for counting frequencies, checking presence, and grouping anagrams.
When designing solutions, consider hash collisions and memory tradeoffs. Combining hashing with other structures can simplify complex lookups and improve overall performance.
Core Takeaways for Interview Preparation
- Understand the strengths and limitations of each core data structure
- Practice recognizing patterns such as sliding window, two pointers, and DFS BFS
- Memorize standard time and space complexities for common operations
- Implement basic structures like arrays, linked lists, and hash maps from scratch
- Run through edge cases and optimize brute force solutions systematically
FAQ
Reader questions
How do I choose between array and linked list for a problem?
Prefer arrays when you need random access and iterate sequentially, and choose linked lists when insertions and deletions happen frequently at known positions.
What is the best first step when optimizing a brute force solution?
Analyze the time complexity, identify repeated work, and consider caching results with hashing or reducing nested loops using two pointers or sliding window.
When should I use BFS instead of DFS on a graph?
Use BFS to find shortest paths in unweighted graphs, and prefer DFS when exploring all possibilities, detecting cycles, or working with recursion depth limits.
Can a single problem use multiple data structures together?
Yes, combining structures such as hash maps with heaps or trees is common to balance fast lookup, ordering, and efficient updates in complex solutions.