Comprehensive Problem Patterns for Interview Preparation

1. Arrays and Strings

Common Patterns:

Two Pointers

• Usage: Efficiently process elements in arrays or strings by using two indices that move towards each other or at different speeds.
• Key Examples:
  • Removing Duplicates: Remove duplicates in-place from a sorted array.
  • Palindrome Checking: Determine if a string is a palindrome considering only alphanumeric characters.
  • Container With Most Water: Find two lines that together with the x-axis form a container that holds the most water.

Sliding Window

• Usage: Find subarrays or substrings that satisfy certain conditions by moving a window over the data.
• Key Examples:
  • Longest Substring Without Repeating Characters: Find the length of the longest substring without repeating characters.
  • Minimum Window Substring: Find the smallest substring containing all characters of another string.
  • Maximum Sum Subarray of Size K: Find the subarray with the maximum sum of length k.

Hash Tables / Dictionaries

• Usage: Use hash maps to store frequencies or mappings for quick lookups.
• Key Examples:
  • Two Sum Problem: Find indices of two numbers that add up to a specific target.
  • Group Anagrams: Group strings that are anagrams of each other.
  • Subarray Sum Equals K: Count the number of subarrays that sum to a given value.

Prefix Sum

• Usage: Precompute cumulative sums or other operations to answer range queries efficiently.
• Key Examples:
  • Range Sum Query: Calculate the sum of elements between two indices efficiently.
  • Subarray Sum Divisible by K: Find the number of subarrays whose sums are divisible by k.
  • Product of Array Except Self: Calculate the product of array elements except for the current index without using division.

Sorting

• Usage: Sort the array to simplify the problem or enable the use of two-pointer techniques.
• Key Examples:
  • Merge Intervals: Merge overlapping intervals after sorting them.
  • Meeting Rooms: Determine if a person could attend all meetings based on sorted intervals.
  • Largest Number: Arrange numbers to form the largest possible number.

2. Linked Lists

Common Patterns:

Fast and Slow Pointers

• Usage: Detect cycles, find the middle of the list, or detect other properties by moving pointers at different speeds.
• Key Examples:
  • Cycle Detection: Determine if a linked list has a cycle.
  • Find Middle Node: Find the middle node of a linked list.
  • Palindrome Linked List: Check if a linked list is a palindrome.

Reversal Techniques

• Usage: Reverse all or part of a linked list.
• Key Examples:
  • Reverse Entire List: Reverse a singly linked list.
  • Reverse Nodes in K-Group: Reverse nodes in groups of k.
  • Swap Nodes in Pairs: Swap every two adjacent nodes.

Dummy Nodes

• Usage: Simplify edge cases when adding or removing nodes by using a dummy head or tail node.
• Key Examples:
  • Merge Two Sorted Lists: Merge two sorted linked lists into one sorted list.
  • Remove Nth Node From End: Remove the nth node from the end of the list.
  • Remove Elements: Remove all elements from a linked list of a specific value.

Pointers Manipulation

• Usage: Adjust pointers to reorder or rearrange the list without creating new nodes.
• Key Examples:
  • Odd Even Linked List: Group all odd nodes together followed by the even nodes.
  • Partition List: Partition a linked list around a value x.
  • Rotate List: Rotate the list to the right by k places.

3. Trees and Binary Trees

Common Patterns:

Depth-First Search (DFS)

• Usage: Traverse trees to perform operations like searching, counting, or modifying nodes.
• Key Examples:
  • Max Depth of Binary Tree: Find the maximum depth of a binary tree.
  • Path Sum: Determine if the tree has a root-to-leaf path with a given sum.
  • Binary Tree Paths: Return all root-to-leaf paths.

Breadth-First Search (BFS)

• Usage: Level order traversal or finding the shortest path in unweighted trees.
• Key Examples:
  • Level Order Traversal: Return the values of the nodes in each level.
  • Minimum Depth of Binary Tree: Find the minimum depth from root to the nearest leaf.
  • Binary Tree Right Side View: Get the values of the nodes visible from the right side.

Binary Search Tree (BST) Properties

