Skip to content
System Design

Technical Interview Master Guide

This guide provides a structured approach to preparing for technical interviews, focusing on core concepts, common patterns, and targeted practice.

1. Array & Search Patterns

This section covers patterns that rely on the linear, sequential nature of arrays and strings. They are fundamental for optimizing solutions that would otherwise require brute-force nested loops.

1.1. Two Pointers

The Two Pointers pattern uses two pointers to iterate over an array or string, often from opposite ends or at different speeds, to find a pair of elements or a sub-array that satisfies a certain condition.

Core Concept

  • Goal: Reduce nested loops (e.g., from O(n^2)) to a single pass (O(n)).
  • Mechanism: Two pointers (left, right or slow, fast) traverse the data structure, comparing elements and moving based on specific conditions.

When to Use (Signals)

  • The input is a sorted or sequential data structure (array, string, linked list).
  • You need to find a pair, sub-array, or palindrome that meets a condition.
  • You need to compare an element at one index with another.
  • You are making in-place swaps or partitioning an array.

Common Variations

  • Opposite Ends: Pointers start at the beginning and end, moving towards each other (e.g., Valid Palindrome, 2 Sum Sorted).
  • Slow & Fast: Pointers start at the same position but move at different speeds (e.g., Linked List Cycle Detection).
  • Boundary & Searcher: One pointer defines a boundary or partition, while the other searches (e.g., Remove Duplicates).

Practice Problems

1.2. Sliding Window

An extension of the Two Pointers pattern. It uses two pointers (left, right) to define a “window” (a sub-array or sub-string). The window expands by moving the right pointer and contracts by moving the left pointer to find an optimal range that satisfies a condition.

Core Concept

  • Goal: Find the maximum, minimum, or optimal sub-range in an array that satisfies a given condition.
  • Mechanism: The right pointer expands the window. Once the window’s state meets a condition, it’s processed. The left pointer then contracts the window until the condition is no longer met.

General Steps

  1. Initialize: Set up window bounds (left=0, right=0), a data structure to track the window’s state (e.g., a hash map, set), and a variable for the return value.
  2. Expand: Iterate with the right pointer, adding the new element to the window and updating its state.
  3. Check & Process: Once the window meets the problem’s condition, process it (e.g., update the max/min length).
  4. Contract: While the condition is met, move the left pointer inward, removing the element from the window’s state, until the condition is no longer satisfied.
  5. Repeat: Continue until the right pointer has traversed the entire array.

Pseudocode Template

def sliding_window_template(arr):
    left = 0
    # Initialize state tracker (e.g., hash_map, count)
    # Initialize result variable (e.g., max_len = 0)


    for right in range(len(arr)):
        # 1. Expand: Add arr[right] to the window state


        # 2. Contract: While window is invalid or meets contraction condition
        while condition_to_contract(window_state):
            # Update result if necessary
            # Remove arr[left] from window state
            left += 1


        # Update result based on the valid window
    return result

Practice Problems

A powerful algorithm for finding an element in a sorted array by repeatedly dividing the search space in half.

Core Concept

  • Goal: Reduce search time from O(n) to O(log n).
  • Mechanism: Compare the target value with the middle element of the search space. If they are not equal, eliminate the half in which the target cannot lie and continue searching in the remaining half.

When to Use (Signals)

  • The input array is sorted.
  • You need to find a target, or the first/last occurrence of a target.
  • The problem can be modeled as a search for a value where a condition function f(x) transitions from False to True. (e.g., f(x) = "can we ship all packages with capacity x?"). This is known as “Binary Search on the Answer.”

Template Variations

  1. Find Target: Standard binary search.
  2. Find Lower Bound: Find the first occurrence of a target or the first element greater than or equal to the target.
  3. Find Upper Bound: Find the last occurrence of a target or the first element strictly greater than the target.

Universal Binary Search Template

This template is powerful for finding boundaries.

