⚡

Interview Patterns

Two pointers, sliding window, fast/slow, merge intervals. Pattern recognition wins interviews.

Interview Patterns

Recognizing the right pattern is more important than memorizing solutions.

1. Two Pointers

When: Sorted array, find pair with target sum, palindrome check, container with most water.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:   return [left, right]
        elif s < target:  left += 1
        else:             right -= 1
    return []

Time: O(n), Space: O(1).

2. Sliding Window

When: Subarray/substring with constraint (max sum, longest with k distinct chars, etc.)

def longest_substring_k_distinct(s, k):
    freq = {}
    left = best = 0
    for right, c in enumerate(s):
        freq[c] = freq.get(c, 0) + 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

3. Fast & Slow Pointers

When: Cycle detection, find middle of linked list, nth from end.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

4. Merge Intervals

When: Overlapping intervals, meeting rooms, merge calendar events.

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

5. Binary Search on Answer

When: "Find minimum X such that condition holds" — answer space is monotonic (False...True or True...False).

def min_days_to_bloom(bloomDay, m, k):
    def can_bloom(day):
        blooms = flowers = 0
        for d in bloomDay:
            if d <= day:
                flowers += 1
                if flowers == k:
                    blooms += 1; flowers = 0
            else:
                flowers = 0
        return blooms >= m

    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_bloom(mid): hi = mid
        else:              lo = mid + 1
    return lo

6. Monotonic Stack

When: Next greater element, largest rectangle in histogram, daily temperatures.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # indices of elements waiting for their "next greater"
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n   # n is the answer for stack[-1]
        stack.append(i)
    return result

7. Greedy Algorithms

Make the locally optimal choice at each step — works when problems have greedy choice property + optimal substructure.

# Activity selection: maximize non-overlapping intervals
def max_activities(intervals):
    # Sort by end time — earliest finish first
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Other greedy problems: fractional knapsack, Huffman coding, minimum spanning tree (Prim's/Kruskal's), jump game.

8. Backtracking

When: Generate all solutions, combinations, permutations, N-Queens, Sudoku.

def backtrack(candidate, result):
    if is_complete(candidate):
        result.append(candidate[:])
        return
    for choice in generate_choices(candidate):
        if is_valid(choice):
            candidate.append(choice)        # make move
            backtrack(candidate, result)
            candidate.pop()                 # undo (backtrack)

9. Divide and Conquer

Break into sub-problems, solve recursively, combine. Classic examples: merge sort, quick sort, binary search, closest pair of points.

Iterative vs Recursive

| | Recursive | Iterative | |--|--|--| | Code clarity | Often cleaner | More boilerplate | | Stack overflow | Risk on deep/skewed input | Explicit stack, safe | | Preferred for | Trees (natural structure) | Large graphs, skewed trees |

Edge Cases Checklist

Before submitting any solution, verify these:

  • Empty input (null, empty string, empty array)
  • Single element
  • All same elements
  • Already sorted / reverse sorted
  • Cycles in graphs or linked lists
  • Disconnected graphs
  • Skewed trees (worst case for BST ops)
  • Integer overflow (less relevant in Python)

Complexity Quick Reference

| Complexity | Name | Example | |-----------|------|---------| | O(1) | Constant | Hash map lookup | | O(log n) | Logarithmic | Binary search, heap ops | | O(n) | Linear | Single pass | | O(n log n)| Linearithmic | Sorting, divide & conquer | | O(n²) | Quadratic | Nested loops | | O(2ⁿ) | Exponential | Recursion without memo | | O(n!) | Factorial | Permutations |

Pattern Recognition Cheat Sheet

| Signal in problem | Try | |-------------------|-----| | Sorted array, pair sum | Two pointers | | Subarray/substring constraint | Sliding window | | Linked list cycle | Fast & slow | | Overlapping intervals | Sort + merge | | Min/max feasibility | Binary search on answer | | Next greater/smaller | Monotonic stack | | Make locally optimal choices | Greedy | | All combinations/paths | DFS + backtracking | | Dependencies/ordering | Topological sort | | Shortest path (unweighted) | BFS | | Shortest path (weighted) | Dijkstra | | Connected components / cycles | Union-Find | | Repeated sub-problems | DP (top-down or bottom-up) |