• Usage: Utilize the ordered nature of BSTs to perform efficient searches and insertions.
• Key Examples:
  • Validate BST: Check if a binary tree is a valid BST.
  • Lowest Common Ancestor: Find the lowest common ancestor of two nodes in a BST.
  • Kth Smallest Element: Find the kth smallest element in a BST.

Tree Serialization and Deserialization

• Usage: Convert trees to a string format and back, useful for storing or transmitting tree structures.
• Key Examples:
  • Serialize and Deserialize Binary Tree: Implement methods to serialize a binary tree to a string and deserialize it back.
  • Serialize and Deserialize BST: Optimize serialization for BSTs using inorder traversal.

4. Graphs

Common Patterns:

DFS and BFS Traversal

• Usage: Explore all nodes in connected components or perform searches.
• Key Examples:
  • Number of Islands: Count the number of islands in a grid using DFS or BFS.
  • Clone Graph: Create a deep copy of a graph.
  • Word Ladder: Find the shortest transformation sequence from one word to another.

Union-Find (Disjoint Set)

• Usage: Keep track of elements partitioned into disjoint subsets; useful for cycle detection and connectivity.
• Key Examples:
  • Connected Components in Undirected Graph: Find the number of connected components.
  • Accounts Merge: Merge accounts with common email addresses.
  • Redundant Connection: Detect and remove an extra edge to make a tree.

Topological Sort

• Usage: Order vertices in a directed acyclic graph (DAG) based on dependencies.
• Key Examples:
  • Course Schedule: Determine if you can finish all courses given prerequisites.
  • Alien Dictionary: Derive the order of letters in an alien language.
  • Task Scheduling: Decide if a sequence of tasks can be completed given dependencies.

Dijkstra's Algorithm

• Usage: Find the shortest path in a graph with non-negative edge weights.
• Key Examples:
  • Network Delay Time: Calculate how long it will take for all nodes to receive a signal.
  • Cheapest Flights Within K Stops: Find the cheapest price for a flight with up to k stops.
  • Path with Maximum Probability: Find the path with the highest probability between two nodes.

5. Dynamic Programming (DP)

Common Patterns:

Memoization and Tabulation

• Usage: Store intermediate results to avoid redundant computations.
• Key Examples:
  • Climbing Stairs: Count the number of ways to reach the top.
  • Fibonacci Sequence: Compute the nth Fibonacci number efficiently.
  • Unique Paths: Find the number of ways to reach the bottom-right corner of a grid.

State Definition and Transition

• Usage: Define DP states and transitions to model the problem.
• Key Examples:
  • Edit Distance: Compute the minimum number of operations to convert one word to another.
  • Longest Common Subsequence: Find the length of the longest subsequence common to two sequences.
  • Coin Change: Determine the fewest coins needed to make a certain amount.

DP on Strings

• Usage: Solve problems related to subsequences and substrings.
• Key Examples:
  • Longest Palindromic Substring: Find the longest palindromic substring in a string.
  • Distinct Subsequences: Count the number of distinct subsequences equal to a target string.
  • Regular Expression Matching: Implement regular expression matching with support for '.' and '*'.

DP on Trees

• Usage: Apply DP techniques to tree structures where subtrees can be solved independently.
• Key Examples:
  • House Robber III: Maximize the amount of money by robbing non-adjacent houses in a tree.
  • Binary Tree Maximum Path Sum: Find the path with the maximum sum in a binary tree.

Knapsack Problems

• Usage: Select items to maximize value under capacity constraints.
• Key Examples:
  • Partition Equal Subset Sum: Determine if an array can be partitioned into two subsets with equal sums.
  • Target Sum: Find the number of ways to assign symbols to make the sum of integers equal to a target.
  • Combination Sum: Find all unique combinations where candidate numbers sum to a target.

6. Backtracking

Common Patterns:

Permutation and Combination Generation

• Usage: Generate all possible permutations or combinations.
• Key Examples:
  • Permutations: Generate all possible permutations of a list.
  • Combinations: Generate all possible combinations of k numbers out of n.
  • Subsets: Find all possible subsets of a set.

Constraint Satisfaction