def binary_search_template(arr, target):
    left, right = 0, len(arr) - 1
    ans = -1 # Or some other default
    while left <= right:
        mid = left + (right - left) // 2
        if condition(arr[mid], target):
            # Found a potential answer, try to find a better one
            ans = mid
            right = mid - 1 # Or left = mid + 1, depending on the problem
        else:
            # Condition not met, discard this half
            left = mid + 1 # Or right = mid - 1
    return ans

Practice Problems

2. Graph Patterns

Graphs are versatile data structures used to model networks and relationships. Problems typically involve traversing the graph, finding paths, or analyzing its structure.

2.1. Graph Representation

Choosing the right representation is the first step.

  • Edge List: A list of [u, v] pairs. Good for input, but usually needs to be converted. Use Union-Find directly on it for connectivity problems.
  • Adjacency Matrix: A V x V matrix where matrix[i][j] = 1 if an edge exists.
    • Pros: Fast edge lookup (O(1)).
    • Cons: High space complexity (O(V^2)). Inefficient for sparse graphs.
  • Adjacency List: A map or array where each vertex u maps to a list of its neighbors v.
    • Pros: Space efficient for sparse graphs (O(V+E)).
    • Cons: Slower edge lookup (O(degree(u))).
    • This is the most common and useful representation.

2.2. Graph Traversal

Breadth-First Search (BFS)

Explores the graph layer by layer. It’s ideal for finding the shortest path in an unweighted graph.

  • Mechanism: Uses a queue.
  • Steps:
    1. Add the starting node to the queue and a visited set.
    2. While the queue is not empty: a. Dequeue a node. b. Process it. c. For each of its unvisited neighbors, add them to the queue and the visited set.

Depth-First Search (DFS)

Explores as far as possible down one branch before backtracking. It’s useful for pathfinding, cycle detection, and topological sorting.

  • Mechanism: Uses recursion (call stack) or an explicit stack.
  • Steps (Recursive):
    1. Mark the current node as visited.
    2. Process it.
    3. For each unvisited neighbor, recursively call DFS on it.

Grid Traversal Checklist

Many graph problems are disguised as grids.

  1. Traversal: Use nested loops to iterate over (row, col).
  2. Visited Set: Use a set of (row, col) tuples or modify the grid in-place to avoid infinite loops.
  3. Directions Array: Define directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] for clean neighbor traversal.
  4. Boundary Check: Create a helper is_in_bounds(row, col) to ensure moves are valid.

Traversal Practice Problems

2.3. Union-Find (Disjoint Set Union)

A data structure that tracks a partition of elements into a number of disjoint (non-overlapping) sets.

  • Core Operations:
    • find(i): Determines which subset an element i is in. Returns the “representative” or “parent” of that set.
    • union(i, j): Merges the two subsets containing i and j.
  • When to Use:
    • Problems involving connected components, network connectivity, or dynamic connectivity.
    • When you are given an edge list and need to determine if adding an edge creates a cycle (e.g., Redundant Connection).

Practice Problems

2.4. Topological Sort

A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.

  • When to Use:
    • Task scheduling with dependencies (e.g., Course Schedule).
    • Any problem that requires a specific order of processing in a DAG.
  • Detection of Cycles: If a topological sort cannot include all vertices, the graph has a cycle.

BFS (Kahn’s Algorithm) Implementation

  1. In-degrees: Compute the in-degree (number of incoming edges) for every vertex.
  2. Queue: Initialize a queue with all vertices that have an in-degree of 0.
  3. Process: While the queue is not empty: a. Dequeue a vertex u and add it to the sorted list. b. For each neighbor v of u: i. Decrement the in-degree of v. ii. If the in-degree of v becomes 0, enqueue v.

Practice Problems

2.5. Shortest Path Algorithms

  • BFS: For unweighted graphs.
  • Dijkstra’s Algorithm: For weighted graphs with no negative edge weights. It’s a single-source shortest path algorithm.
    • Mechanism: Uses a priority queue (min-heap) to always explore the “cheapest” path next.
  • Bellman-Ford Algorithm: For weighted graphs, can handle negative edge weights.
    • Mechanism: Relaxes all edges V-1 times. A final iteration can detect negative weight cycles. Slower than Dijkstra’s.

