DEV Community

Dev Cookies
Dev Cookies

Posted on

The Ultimate Guide to DSA Patterns for Top Tech Company Interviews

Landing a job at top tech companies like Google, Amazon, Microsoft, Facebook (Meta), Apple, Netflix, or startups requires mastering specific Data Structures and Algorithms (DSA) patterns. This comprehensive guide covers all the essential patterns with real Java examples from actual interviews and direct LeetCode links.

Table of Contents

  1. Two Pointers Pattern
  2. Sliding Window Pattern
  3. Fast & Slow Pointers Pattern
  4. Merge Intervals Pattern
  5. Cyclic Sort Pattern
  6. In-place Reversal of LinkedList
  7. Tree Breadth-First Search (BFS)
  8. Tree Depth-First Search (DFS)
  9. Two Heaps Pattern
  10. Subsets Pattern
  11. Modified Binary Search
  12. Bitwise XOR Pattern
  13. Top K Elements
  14. K-way Merge
  15. Dynamic Programming Patterns
  16. Topological Sort
  17. Graph Algorithms
  18. Trie Pattern
  19. Union Find (Disjoint Set)
  20. Backtracking Pattern

1. Two Pointers Pattern

When to use: When dealing with sorted arrays, palindromes, or when you need to find pairs/triplets with specific conditions.

Time Complexity: Usually O(n) or O(n²)
Space Complexity: O(1)

Key Problems & Companies:

Two Sum II - Input Array Is Sorted 

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[]{-1, -1};
}
Enter fullscreen mode Exit fullscreen mode

3Sum

  • Companies: Amazon, Google, Microsoft, Facebook, Apple, Uber, LinkedIn
  • Difficulty: Medium
  • Interview Frequency: Very High
  • LeetCode: 15. 3Sum 
public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}
Enter fullscreen mode Exit fullscreen mode

Container With Most Water

Valid Palindrome

More Two Pointers Problems:

2. Sliding Window Pattern

When to use: When dealing with subarrays/substrings with specific conditions (max/min length, sum, distinct characters).

Time Complexity: O(n)
Space Complexity: O(1) to O(k)

Key Problems & Companies:

Longest Substring Without Repeating Characters 

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charMap = new HashMap<>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        char rightChar = s.charAt(right);

        if (charMap.containsKey(rightChar) && charMap.get(rightChar) >= left) {
            left = charMap.get(rightChar) + 1;
        }

        charMap.put(rightChar, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}
Enter fullscreen mode Exit fullscreen mode

Minimum Window Substring

  • Companies: Google, Facebook, Amazon, Microsoft, Uber, LinkedIn
  • Difficulty: Hard
  • Interview Frequency: High
  • LeetCode: 76. Minimum Window Substring 
public String minWindow(String s, String t) {
    if (s.length() == 0 || t.length() == 0) return "";

    Map<Character, Integer> dictT = new HashMap<>();
    for (char c : t.toCharArray()) {
        dictT.put(c, dictT.getOrDefault(c, 0) + 1);
    }

    int required = dictT.size();
    int left = 0, right = 0;
    int formed = 0;

    Map<Character, Integer> windowCounts = new HashMap<>();

    int[] ans = {-1, 0, 0}; // length, left, right

    while (right < s.length()) {
        char character = s.charAt(right);
        windowCounts.put(character, windowCounts.getOrDefault(character, 0) + 1);

        if (dictT.containsKey(character) && 
            windowCounts.get(character).intValue() == dictT.get(character).intValue()) {
            formed++;
        }

        while (left <= right && formed == required) {
            character = s.charAt(left);

            if (ans[0] == -1 || right - left + 1 < ans[0]) {
                ans[0] = right - left + 1;
                ans[1] = left;
                ans[2] = right;
            }

            windowCounts.put(character, windowCounts.get(character) - 1);
            if (dictT.containsKey(character) && 
                windowCounts.get(character) < dictT.get(character)) {
                formed--;
            }

            left++;
        }

        right++;
    }

    return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
Enter fullscreen mode Exit fullscreen mode

Sliding Window Maximum

More Sliding Window Problems:

3. Fast & Slow Pointers Pattern

When to use: Detecting cycles in linked lists, finding middle elements, or problems involving circular arrays.

Time Complexity: O(n)
Space Complexity: O(1)

Key Problems & Companies:

Linked List Cycle

  • Companies: Amazon, Google, Microsoft, Facebook, Apple
  • Difficulty: Easy
  • Interview Frequency: Very High
  • LeetCode: 141. Linked List Cycle 
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    ListNode slow = head;
    ListNode fast = head.next;

    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return true;
}
Enter fullscreen mode Exit fullscreen mode