• Usage: Solve problems where you need to fill in values under certain constraints.
• Key Examples:
  • N-Queens Problem: Place n queens on an n×n chessboard without attacking each other.
  • Sudoku Solver: Fill a 9×9 grid so that each row, column, and 3×3 box contains the digits 1 to 9.
  • Word Search: Determine if a word exists in a grid by moving horizontally or vertically.

Recursive Exploration

• Usage: Explore all potential solutions recursively.
• Key Examples:
  • Combination Sum: Find all unique combinations where candidate numbers sum to a target.
  • Palindrome Partitioning: Partition a string such that every substring is a palindrome.
  • Letter Combinations of a Phone Number: Return all letter combinations that the number could represent.

7. Greedy Algorithms

Common Patterns:

Activity Selection

• Usage: Select maximum number of activities without conflicts.
• Key Examples:
  • Job Sequencing: Schedule jobs to maximize profit given deadlines.
  • Interval Scheduling: Find the maximum number of non-overlapping intervals.
  • Meeting Rooms II: Find the minimum number of conference rooms required.

Optimal Substructure

• Usage: Make the locally optimal choice at each step, which leads to a globally optimal solution.
• Key Examples:
  • Jump Game II: Find the minimum number of jumps to reach the end of an array.
  • Candy Distribution: Distribute candies to children according to their ratings with minimal total candies.
  • Gas Station: Determine the starting gas station's index to complete the circuit.

8. Stacks and Queues

Common Patterns:

Monotonic Stack

• Usage: Solve problems related to the next greater or smaller element.
• Key Examples:
  • Largest Rectangle in Histogram: Find the largest rectangle area in a histogram.
  • Daily Temperatures: For each day, find out how many days to wait until a warmer temperature.
  • Next Greater Element: Find the next greater element for each element in an array.

Parentheses Matching

• Usage: Validate or compute expressions with nested parentheses.
• Key Examples:
  • Valid Parentheses: Check if the input string has valid parentheses.
  • Longest Valid Parentheses: Find the length of the longest valid (well-formed) parentheses substring.
  • Basic Calculator: Implement a calculator to evaluate simple expression strings.

Implement Data Structures

• Usage: Build queues using stacks or vice versa.
• Key Examples:
  • Implement Queue using Stacks: Use two stacks to implement a queue.
  • Implement Stack using Queues: Use two queues to implement a stack.
  • Min Stack: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

9. Heaps and Priority Queues

Common Patterns:

Top K Elements

• Usage: Find the largest or smallest k elements in a collection.
• Key Examples:
  • Kth Largest Element in an Array: Find the kth largest element in an unsorted array.
  • Top K Frequent Elements: Find the k most frequent elements in an array.
  • K Closest Points to Origin: Find the k closest points to the origin.

Merge K Sorted Lists/Arrays

• Usage: Efficiently merge multiple sorted lists or arrays.
• Key Examples:
  • Merge K Sorted Lists: Merge k sorted linked lists into one sorted list.
  • Find Median from Data Stream: Continuously find the median as new data comes in.
  • Smallest Range Covering Elements from K Lists: Find the smallest range that includes at least one number from each of the k lists.

Scheduling Problems

• Usage: Assign tasks based on priority or other criteria.
• Key Examples:
  • Task Scheduler: Schedule tasks with cooldown periods.
  • Reorganize String: Rearrange a string so that no two adjacent characters are the same.
  • Meeting Rooms II: Find the minimum number of conference rooms required.

10. Binary Search

Common Patterns:

Search in Sorted Arrays

• Usage: Efficiently find elements in sorted arrays or matrices.
• Key Examples:
  • Binary Search: Implement binary search to find a target value.
  • Search Insert Position: Find the index where a target should be inserted in a sorted array.
  • Search in Rotated Sorted Array: Find a target value in a rotated sorted array.

Modified Binary Search

• Usage: Apply binary search in more complex scenarios.
• Key Examples:
  • Find Minimum in Rotated Sorted Array: Find the minimum element in a rotated sorted array.
  • Peak Index in a Mountain Array: Find the peak element in a mountain array.
  • Median of Two Sorted Arrays: Find the median of two sorted arrays.

Answer Range Problems

