Preparing for coding interviews can be made easier by focusing on coding patterns. Every software engineer should learn coding patterns such as Sliding Window, Two Pointers, Two Heaps, etc. By doing so, software engineers will be able to develop the skill of “mapping a new problem to an existing one.” In this post, we will learn which coding patterns have the highest return on investment for software engineers.
Grokking the Coding Interview came up with a list of 18 patterns for coding questions based on the similarities in the techniques needed to solve them. The course’s idea is to teach famous coding patterns so that once someone is familiar with a pattern, they will be able to solve dozens of problems with it.
LeetCode (LC), being the largest repository of coding problems, contains more than 2k+ questions. Each question on LC can be tagged with one or more topics. These topics are either data structures like Array, HashTable, Tree, etc., or algorithmic techniques like Greedy, Divide and Conquer, Sorting, etc., or coding patterns like Sliding Window, Depth First Search, Topological Sort, etc. Here is the topic distribution for LC questions:
The top topic is Array with 1142 problems, followed by String with 549 problems, and so on. Let’s take a closer look at each category of topics, namely Data Structures, Algorithms, and Coding Patterns.
Here are the top Data Structures with the highest return on investment:
- Array (1142 problems)
- String (549)
- Hash Table (392)
- Tree (191)
- Matrix (171)
- Stack (128)
- Heap or Priority Queue (107)
- Graph (102)
- Linked List (69)
- Trie (44)
Here are the top algorithmic techniques with the highest return on investment:
- Dynamic Programming (383)
- Sorting (253)
- Greedy (248)
- Binary Search (186)
- Backtracking (91)
- Recursion (44)
- Divide and Conquer (38)
Here are the top coding patterns with the highest return on investment:
- Depth First Search (250)
- Breadth First Search(198)
- Binary Search (186)
- Two Pointers (147)
- Sliding Window (72)
- Monotonic Stack (44)
- Union Find (63)
- Memoization (32)
- Topological Sort (28)
- Segment Tree (27)
Combining all categories from the above data, here is the list of best coding patterns/techniques with the highest ROI:
1. Two Pointers (Arrays, Strings, Fast & Slow Pointer)
This pattern covers a huge set of questions related to Arrays and Strings, which are the highest tagged data structures. Fast & Slow Pointer can be easily understood as a variation of the Two Pointers pattern.
2. Sliding Window (Arrays, Strings, Hash Tables)
Sliding Window covers most of the problems related to top data structures like Arrays, Strings, and HashTables.
3. Tree and Graph Depth First Search (Matrix Traversal)
Most Trees and Graphs problems can be solved using Depth First Search (DFS). Matrix Traversal, which is also DFS based pattern, covers most of the matrix-related problems.
4. Tree and Graph Breadth First Search (Queue, Subsets, Matrix Traversal, Topological Sort)
Breadth First Search (BFS) is a very handy pattern. BFS’s patterns like Subsets, Matrix Traversal, and Topological Sort cover a good number of problems.
5. Binary Search (Arrays)
Binary Search and its variants are used to solve a huge number of coding questions.
6. Interval Merge
Although there are not many problems related to Interval Merge, these problems frequently appear in coding interviews.
Backtracking and recursion are used to solve a wide range of problems. Mastering these techniques is highly recommended.
Most programming interviews include LeetCode-type questions. Software engineers practice such coding problems before interviews. The highest return on investment is achieved by preparing smartly and focusing on the problem patterns. You can learn more about these patterns and related problems in Grokking the Coding Interview and Grokking Dynamic Programming for Coding Interviews.
Preparing for system design interviews, see this: The Complete Guide to Ace the System Design Interview