https://www.greatfrontend.com/
https://leetcode.com/studyplan/top-interview-150/
Essential Coding Templates for FAANG-Level LeetCode Problems
Cracking FAANG-level coding interview questions can be daunting, but having a solid set of templates can significantly boost your confidence and efficiency. In this article, I’ll share essential algorithms and data structure templates with challenging examples, designed to prepare you for top-tier tech interviews.
Array / String
Problem: Longest Substring Without Repeating Characters
Find the length of the longest substring without repeating characters.
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
Two Pointers
Problem: Container With Most Water
Given an array of heights, find the maximum area of water that can be contained.
function maxArea(height) {
let left = 0, right = height.length - 1, maxArea = 0;
while (left < right) {
const minHeight = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, minHeight * (right - left));
if (height[left] < height[right]) left++;
else right--;
}
return maxArea;
}
Sliding Window
Problem: Minimum Window Substring
Find the smallest substring in s that contains all characters of t.
function minWindow(s, t) {
const need = new Map();
for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
let have = new Map();
let left = 0, minLen = Infinity, result = "";
let count = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
have.set(ch, (have.get(ch) || 0) + 1);
if (need.has(ch) && have.get(ch) === need.get(ch)) count++;
while (count === need.size) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
result = s.substring(left, right + 1);
}
have.set(s[left], have.get(s[left]) - 1);
if (need.has(s[left]) && have.get(s[left]) < need.get(s[left])) count--;
left++;
}
}
return result;
}
Matrix
Problem: Rotate Image
Rotate an n x n matrix by 90 degrees clockwise.
function rotate(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
for (let row of matrix) {
row.reverse();
}
}
Hashmap
Problem: Two Sum
Find two numbers in an array that add up to a target.
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) return [map.get(complement), i];
map.set(nums[i], i);
}
return [];
}
Intervals
Problem: Merge Intervals
Merge overlapping intervals.
function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const merged = [];
for (const interval of intervals) {
if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
merged.push(interval);
} else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
}
}
return merged;
}
Stack
Problem: Valid Parentheses
Check if a string has valid parentheses.
function isValid(s) {
const stack = [];
const map = { ')': '(', ']': '[', '}': '{' };
for (const ch of s) {
if (map[ch]) {
if (stack.pop() !== map[ch]) return false;
} else {
stack.push(ch);
}
}
return stack.length === 0;
}
Linked List
Problem: Detect Cycle
Determine if a linked list has a cycle.
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
Binary Tree - Traversal
Problem: Inorder Traversal
Traverse a binary tree inorder.
function inorder(root) {
if (!root) return [];
return [...inorder(root.left), root.val, ...inorder(root.right)];
}
Binary Tree BFS
Problem: Level Order Traversal
Return nodes level-by-level.
function levelOrder(root) {
const result = [];
if (!root) return result;
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
Binary Search Tree
Problem: Insert into BST
Insert a node into a BST.
function insertIntoBST(root, val) {
if (!root) return new TreeNode(val);
if (val < root.val) root.left = insertIntoBST(root.left, val);
else root.right = insertIntoBST(root.right, val);
return root;
}
Graph - General
Problem: DFS Traversal
Perform DFS on a graph.
function dfsGraph(node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
// process node here
for (const neighbor of graph[node]) {
dfsGraph(neighbor, visited);
}
}
Graph BFS
// BFS traversal
function bfsGraph(start) {
const visited = new Set();
const queue = [start];
while (queue.length) {
const node = queue.shift();
if (visited.has(node)) continue;
visited.add(node);
// process node here
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) queue.push(neighbor);
}
}
}
Trie
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
node = node.children.get(ch);
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) return false;
node = node.children.get(ch);
}
return node.isEndOfWord;
}
}
Backtracking
// N-Queens
function solveNQueens(n) {
const board = Array.from({ length: n }, () => Array(n).fill('.'));
const results = [];
function isValid(row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
if (Math.abs(i - row) === Math.abs(board[i].indexOf('Q') - col)) return false;
}
return true;
}
function backtrack(row = 0) {
if (row === n) {
results.push(board.map(r => r.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (isValid(row, col)) {
board[row][col] = 'Q';
backtrack(row + 1);
board[row][col] = '.';
}
}
}
backtrack();
return results;
}
Divide & Conquer
// Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
}
Kadane’s Algorithm (Maximum Subarray)
function maxSubArray(nums) {
let maxEndingHere = nums[0], maxSoFar = nums[0];
for (let i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
Binary Search
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
Heap (Priority Queue)
// Kth Largest Element using Min Heap
class MinHeap {
constructor() {
this.heap = [];
}
insert(val) {
this.heap.push(val);
this.heapifyUp();
}
extractMin() {
if (this.heap.length === 0) return null;
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.heapifyDown();
}
return min;
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIdx = Math.floor((index - 1) / 2);
if (this.heap[parentIdx] <= this.heap[index]) break;
[this.heap[parentIdx], this.heap[index]] = [this.heap[index], this.heap[parentIdx]];
index = parentIdx;
}
}
heapifyDown() {
let index = 0;
const length = this.heap.length;
while (true) {
let leftIdx = 2 * index + 1;
let rightIdx = 2 * index + 2;
let smallest = index;
if (leftIdx < length && this.heap[leftIdx] < this.heap[smallest]) smallest = leftIdx;
if (rightIdx < length && this.heap[rightIdx] < this.heap[smallest]) smallest = rightIdx;
if (smallest === index) break;
[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
index = smallest;
}
}
}
function findKthLargest(nums, k) {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.heap.length > k) minHeap.extractMin();
}
return minHeap.heap[0];
}
Bit Manipulation
// Single Number - XOR of all elements
function singleNumber(nums) {
let result = 0;
for (const num of nums) {
result ^= num;
}
return result;
}
Math
// Greatest Common Divisor (Euclidean Algorithm)
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
1D Dynamic Programming
// Climbing Stairs
function climbStairs(n) {
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Multidimensional Dynamic Programming
// Unique Paths in a Grid
function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
Wrap Up
Having these templates at your fingertips can streamline your problem-solving process and help you handle even the most challenging FAANG-level questions. Practice applying them to different problems to strengthen your understanding.
Happy coding!
Top comments (0)