20 Basic Coding Patterns You Need To Keep Handy
Interviews for programmers are getting more difficult daily. It was more than sufficient to prepare for an interview a few years ago by studying important data structures and working through 50–75 coding interview questions. Today, everyone has access to massive sets of coding problems, and they’re no less than weathering the storm. These interview processes nowadays are like jumping out of the frying pan and into the fire.
While starting from scratch can be challenging, there are coding challenges that can help you test and improve your skills. Programmers tend to improve their knowledge, hone their abilities, and get ready for programming job interviews. The one skill that helps the most when preparing for coding interviews is the ability to map a new problem to an already-known problem.
But no one really likes spending that much time preparing for the coding interviews. So is there a smarter solution?
Everyone preparing for coding interviews must be familiar with websites like LeetCode or CodeChef or HackerRank. These websites are most likely the largest collection of coding interview questions available online. Let’s examine the issues programmers encounter.
Have You Realized That There’s A Catch With Coding Platforms Too?
There are over 7k problems on these websites of coding problems. But the biggest challenge with these websites is the lack of organisation; it has huge sets of problems and one isn’t aware of where to start from or what to focus leaving the programmer wandering in the wilderness.
One wonders what is the adequate number of questions one should go through to consider themselves on the top of the game.
Every programmer would love to see a streamlined process that leads and instructs them on sufficient algorithmic approaches offering them a vote of confidence.
Let’s Square The Circles Because There’s Always A Solution!
One technique that is frequently used in solving questions related to the same data structure; for example, focusing on questions related to Arrays, then LinkedList, HashMap, Heap, Tree, Graph, or Trie, etc. Although this does offer some organization, it is still inconsistent. For instance, HashMaps can be used to address a lot of problems, but they still call for other algorithmic methods.
The problem-solving techniques such as Sliding Window, Fast and Slow Pointers, Two Pointers, Two Heaps, Topological Sort, etc. are the best. Mapping a new problem into an already-known problem would develop a programmer's skill exponentially. This will not only make the process of preparing for the interview and coding enjoyable, but it will also make it much more structured.
Coding patterns enhance our “ability to map a new problem to an already known problem.”
20 Key Coding Patterns That Will Guide You Through
Anyone can master these incredible algorithmic strategies and really excel in coding interviews by using roughly 20 of these coding issue patterns that are compiled here.
The idea behind these patterns is that one can use a pattern to solve dozens of issues once one becomes familiar with it.
Without further ado, let us enumerate each of these patterns:
1. Sliding Window
Usage: This algorithmic technique is used when we need to handle the input of the data in a specific window size.
DS involved: Array, String, HashTable
Sample Problems: Longest Substring with ‘K’ distinct characters, Fruits into baskets
2. Islands (Matrix Traversal)
Usage: This pattern describes all the efficient ways of traversing a matrix (or 2D array).
DS involved: Matrix, Queue
Sample Problem: Number of Islands, Flood Fill, Cycle in a matrix
3. Two Pointers
Usage: This technique uses two pointers to iterate input data. Generally, both pointers move in the opposite direction at a constant interval.
DS involved: Array, String, LinkedLists
Sample Problems: Squaring a Sorted Array, Dutch National Flag Problem, Minimum Window Sort
4. Fast & Slow Pointers
Usage: Also known as Hare & Tortoise algorithm. This technique uses two pointers that traverse the input data at different speeds.
DS involved: Array, String, LinkedList
Sample Problems: Middle of the LinkedList, Happy Number, Cycle in a Circular Array
5. Merge Intervals
Usage: This technique is used to deal with overlapping intervals.
DS involved: Array, Heap
Sample Problems: Conflicting Appointments, Minimum Meeting Rooms
6. Cyclic Sort
Usage: Use this technique to solve array problems where the input data lies within a fixed range.
DS involved: Array
Sample Problems: Find All Missing Numbers, Find All Duplicate Numbers, Find the First K mIssing Positive Numbers
7. In-place Reversal of a LinkedList
Usage: This technique provides an efficient way to reverse the links between a set of nodes of a LinkedList. Often, the constraint is that we need to do this in place, i.e., using the existing node objects and without using extra memory.
DS involved: LinkedList
Sample Problems: Reverse every K-element Sub-list
8. Tree Breadth-First Search
Usage: This technique is used to solve problems involving traversing trees or graphs in a breadth-first search manner.
DS involved: Trees, Graph, Matrix, Queue
Sample Problems: Binary Tree Level Order Traversal, Minimum Depth of a Binary Tree, Connect Level Order Siblings
9. Tree Depth First Search
Usage: This technique is used to solve problems involving how traversing trees or graphs in a depth-first searching manner.
DS involved: Trees, Graphs, Matrix
Sample Problems: Path With Given Sequence, Count Paths for a sum
10. Two Heaps
Usage: In many problems, we are given a set of elements that can be divided into two parts. We are interested in knowing the smallest element in one part and the biggest element in the other part. As the name suggests, this technique uses a Min-Heap to find the smallest element and a Max-Heap to find the biggest element.
DS involved: Heap, Array
Sample Problems; Find the median of a number system, Next Interval
11. Subsets
Usage: Use this technique when the problem asks to deal with permutations or combinations of a set of elements.
DS Involved: Queue, Array, String
Sample Problems: String permutations by changing case, Unique Generalized Abbreviations
12. Modified Binary Search
Usage: Use this technique to search a sorted set of elements efficiently.
DS involved: Array
Sample Problems: Ceiling of a Number, Bitonic Array Maximum
13. Bitwise XOR
Usage: This technique uses the XOR operator to manipulate bits to solve problems.
DS involved: Array, Bits
Sample Problems: Two Single Numbers, Flip and Invert an Image
14. Top ‘K’ Elements
Usage: This technique is used to find the top/smallest/frequently occurring ’K’ elements in a set.
DS involved: Array, Heap, Queue
Sample Problems: ‘K’ Closest Points to the Origin, Maximum Distinct Elements
15. K-way Merge
Usage: This technique helps us to solve problems that involve a list of sorted arrays.
DS involved: Array, Queue, Heap
Sample Problems: Kth Smallest Number in M sorted Lists, Kth Smallest Numbers in a Sorted Matrix
16. Topological Sort
Usage: This technique is used to find a linear ordering of elements that have dependencies on each other.
DS involved: Array, HashTable, Queue, Graph
Sample Problems: Tasks Scheduling, Alien Dictionary
17. 0/1 Knapsack
Usage: This technique is used to solve optimization problems. Use this technique to select elements that give maximum profit from a given set with limitations on capacity and that each element can only be picked once.
DS involved: Array, HashTable
Sample Problems: Equal Subset Sum Partition, Minimum Subset Sum Difference
18. Fibonacci Numbers
Usage: Use this technique to solve problems that follow the Fibonacci numbers sequence, i.e., every subsequent number is calculated from the last few numbers.
DS involved: Array, HashTable
Sample Problems: Staircase, HouseTheif
19. Palindromic Subsequence
Usage: This technique is used to solve optimization problems related to palindromic sequences or strings.
DS involved: Array, HashTable
Sample Problems: Longest Palindromic Subsequence, Minimum Deletions in a String to make it a Palindrome
20. Longest Common Substring
Usage: Use this string technique to find the optimal part of a string/sequence or set of strings/ sequences.
DS involved: Array, HashTable
Sample Problems: Maximum Sum Increasing Subsequence, Edit Distance
Conclusion
Call it a lucky streak or a programmer's practice questions from such websites as LeetCode or CodeChef or HackerRank before an interview because, like it or not, they are asked in almost all programming interviews.
Even when it’s actually clear if a problem can be solved using these patterns, it can be pretty challenging to even know where to start on the solution. Rather than just trying to memorize solutions, walk through these easy-to-understand techniques to handle any DSA problem. Their best bet is to be well-prepared and acquire the skill of problem-solving by concentrating on the fundamental patterns of the problems, if not then even the fickle finger of fate might intervene.