Middle of the Linked List

Linked List Cycle II

More Fast & Slow Pointers Problems:

4. Merge Intervals Pattern

When to use: When dealing with overlapping intervals, scheduling problems, or interval merging.

Time Complexity: O(n log n)
Space Complexity: O(n)

Key Problems & Companies:

Merge Intervals

  • Companies: Amazon, Google, Microsoft, Facebook, Apple, Bloomberg
  • Difficulty: Medium
  • Interview Frequency: Very High
  • LeetCode: 56. Merge Intervals 
public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> result = new ArrayList<>();
    int[] currentInterval = intervals[0];
    result.add(currentInterval);

    for (int[] interval : intervals) {
        int currentEnd = currentInterval[1];
        int nextBegin = interval[0];
        int nextEnd = interval[1];

        if (currentEnd >= nextBegin) {
            currentInterval[1] = Math.max(currentEnd, nextEnd);
        } else {
            currentInterval = interval;
            result.add(currentInterval);
        }
    }

    return result.toArray(new int[result.size()][]);
}
Enter fullscreen mode Exit fullscreen mode

Insert Interval

  • Companies: Google, Amazon, Facebook, Microsoft
  • Difficulty: Medium
  • LeetCode: 57. Insert Interval

Meeting Rooms

  • Companies: Google, Facebook, Amazon, Microsoft, Uber
  • Difficulty: Easy
  • LeetCode: 252. Meeting Rooms (Premium)

More Merge Intervals Problems:

5. Cyclic Sort Pattern

When to use: When dealing with arrays containing numbers in a given range (usually 1 to n).

Time Complexity: O(n)
Space Complexity: O(1)

Key Problems & Companies:

Missing Number

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Easy
  • LeetCode: 268. Missing Number 
public int missingNumber(int[] nums) {
    int i = 0;
    int n = nums.length;

    while (i < n) {
        if (nums[i] < n && nums[i] != nums[nums[i]]) {
            swap(nums, i, nums[i]);
        } else {
            i++;
        }
    }

    for (i = 0; i < n; i++) {
        if (nums[i] != i) {
            return i;
        }
    }

    return n;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
Enter fullscreen mode Exit fullscreen mode

Find All Numbers Disappeared in an Array

More Cyclic Sort Problems:

6. In-place Reversal of LinkedList

When to use: When you need to reverse a linked list or parts of it without using extra space.

Time Complexity: O(n)
Space Complexity: O(1)

Key Problems & Companies:

Reverse Linked List

  • Companies: Amazon, Google, Microsoft, Facebook, Apple, Netflix
  • Difficulty: Easy
  • Interview Frequency: Very High
  • LeetCode: 206. Reverse Linked List 
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }

    return prev;
}
Enter fullscreen mode Exit fullscreen mode

Reverse Nodes in k-Group

More LinkedList Reversal Problems:

7. Tree Breadth-First Search (BFS)

When to use: When you need to traverse tree level by level or find shortest path in trees.

Time Complexity: O(n)
Space Complexity: O(w) where w is maximum width

Key Problems & Companies:

Binary Tree Level Order Traversal 

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode currentNode = queue.poll();
            currentLevel.add(currentNode.val);

            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

        result.add(currentLevel);
    }

    return result;
}
Enter fullscreen mode Exit fullscreen mode

Binary Tree Zigzag Level Order Traversal

More Tree BFS Problems:

8. Tree Depth-First Search (DFS)

When to use: When you need to explore tree paths, find sums, or perform recursive tree operations.

Time Complexity: O(n)
Space Complexity: O(h) where h is height

Key Problems & Companies:

Path Sum

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Easy
  • LeetCode: 112. Path Sum 
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    }

    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
}
Enter fullscreen mode Exit fullscreen mode

Binary Tree Paths

More Tree DFS Problems:

9. Two Heaps Pattern

When to use: When you need to find medians, or divide elements into two parts.

Time Complexity: O(log n) for insertion, O(1) for median
Space Complexity: O(n)

