Must-Know Classic Problems

​

The Essential Seven

​

1. Two Sum - The Hash Table Foundation

def twoSum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

• Pair sum problems (3Sum, 4Sum, Two Sum II)
• Anagram detection
• Frequency counting
• Duplicate detection
• Caching and memoization

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        elif total < target:
            left += 1
        else:
            right -= 1

• “What if the array is sorted?” → Two pointers
• “What if we need all pairs?” → Handle duplicates carefully
• “What if input is too large for memory?” → External merge sort

​

2. Valid Parentheses - The Stack Pattern

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)
    
    return not stack

• Matching/balancing problems (parentheses, tags)
• Expression evaluation (calculators, parsers)
• Backtracking and undo operations
• Monotonic stack problems (next greater element)
• DFS traversal (iterative)

def minRemoveToMakeValid(s):
    to_remove = set()
    stack = []
    
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                to_remove.add(i)
    
    to_remove.update(stack)
    return ''.join(char for i, char in enumerate(s) 
                  if i not in to_remove)

• “What if we need to count minimum insertions?” → Counter approach
• “Can you do it with O(1) space?” → Counter for simple cases
• “What about nested tag validation?” → Stack with state

​

3. Merge Intervals - The Sorting + Greedy Pattern

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged

• Scheduling conflicts (meeting rooms, calendar)
• Range queries and updates
• Resource allocation
• Time-based analytics
• Interval tree problems

def insert(intervals, newInterval):
    result = []
    i = 0
    
    # Add all intervals before newInterval
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
    
    # Add remaining intervals
    result.extend(intervals[i:])
    return result

• “What if intervals aren’t sorted?” → Must sort first
• “How to handle infinite streams?” → Sweep line with priority queue
• “Optimize for many queries?” → Interval tree

​

4. LRU Cache - The Design Pattern

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

• Combining data structures (hash table + linked list)
• O(1) operation design
• System design principles
• Cache invalidation strategies
• Real-world data structure implementation

• “How to handle concurrent access?” → Locks or lock-free structures
• “What if cache is distributed?” → Consistent hashing
• “Memory vs performance tradeoffs?” → Discuss eviction policies

​

5. Best Time to Buy/Sell Stock - The DP Foundation

def maxProfit(prices: List[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)
    
    return max_profit

• State-based dynamic programming
• Tracking optimal solutions incrementally
• Space optimization (reducing from O(n) to O(1))
• Maximum subarray variants
• Financial modeling patterns

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

• “What if we can do k transactions?” → Generalized DP
• “With transaction fees?” → Subtract fee in profit calculation
• “Prove this is optimal” → Explain greedy property

​

6. Merge k Sorted Lists - The Heap Mastery

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    min_heap = []
    
    # Initialize heap with first node from each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(min_heap, (node.val, i, node))
    
    dummy = ListNode(0)
    current = dummy
    
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
    
    return dummy.next

• Top-K problems
• Stream processing (finding median, top elements)
• Priority scheduling
• Merge operations
• External sorting

def findKthLargest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap[0]

• “What if lists are very long?” → External merge sort
• “Divide and conquer alternative?” → Merge pairs recursively
• “How to handle duplicates?” → No change needed

​

7. Clone Graph - The Graph Traversal Template

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None
    
    cloned = {}
    
    def dfs(node):
        if node in cloned:
            return cloned[node]
        
        clone = Node(node.val)
        cloned[node] = clone
        
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

• Social network queries
• Dependency resolution
• Path finding
• Cycle detection
• Connected components
• Topological sorting

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    # 0: unvisited, 1: visiting, 2: visited
    state = [0] * numCourses
    
    def hasCycle(course):
        if state[course] == 1:
            return True
        if state[course] == 2:
            return False
        
        state[course] = 1
        for prereq in graph[course]:
            if hasCycle(prereq):
                return True
        state[course] = 2
        return False
    
    return not any(hasCycle(i) for i in range(numCourses))

• “BFS vs DFS - when to use which?” → BFS for shortest path, DFS for all paths
• “How to detect cycles?” → Three-state coloring or visited set with recursion stack
• “Optimize for sparse vs dense graphs?” → Adjacency list vs matrix

​

Pattern Recognition Guide

​

Mastery Checklist

​

Study Strategy

​

Why These Seven?

1. High Frequency: Appear in 62-77% of interviews at top companies
2. Fundamental Patterns: Each teaches a pattern that appears in 50+ other problems
3. Building Blocks: More complex problems combine these patterns
4. Real-World Relevance: These patterns appear daily in production code
5. Interview Signals: Success on these indicates strong foundational knowledge

​

Next Steps