北美sde面试算法只是速查表

北美SDE算法面试终极速查表

北美SDE面试中算法题占据了技术面试的核心地位，面试时间通常只有45分钟，需要在有限时间内快速识别题目类型、选择最优解法、写出bug-free代码。这份速查表按照数据结构和算法类型进行分类整理，帮助快速回忆关键知识点。

速查表使用方法

面试前15分钟快速浏览对应章节，重点关注时间复杂度和核心实现要点。遇到题目时先判断数据结构类型，再确定算法分类，最后套用对应的代码模板。每个算法都包含核心思想、复杂度分析、典型应用场景和实现要点四个部分。

数组类算法核心要点

Two Pointers技巧：用于处理有序数组或需要比较两个位置的问题，时间复杂度O(n)，空间复杂度O(1)。核心思想是设置左右指针向中间移动或同向移动。

典型应用：Two Sum in sorted array、Remove duplicates、Container with most water

实现要点：注意指针移动条件，避免死循环，处理边界情况

代码模板： def two_pointers(arr, target): left, right = 0, len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target: return [left, right] elif current_sum < target: left += 1 else: right -= 1 return []

Sliding Window技巧：用于处理子数组或子字符串问题，时间复杂度O(n)，空间复杂度O(1)或O(k)。核心思想是维护一个窗口，根据条件扩展或收缩窗口。

典型应用：Longest substring without repeating characters、Minimum window substring、Maximum sum subarray

实现要点：明确窗口扩展和收缩条件，使用HashMap记录窗口内元素状态

代码模板： def sliding_window(s, target): left = 0 window = {} result = 0

for right in range(len(s)):
    # 扩展窗口
    char = s[right]
    window[char] = window.get(char, 0) + 1
    
    # 收缩窗口
    while window_needs_shrink():
        left_char = s[left]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]
        left += 1
    
    # 更新结果
    result = max(result, right - left + 1)

return result

Binary Search变种：用于有序数组查找问题，时间复杂度O(log n)，空间复杂度O(1)。核心思想是每次排除一半搜索空间。

典型应用：Search in rotated sorted array、Find first and last position、Search insert position

实现要点：注意边界条件，选择合适的mid计算方式，避免整数溢出

代码模板： def binary_search(arr, target): left, right = 0, len(arr) - 1

while left <= right:
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return -1

链表类算法核心要点

Fast and Slow Pointers：用于检测环、找中点等问题，时间复杂度O(n)，空间复杂度O(1)。核心思想是设置快慢指针，快指针每次移动两步，慢指针每次移动一步。

典型应用：Detect cycle、Find middle node、Remove nth node from end

实现要点：注意空指针检查，处理链表长度为奇数或偶数的情况

代码模板： def has_cycle(head): if not head or not head.next: return False

slow = fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    
    if slow == fast:
        return True

return False

链表反转：用于反转链表或部分反转，时间复杂度O(n)，空间复杂度O(1)。核心思想是改变指针方向。

典型应用：Reverse linked list、Reverse nodes in k-group、Swap nodes in pairs

实现要点：保存next节点，正确更新指针关系，处理头节点变化

代码模板： def reverse_list(head): prev = None current = head

while current:
    next_temp = current.next
    current.next = prev
    prev = current
    current = next_temp

return prev

树类算法核心要点

DFS遍历：包括前序、中序、后序遍历，时间复杂度O(n)，空间复杂度O(h)其中h是树高。核心思想是递归或栈实现深度优先搜索。

典型应用：Tree traversal、Path sum、Maximum depth、Validate BST

实现要点：选择合适的遍历顺序，处理空节点，注意递归终止条件

代码模板： def inorder_traversal(root): result = []

def dfs(node):
    if not node:
        return
    
    dfs(node.left)
    result.append(node.val)
    dfs(node.right)

dfs(root)
return result

BFS遍历：层序遍历，时间复杂度O(n)，空间复杂度O(w)其中w是最大宽度。核心思想是使用队列实现广度优先搜索。

典型应用：Level order traversal、Minimum depth、Binary tree right side view

实现要点：使用队列，按层处理节点，记录每层节点数量

