DSA Primer
Data Structures and Algorithms is an essential subject for software engineers, and there is no shortage of learning materials out there. But it can be overwhelming sifting through it all. This DSA Primer, an expansion on this excellent reddit comment, is meant to be a brief refresher on some of the most frequently tested patterns in technical interviews.
Each common pattern is paired with a single problem for 27 problems in total. Problem sets like the Leetcode 75, Top Interview 150, or Neetcode 150 will offer more comprehensive preparation, but given limited time, I believe your time is best spent thoroughly understanding some of these core tactics and strategies, rather than spreading yourself too thin.
It will in no way replace a proper university course, nor will it suffice to prepare you for a really rigorous interview. But if you’re cramming last-minute, it might just give you enough preparation so that you don’t make a fool of yourself when you’re staring down a blank whiteboard.
Table of Contents
- Two Pointers: Used for finding pairs or elements that meet specific criteria.
- Sliding Window: Maintains a subset of elements within a larger dataset.
- Binary Search: Efficient searching in sorted arrays.
- Prefix Sum: Precompute cumulative sums for quick range queries.
- Depth-First Search (DFS): Preorder, inorder, and postorder traversals.
- Breadth-First Search (BFS): Level-order traversal.
- Binary Search Tree (BST) operations: Insertion, deletion, and validation.
- Tree construction: From preorder/inorder or postorder/inorder traversals.
- Frequency counting: Track occurrences of elements.
- Two Sum pattern: Find pairs with a specific sum.
- Anagram detection: Compare character frequencies.
- Caching: Store computed results for quick lookup.
- Depth-First Search (DFS): Explore paths deeply before backtracking.
- Breadth-First Search (BFS): Explore nodes level by level.
- Topological Sort: Order nodes in a directed acyclic graph.
- Union Find: Detect cycles and connect components.
- Parentheses matching: Validate balanced brackets.
- Monotonic stack: Maintain increasing/decreasing order for next greater/smaller element problems.
- Expression evaluation: Evaluate arithmetic expressions.
- BFS implementation: Level-order traversal in graphs and trees.
- Task scheduling: Manage order of operations.
- Sliding window problems: Maintain a window of elements.
- Top K Elements Pattern: Find or manipulate the K largest/smallest elements in a collection.
- Merge K Sorted Pattern: Combine K sorted lists or arrays into a single sorted list.
- Two Heaps Pattern: Use two heaps to track median or balance elements in a stream.
- Sliding Window Median Pattern: Calculate median in a sliding window over a stream of numbers.
- Scheduling Pattern: Manage tasks or intervals using a heap for efficient scheduling.
Additional Resources
Leetcode is the go-to source of practice problems. If you are new to algorithm practice, Leetcode 75 is the standard recommendation. If you have more time, the Top Interview 150 problem set is more comprehensive.
Neetcode is in many ways the ideal resource for new learners. Rather than throwing you in the deep end, Navi provides a structured curriculum that exposes you to the core concepts before presenting related problems. He only goes as deep as is necessary for practical application.
If and when you have the time to develop a deeper conceptual understanding, Teach Yourself CS offers excellent advice on how to approach it. And Oz Nova’s newer project CS Primer provides a full course including a section on algorithms. The content on problem-solving is especially helpful.