3. Other Key Patterns

3.1. Intervals

Problems involving time intervals, ranges, or merging overlapping segments.

Core Pattern

  1. Sort: Sort the intervals, usually by their start times. This is almost always the first step.
  2. Iterate & Merge/Compare: Iterate through the sorted intervals, comparing the current interval with the previous one (or the last one in your result list).
  3. Logic:
    • Overlap Check: interval_b.start < interval_a.end.
    • Merging: If they overlap, the new merged interval is [min(a.start, b.start), max(a.end, b.end)].

Practice Problems

3.2. Linked Lists

Focus on pointer manipulation. Drawing the nodes and pointers is crucial.

Core Routines

  • Dummy Head Node: Use a dummy = ListNode(0) to simplify edge cases for list head modifications (e.g., removing the first element). Return dummy.next.
  • Fast & Slow Pointers: Find the middle node or detect a cycle.
  • In-place Reversal: A fundamental subroutine.
  • Merging Two Lists: Another key subroutine.

Problem Categories

  1. Reversal / Reordering:
  2. Cycle Detection / Middle Element:
  3. Merging / Two Lists:
  4. Deletion:
  5. Design:
    • LRU Cache (Medium) - (Use a hash map and a doubly-linked list)

3.3. Trees

Hierarchical data structures. Most problems can be solved with recursion (DFS) or iteration (BFS).

Traversal Types

  • DFS (Depth-First Search):
    • In-order: Left -> Root -> Right (yields sorted elements in a BST)
    • Pre-order: Root -> Left -> Right (useful for copying a tree)
    • Post-order: Left -> Right -> Root (useful for “bottom-up” calculations)
  • BFS (Breadth-First Search):
    • Level-order traversal. Uses a queue. Perfect for finding the “first” or “shallowest” node that meets a condition.

Practice Problems

3.4. Monotonic Stack

A stack where the elements are always in a sorted order (either increasing or decreasing).

  • When to Use:
    • Problems involving finding the next greater/smaller element or previous greater/smaller element for each item in an array.
  • Mechanism: As you iterate through the array, you pop elements from the stack that violate the monotonic property. The element that was just popped is then processed, often in relation to the current element.

Practice Problems

3.5. Greedy Algorithms

Making the locally optimal choice at each step with the hope of finding a global optimum.

  • When to Use:
    • Does the problem have the “greedy choice property”? (A local optimum leads to a global one).
    • Does it have the “optimal substructure” property? (An optimal solution to the problem contains optimal solutions to subproblems).
  • Strategy: Sort the input and process it piece by piece, making the most immediate, obvious best choice.

Practice Problems

3.6. Dynamic Programming (DP)

Breaking down a problem into smaller overlapping subproblems and solving each subproblem only once, storing their solutions to avoid re-computation.

  • Key Signals:
    • The problem asks for a max, min, count, or true/false answer.
    • You see phrases like “longest…”, “shortest…”, “number of ways…”.
    • You can define a state based on one or more variables (e.g., dp[i] = max value up to index i).
  • Approaches:
    • Top-Down (Memoization): Use recursion and a cache (e.g., a hash map or array) to store results. More intuitive.
    • Bottom-Up (Tabulation): Use an array or matrix (dp table) and fill it out iteratively from the base cases up. More efficient.

DP Patterns

  • Fibonacci Style / 1D DP: dp[i] depends on dp[i-1], dp[i-2], etc. (e.g., Climbing Stairs, House Robber).
  • Knapsack (0/1, Unbounded): dp[i][w] = max value using first i items with capacity w.
  • Longest Common Subsequence / 2D DP: dp[i][j] depends on dp[i-1][j], dp[i][j-1], etc.
  • State Machine: The state transitions depend on actions (e.g., Buy and Sell Stock with Cooldown).

Practice Problems

Master Resource List

Pattern Guides & Templates

General Blogs & Walkthroughs