代码模板： def level_order(root): if not root: return []

result = []
queue = [root]

while queue:
    level_size = len(queue)
    level_nodes = []
    
    for _ in range(level_size):
        node = queue.pop(0)
        level_nodes.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    result.append(level_nodes)

return result

图类算法核心要点

DFS图遍历：用于连通性检查、路径查找等，时间复杂度O(V+E)，空间复杂度O(V)。核心思想是递归或栈实现深度优先搜索。

典型应用：Number of islands、Course schedule、Clone graph

实现要点：使用visited集合避免重复访问，处理有向图和无向图的区别

代码模板： def dfs_graph(graph, start, visited): if start in visited: return

visited.add(start)

for neighbor in graph[start]:
    dfs_graph(graph, neighbor, visited)

BFS图遍历：用于最短路径、层级关系等，时间复杂度O(V+E)，空间复杂度O(V)。核心思想是使用队列实现广度优先搜索。

典型应用：Shortest path、Word ladder、Minimum steps

实现要点：使用队列和visited集合，记录距离或层数

代码模板： def bfs_graph(graph, start, target): queue = [(start, 0)] visited = {start}

while queue:
    node, distance = queue.pop(0)
    
    if node == target:
        return distance
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append((neighbor, distance + 1))

return -1

动态规划核心要点

一维DP：用于序列问题，时间复杂度O(n)，空间复杂度O(n)或O(1)。核心思想是状态转移方程。

典型应用：Fibonacci、Climbing stairs、House robber、Maximum subarray

实现要点：定义状态含义，找出状态转移方程，确定初始状态和边界条件

代码模板： def dp_1d(arr): n = len(arr) if n == 0: return 0

dp = [0] * n
dp[0] = arr[0]

for i in range(1, n):
    dp[i] = max(dp[i-1], arr[i])  # 状态转移方程

return dp[n-1]

二维DP：用于矩阵或两个序列问题，时间复杂度O(mn)，空间复杂度O(mn)。核心思想是二维状态转移。

典型应用：Unique paths、Longest common subsequence、Edit distance

实现要点：定义二维状态，找出状态转移方程，初始化边界条件

代码模板： def dp_2d(grid): m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)]

# 初始化
dp[0][0] = grid[0][0]

for i in range(m):
    for j in range(n):
        if i > 0:
            dp[i][j] = max(dp[i][j], dp[i-1][j] + grid[i][j])
        if j > 0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + grid[i][j])

return dp[m-1][n-1]

回溯算法核心要点

排列组合：用于生成所有可能的排列或组合，时间复杂度O(n!)或O(2^n)，空间复杂度O(n)。核心思想是递归尝试所有可能性。

典型应用：Permutations、Combinations、Subsets、N-Queens

实现要点：定义递归函数，设置终止条件，回溯时恢复状态

代码模板： def backtrack_combinations(nums, target): result = []

def backtrack(start, path, remaining):
    if remaining == 0:
        result.append(path[:])
        return
    
    for i in range(start, len(nums)):
        if nums[i] <= remaining:
            path.append(nums[i])
            backtrack(i + 1, path, remaining - nums[i])
            path.pop()

backtrack(0, [], target)
return result

路径搜索：用于在图或矩阵中找路径，时间复杂度取决于搜索空间，空间复杂度O(path_length)。核心思想是DFS加回溯。

典型应用：Word search、Path with maximum gold、Sudoku solver

实现要点：标记访问状态，搜索完成后恢复状态，处理边界条件

代码模板： def word_search(board, word): def backtrack(i, j, index): if index == len(word): return True

    if (i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or 
        board[i][j] != word[index]):
        return False
    
    temp = board[i][j]
    board[i][j] = '#'  # 标记已访问
    
    found = (backtrack(i+1, j, index+1) or backtrack(i-1, j, index+1) or
            backtrack(i, j+1, index+1) or backtrack(i, j-1, index+1))
    
    board[i][j] = temp  # 恢复状态
    return found

for i in range(len(board)):
    for j in range(len(board[0])):
        if backtrack(i, j, 0):
            return True
return False