Key Problems & Companies:

Find Median from Data Stream 

class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size() + 1) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

More Two Heaps Problems:

10. Subsets Pattern

When to use: When you need to generate all combinations, permutations, or subsets.

Time Complexity: O(2^n) for subsets, O(n!) for permutations
Space Complexity: O(n)

Key Problems & Companies:

Subsets

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Medium
  • LeetCode: 78. Subsets 
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> tempList, 
                      int[] nums, int start) {
    result.add(new ArrayList<>(tempList));

    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]);
        backtrack(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}
Enter fullscreen mode Exit fullscreen mode

Permutations

  • Companies: Amazon, Google, Microsoft, Facebook, Apple
  • Difficulty: Medium
  • LeetCode: 46. Permutations

More Subsets Problems:

11. Modified Binary Search

When to use: When dealing with sorted arrays with modifications or rotations.

Time Complexity: O(log n)
Space Complexity: O(1)

Key Problems & Companies:

Search in Rotated Sorted Array 

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}
Enter fullscreen mode Exit fullscreen mode

Find Minimum in Rotated Sorted Array

More Modified Binary Search Problems:

12. Bitwise XOR Pattern

When to use: When dealing with problems involving finding unique elements or bit manipulations.

Time Complexity: O(n)
Space Complexity: O(1)

Key Problems & Companies:

Single Number

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Easy
  • LeetCode: 136. Single Number 
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}
Enter fullscreen mode Exit fullscreen mode

More Bitwise XOR Problems:

13. Top K Elements

When to use: When you need to find the K largest/smallest elements or K most frequent elements.

Time Complexity: O(n log k)
Space Complexity: O(k)

Key Problems & Companies:

Kth Largest Element in an Array 

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }

    return heap.peek();
}
Enter fullscreen mode Exit fullscreen mode

Top K Frequent Elements

More Top K Problems:

14. K-way Merge

When to use: When you need to merge K sorted arrays or lists.

Time Complexity: O(n log k)
Space Complexity: O(k)

Key Problems & Companies:

Merge k Sorted Lists 

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

    for (ListNode list : lists) {
        if (list != null) {
            heap.offer(list);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        current.next = node;
        current = current.next;

        if (node.next != null) {
            heap.offer(node.next);
        }
    }

    return dummy.next;
}
Enter fullscreen mode Exit fullscreen mode

More K-way Merge Problems:

15. Dynamic Programming Patterns

When to use: When problems have optimal substructure and overlapping subproblems.

Time Complexity: Varies (usually O(n²) to O(n³))
Space Complexity: O(n) to O(n²)

Key DP Patterns:

1. Linear DP

Climbing Stairs

  • Companies: Amazon, Google, Microsoft, Facebook, Apple
  • Difficulty: Easy
  • LeetCode: 70. Climbing Stairs 
public int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1, prev1 = 2;

    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}
Enter fullscreen mode Exit fullscreen mode

House Robber

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Medium
  • LeetCode: 198. House Robber 
public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}
Enter fullscreen mode Exit fullscreen mode

2. 2D DP

Unique Paths

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Medium
  • LeetCode: 62. Unique Paths 
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}
Enter fullscreen mode Exit fullscreen mode

Longest Common Subsequence

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}
Enter fullscreen mode Exit fullscreen mode

3. Knapsack Pattern

0/1 Knapsack

  • Companies: Amazon, Google, Microsoft
  • Difficulty: Medium 
public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], 
                                  dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}
Enter fullscreen mode Exit fullscreen mode

Coin Change

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Medium
  • LeetCode: 322. Coin Change

More DP Problems:

16. Topological Sort

When to use: When dealing with directed acyclic graphs (DAG) and dependency resolution.

Time Complexity: O(V + E)
Space Complexity: O(V)

Key Problems & Companies:

