Mastering the Top Coding Patterns for FAANG Interviews
Welcome to the best guide on Mastering the Top Coding Patterns for FAANG Interviews!
After receiving multiple offers from esteemed companies like Apple, Citadel, JP Morgan, Google, Trainline, SkyScanner, OVO, HSBC, and Amazon, I couldn't wait to share the key factor that made it all possible!
Coding patterns.
All software engineers should learn coding patterns like Sliding Window, Two Pointers, Two Heaps, and more. Whether you're a beginner or seasoned coder, these patterns will empower you to tackle complex problems with confidence and precision. Let's dive in and discover the key to success in FAANG interviews!
What is LeetCode?
Before discussing coding patterns, it’s probably best to familiarise yourself with Leetcode. This is the largest repository of coding problems, containing more than 2,000 questions. Each question on LeetCode can be tagged with one or more topics. These topics fall into categories like Data Structures (e.g., Array, HashTable, Tree), Algorithmic Techniques (e.g., Greedy, Divide and Conquer, Sorting), or Coding Patterns (e.g., Sliding Window, Depth First Search, Topological Sort).
Here is the distribution of topics for LeetCode questions:
Array: 1142 problems
String: 549 problems
Hash Table: 392 problems
Tree: 191 problems
Matrix: 171 problems
Stack: 128 problems
Heap or Priority Queue: 107 problems
Graph: 102 problems
Linked List: 69 problems
Trie: 44 problems
Best Coding Patterns with Highest ROI (with Examples):
Coding patterns are techniques that are widely used in solving various coding problems. By recognising and mastering these patterns, you'll be able to quickly identify the approach to tackle a problem and map it to an existing one, drastically boosting your problem-solving skills.
Below, we will cover some coding patterns and will provide examples for each.
Sliding Window Pattern:
This pattern is particularly useful when it comes to dealing with subarray or substring problems. It involves maintaining a "window" over a given sequence and efficiently processing each element within that window.
Imagine you’re in an interview, and you’ve been asked to find the maximum sum of any contiguous subarray of length K, when given an array of numbers. In other words, in this list of numbers, what is the maximum sublist (and sublist here means that numbers must come one after another).
How would you solve this?
This is where the sliding window pattern comes in.
function maxSumSubarray(arr, K) {
let windowSum = 0;
let maxSum = 0;
for (let i = 0; i < arr.length; i++) {
windowSum += arr[i];
if (i >= K - 1) {
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[i - (K - 1)];
}
}
return maxSum;
}
Two Pointers Pattern:
The Two Pointers pattern is an efficient approach used with sorted arrays or linked lists. It involves maintaining two pointers that move towards each other to find a solution or satisfy a given condition. This pattern is used for things like removing duplicates, finding intersection of sorted arrays and finding sub arrays.
Let’s see an example.
The first exercise on Leetcode’s website introduces the two sum problem. This question states: “Given a sorted array, find if there are two elements that add up to your target”. We can solve this using the Two Sum pattern by doing the following:
function hasTwoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return true;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return false;
}
Tree and Graph Breadth First Search (Queue, Subsets, Matrix Traversal, Topological Sort):
The Breadth First Search (BFS) is another powerful technique used for tree and graph problems. It explores all the vertices at the present depth before moving on to the next level. BFS is also applied to problems like finding subsets, matrix traversal, and topological sorting.
It can also be applied to shortest path finding (finding shortest path between two vertices in an unweighted graph), social networking (finding connections between users or determining the degrees of separation between two individuals), garbage collection etc.
Let’s see an example!
Given a binary tree, return its level order traversal as an array of arrays.
class TreeNode {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
}
function levelOrderTraversal(root) {
if (!root) {
return [];
}
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
result.push(currentLevel);
}
return result;
}
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(levelOrderTraversal(root)); // Output: [[3], [9, 20], [15, 7]]
Binary Search (Arrays):
Binary Search is an efficient technique used to find a specific element in a sorted array. It divides the search space in half by repeatedly comparing the middle element with the target value.
This pattern is typically used for searching in sorted lists, finding upper or lower bounds of a list, divide and conquer algorithms and much more!
Let’s see this in action.
Given a sorted array, find the index of a target element. If the target is not found, return -1.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
const sortedArr = [2, 5, 8, 12, 16, 23, 38, 45];
const target = 16;
console.log(binarySearch(sortedArr, target)); // Output: 4
Conclusion
In conclusion, to ace programming interviews, it is crucial to practice LeetCode-type problems using coding patterns, undertake the Blind 75 Leetcode challenge, stick to one language, and solve real-world coding challenges.
In the world of programming interviews, preparing smartly and mastering problem patterns is the key to success.
Stay consistent, solve real-world challenges, and embrace the journey of growth. You've got this! Keep coding and shining brightly in your coding interviews!
Links:
Blind 75 Questions