贪心算法核心要点

区间问题：用于处理时间安排、资源分配等，时间复杂度O(n log n)，空间复杂度O(1)。核心思想是局部最优选择。

典型应用：Meeting rooms、Non-overlapping intervals、Minimum arrows

实现要点：选择合适的排序策略，确定贪心选择标准

代码模板： def interval_scheduling(intervals): 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

排序算法核心要点

Quick Sort：平均时间复杂度O(n log n)，最坏O(n^2)，空间复杂度O(log n)。核心思想是分治法。

实现要点：选择pivot，分区操作，递归排序

代码模板： def quick_sort(arr, low, high): if low < high: pi = partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high)

def partition(arr, low, high): pivot = arr[high] i = low - 1

for j in range(low, high):
    if arr[j] <= pivot:
        i += 1
        arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

Merge Sort：时间复杂度O(n log n)，空间复杂度O(n)。核心思想是分治合并。

实现要点：分割数组，合并有序数组

代码模板： def merge_sort(arr): if len(arr) <= 1: return arr

mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])

return merge(left, right)

def merge(left, right): result = [] i = j = 0

while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1

result.extend(left[i:])
result.extend(right[j:])
return result

哈希表应用要点

频率统计：用于计数、查找重复等，时间复杂度O(n)，空间复杂度O(n)。核心思想是空间换时间。

典型应用：Two sum、Group anagrams、Top k frequent elements

实现要点：选择合适的key，处理哈希冲突

代码模板： def two_sum(nums, target): num_map = {}

for i, num in enumerate(nums):
    complement = target - num
    if complement in num_map:
        return [num_map[complement], i]
    num_map[num] = i

return []

前缀和技巧：用于快速计算区间和，时间复杂度O(n)预处理，O(1)查询，空间复杂度O(n)。

典型应用：Subarray sum equals k、Range sum query

实现要点：构建前缀和数组，利用前缀和性质

代码模板： def subarray_sum(nums, k): count = 0 prefix_sum = 0 sum_map = {0: 1}

for num in nums:
    prefix_sum += num
    
    if prefix_sum - k in sum_map:
        count += sum_map[prefix_sum - k]
    
    sum_map[prefix_sum] = sum_map.get(prefix_sum, 0) + 1

return count

延伸阅读 Recommended Reading

for right in range(len(s)): # 扩展窗口 char = s[right] window[char] = window.get(char, 0) + 1 # 收缩窗口 while window_needs_shrink(): left_char = s[left] window[left_char] -= 1 if window[left_char] == 0: del window[left_char] left += 1 # 更新结果 result = max(result, right - left + 1) return result

while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1

result = [] queue = [root] while queue: level_size = len(queue) level_nodes = [] for _ in range(level_size): node = queue.pop(0) level_nodes.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_nodes) return result

while queue: node, distance = queue.pop(0) if node == target: return distance for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance + 1)) return -1

# 初始化 dp[0][0] = grid[0][0] for i in range(m): for j in range(n): if i > 0: dp[i][j] = max(dp[i][j], dp[i-1][j] + grid[i][j]) if j > 0: dp[i][j] = max(dp[i][j], dp[i][j-1] + grid[i][j]) return dp[m-1][n-1]

def backtrack(start, path, remaining): if remaining == 0: result.append(path[:]) return for i in range(start, len(nums)): if nums[i] <= remaining: path.append(nums[i]) backtrack(i + 1, path, remaining - nums[i]) path.pop() backtrack(0, [], target) return result

if (i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]): return False temp = board[i][j] board[i][j] = '#' # 标记已访问 found = (backtrack(i+1, j, index+1) or backtrack(i-1, j, index+1) or backtrack(i, j+1, index+1) or backtrack(i, j-1, index+1)) board[i][j] = temp # 恢复状态 return found for i in range(len(board)): for j in range(len(board[0])): if backtrack(i, j, 0): return True return False

while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result

北美sde面试算法只是速查表

Recommended Reading

延伸阅读 Recommended Reading

免费咨询美国求职

北美sde面试算法只是速查表

Recommended Reading

延伸阅读 Recommended Reading