• Usage: Use binary search to find an optimal value in a range that satisfies certain conditions.
• Key Examples:
  • Koko Eating Bananas: Find the minimum eating speed to finish bananas within h hours.
  • Capacity to Ship Packages Within D Days: Find the least weight capacity to ship all packages within d days.
  • Split Array Largest Sum: Split the array into m parts minimizing the largest sum among them.

11. Trie (Prefix Tree)

Common Patterns:

Prefix Search

• Usage: Store words for efficient prefix searches.
• Key Examples:
  • Implement Trie: Implement insert, search, and startsWith functions for a trie.
  • Word Search II: Find all words in a grid that are in a dictionary.
  • Replace Words: Replace words in a sentence with their root forms from a dictionary.

Autocomplete Systems

• Usage: Suggest words based on input prefixes.
• Key Examples:
  • Design Search Autocomplete System: Implement an autocomplete system that suggests the most frequent sentences.
  • Search Suggestions System: Return a list of suggested products based on a search word.

12. Bit Manipulation

Common Patterns:

Bitwise Operations

• Usage: Perform operations using bits for efficiency and to solve specific problems.
• Key Examples:
  • Single Number: Find the element that appears only once when every other element appears twice.
  • Counting Bits: Count the number of set bits for every number up to n.
  • Reverse Bits: Reverse bits of a given 32 bits unsigned integer.

Masking Techniques

• Usage: Use bit masks to represent subsets or combinations.
• Key Examples:
  • Subsets: Generate all possible subsets of a set using bit manipulation.
  • Total Hamming Distance: Compute the total Hamming distance between all pairs of integers.
  • Maximum XOR of Two Numbers in an Array: Find the maximum result of nums[i] XOR nums[j].

13. Math and Number Theory

Common Patterns:

Prime Numbers and Factors

• Usage: Work with prime numbers and factorization.
• Key Examples:
  • Count Primes: Count the number of prime numbers less than a non-negative number n.
  • Ugly Number: Determine if a number is an ugly number (only prime factors of 2, 3, 5).
  • Perfect Squares: Check if a number is a perfect square.

Modular Arithmetic

• Usage: Handle large numbers with modulo operations.
• Key Examples:
  • Pow(x, n): Implement pow(x, n), calculating x raised to the power n.
  • Multiply Strings: Multiply two non-negative integers represented as strings.
  • Super Pow: Calculate (a^b) mod 1337 where b is a large integer given as an array.

14. Design Problems

Common Patterns:

LRU Cache Implementation

• Usage: Implement caching mechanisms with specific constraints.
• Key Examples:
  • LRU Cache: Design a data structure that follows the constraints of a Least Recently Used cache.
  • LFU Cache: Design a data structure that follows the constraints of a Least Frequently Used cache.

Concurrency Control

• Usage: Manage multi-threading in concurrent environments.
• Key Examples:
  • Print in Order: Ensure threads print in a specific order.
  • Dining Philosophers: Implement a solution to the dining philosophers problem.
  • Design Bounded Blocking Queue: Implement a thread-safe bounded blocking queue.

15. Recursion and Divide & Conquer

Common Patterns:

Recursive Tree Traversal

• Usage: Use recursion to traverse and solve problems on trees.
• Key Examples:
  • Symmetric Tree: Check if a tree is symmetric around its center.
  • Maximum Depth of Binary Tree: Find the maximum depth of a binary tree.
  • Flatten Binary Tree to Linked List: Flatten a binary tree to a linked list in-place.

Divide and Conquer

• Usage: Break problems into subproblems, solve them independently, and combine results.
• Key Examples:
  • Merge Sort: Sort an array using the merge sort algorithm.
  • Quick Sort: Sort an array using the quick sort algorithm.
  • Kth Largest Element in an Array: Find the kth largest element using quickselect.

16. Hashing

Common Patterns:

Frequency Counting

• Usage: Count the frequency of elements efficiently.
• Key Examples:
  • Top K Frequent Words: Return the k most frequent words from a list.
  • Majority Element: Find the element that appears more than ⌊ n/2 ⌋ times.
  • Longest Consecutive Sequence: Find the length of the longest consecutive elements sequence.

Hash Set for Uniqueness