Course Schedule 

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] indegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();

    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }

    for (int[] prerequisite : prerequisites) {
        adj.get(prerequisite[1]).add(prerequisite[0]);
        indegree[prerequisite[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;

        for (int neighbor : adj.get(course)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return count == numCourses;
}
Enter fullscreen mode Exit fullscreen mode

Course Schedule II

More Topological Sort Problems:

17. Graph Algorithms

When to use: When dealing with graph traversal, shortest paths, or connectivity problems.

Key Graph Patterns:

1. DFS/BFS Traversal

Number of Islands

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || 
        grid[i][j] == '0') {
        return;
    }

    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}
Enter fullscreen mode Exit fullscreen mode

Clone Graph

  • Companies: Google, Amazon, Facebook, Microsoft
  • Difficulty: Medium
  • LeetCode: 133. Clone Graph

2. Shortest Path

Word Ladder

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Hard
  • LeetCode: 127. Word Ladder

More Graph Problems:

18. Trie Pattern

When to use: When dealing with prefix matching, word search, or autocomplete features.

Time Complexity: O(m) where m is word length
Space Complexity: O(ALPHABET_SIZE * N * M)

Key Problems & Companies:

Implement Trie (Prefix Tree) 

class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26];
            isEndOfWord = false;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }
}
Enter fullscreen mode Exit fullscreen mode

Word Search II

  • Companies: Google, Amazon, Microsoft, Facebook
  • Difficulty: Hard
  • LeetCode: 212. Word Search II

More Trie Problems:

19. Union Find (Disjoint Set)

When to use: When dealing with connectivity, grouping, or cycle detection in undirected graphs.

Time Complexity: O(α(n)) amortized
Space Complexity: O(n)

Key Problems & Companies:

Number of Connected Components in an Undirected Graph 

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int components;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        components--;
        return true;
    }

    public int getComponents() {
        return components;
    }
}

public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);

    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);
    }

    return uf.getComponents();
}
Enter fullscreen mode Exit fullscreen mode

More Union Find Problems:

20. Backtracking Pattern

When to use: When you need to explore all possible solutions and backtrack when constraints are violated.

Time Complexity: Exponential (varies by problem)
Space Complexity: O(depth of recursion)

Key Problems & Companies:

Generate Parentheses 

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

private void backtrack(List<String> result, String current, 
                      int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }

    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }

    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}
Enter fullscreen mode Exit fullscreen mode

Word Search

  • Companies: Amazon, Google, Microsoft, Facebook
  • Difficulty: Medium
  • LeetCode: 79. Word Search 
public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, word, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
        board[i][j] != word.charAt(index)) {
        return false;
    }

    char temp = board[i][j];
    board[i][j] = '#'; // Mark as visited

    boolean found = dfs(board, word, i + 1, j, index + 1) ||
                   dfs(board, word, i - 1, j, index + 1) ||
                   dfs(board, word, i, j + 1, index + 1) ||
                   dfs(board, word, i, j - 1, index + 1);

    board[i][j] = temp; // Backtrack
    return found;
}
Enter fullscreen mode Exit fullscreen mode

N-Queens

  • Companies: Google, Amazon, Microsoft, Facebook
  • Difficulty: Hard
  • LeetCode: 51. N-Queens

More Backtracking Problems:

Interview Preparation Strategy

1. Study Pattern by Pattern

  • Master one pattern completely before moving to the next
  • Practice 5-10 problems per pattern
  • Focus on understanding the underlying technique

2. Company-Specific Preparation

  • Google: Focus on hard algorithmic problems, system design
  • Amazon: Leadership principles + coding (medium difficulty)
  • Microsoft: Balanced approach, good for beginners
  • Facebook/Meta: Product sense + challenging coding problems
  • Apple: Focus on fundamentals and clean code

3. Time Management

  • Easy problems: 10-15 minutes
  • Medium problems: 20-30 minutes
  • Hard problems: 35-45 minutes

4. Common Mistakes to Avoid

  • Not clarifying requirements
  • Jumping into coding without planning
  • Not testing with edge cases
  • Poor time management
  • Not communicating thought process

5. Mock Interview Practice

  • Use platforms like Pramp, InterviewBit, or LeetCode Mock
  • Practice explaining your solution clearly
  • Get comfortable with live coding

Conclusion

Mastering these 20 patterns will give you a strong foundation for tackling most coding interview problems. Remember:

  1. Pattern Recognition is key - identify which pattern applies
  2. Practice Consistently - solve problems daily
  3. Understand Trade-offs - know time/space complexities
  4. Mock Interviews - practice under pressure
  5. System Design - don't neglect this for senior roles

The key to success is consistent practice and understanding the underlying patterns rather than memorizing solutions. Focus on building problem-solving intuition that will help you tackle new problems during interviews.

Good luck with your interview preparation! 🚀

Top comments (0)