• Usage: Ensure elements are unique or detect duplicates.
• Key Examples:
  • Contains Duplicate: Determine if the array contains any duplicates.
  • Happy Number: Determine if a number is a happy number using seen sums.
  • Longest Substring Without Repeating Characters: Find the length of the longest substring without repeating characters.

17. Sliding Window

Common Patterns:

Fixed Size Window

• Usage: Move a window over data of a fixed size to solve problems.
• Key Examples:
  • Maximum Average Subarray: Find the contiguous subarray of given length that has the maximum average.
  • Maximum Sum Subarray of Size K: Find the maximum sum of any contiguous subarray of size k.
  • Grumpy Bookstore Owner: Maximize the number of customers that can be satisfied.

Variable Size Window

• Usage: Adjust the window size dynamically based on conditions.
• Key Examples:
  • Minimum Window Substring: Find the minimum window in a string which will contain all the characters of another string.
  • Longest Substring with At Most K Distinct Characters: Find the length of the longest substring that contains at most k distinct characters.
  • Substring with Concatenation of All Words: Find all starting indices of substring(s) in a string that is a concatenation of each word in a list exactly once.

18. String Manipulation

Common Patterns:

Two Pointer Technique

• Usage: Process strings from both ends or compare characters in a string.
• Key Examples:
  • Valid Palindrome: Determine if a string is a palindrome.
  • Reverse Vowels of a String: Reverse only the vowels in a string.
  • Longest Palindromic Substring: Find the longest palindromic substring in a string.

String Parsing

• Usage: Parse and evaluate strings, often involving nested structures.
• Key Examples:
  • Basic Calculator: Implement a calculator to evaluate simple expression strings.
  • Decode String: Decode a string encoded with a certain pattern (e.g., "3[a2[c]]").
  • Simplify Path: Simplify a given Unix-style file path.

Pattern Matching

• Usage: Match patterns using algorithms like KMP or regular expressions.
• Key Examples:
  • Implement strStr(): Find the index of the first occurrence of a substring.
  • Wildcard Matching: Implement wildcard pattern matching with support for '?' and '*'.
  • Regular Expression Matching: Implement regular expression matching with support for '.' and '*'.

19. Geometry and Coordinate Problems

Common Patterns:

Sweep Line Algorithm

• Usage: Process points or intervals in a sorted order to solve problems efficiently.
• Key Examples:
  • Meeting Rooms II: Find the minimum number of conference rooms required.
  • The Skyline Problem: Compute the skyline formed by a collection of rectangular buildings.
  • Merge Intervals: Merge overlapping intervals.

Coordinate Transformation

• Usage: Convert between coordinate systems or rotate matrices.
• Key Examples:
  • Rotate Image: Rotate a 2D matrix by 90 degrees.
  • Max Points on a Line: Find the maximum number of points that lie on the same straight line.
  • Image Overlap: Find the largest possible overlap between two binary images.

20. Combinatorics and Probability

Common Patterns:

Counting Techniques

• Usage: Calculate the number of ways to arrange or select items.
• Key Examples:
  • Unique Paths: Find the number of unique paths in a grid from the top-left to the bottom-right.
  • Letter Tile Possibilities: Count the number of possible sequences of letters.
  • Count Vowel Strings in Lexicographical Order: Count the number of strings that consist of vowels and are sorted.

Probability Calculations

• Usage: Compute likelihoods or simulate random events.
• Key Examples:
  • Random Pick with Weight: Randomly pick an index based on weight.
  • Implement Rand10() Using Rand7(): Use one random number generator to implement another.
  • Random Point in Non-overlapping Rectangles: Randomly pick a point from given non-overlapping rectangles.

Preparation Tips:

• Understand Fundamental Concepts: Master the basics of data structures and algorithms.
• Recognize Patterns: Practice problems in each category to identify patterns quickly.
• Optimize Solutions: Focus on improving time and space complexity.
• Practice Coding: Write clean, readable code with proper syntax.
• Edge Cases: Think about and test for edge cases in your solutions.
• Explain Your Thinking: Be prepared to discuss your approach and reasoning during interviews.

By studying these patterns and practicing the associated types of problems, you'll enhance your problem-solving skills and be well-prepared for your interviews. Good luck with your preparation!