Coding interview 解题技巧与方法

多数候选人在 coding interview 最大的恐惧是：如果卡住不会做怎么办？好消息是，有结构化的方法可以提高你解题的成功率。从怎么找到解法，到如何优化 time/space complexity，下面是一些最实用的 tips 和 best practices。

如何找到解法

拿到题目后，先澄清问题并和面试官讨论几个可能的思路。但很多人卡在这一环。其实有一套结构化方式可用。

注意：不是每个技巧都适用于所有题，你也可以在同一个题上组合使用多个技巧。练习多了，你会逐渐建立直觉，知道什么问题适合用哪种技巧。

1. 画图可视化问题

为什么 coding interview 常在白板上进行？为什么讲解视频常用图？因为图能帮助理解问题。coding 很大一部分在于理解程序内部状态的变化，而图是表示内部状态的最佳方式。如果你难以理解解法，画出问题、以及关键步骤的内部状态。

这个方法特别适合 trees、graphs、matrices、linked lists。

Example

如何 return all elements of a matrix in spiral order？把 matrix 画出来，标清迭代方向，会非常直观。

2. 手动解题（不写 code）

先用“非程序员”的方式思考解题步骤，不写代码。很多时候你理解 sample input 的过程就是在这么做。

有时一个可行解法就是手动步骤的代码版本。如果你能总结出一套对所有例子都适用的规则，就可以直接写成 code。虽然不一定最优，但至少能拿到部分分数。

Example

如何不写 code 判断一个 tree 是否是 valid BST？你会先检查左子树全小于 root，再检查右子树全大于 root，然后对每个 node 重复。这个流程可行，你只需把它转成 code。

3. 举更多例子

无论你是否卡住，举更多例子都很有帮助：强化对题目的理解，避免过早写 code，帮助你发现 pattern，并能在最后作为 test cases 使用。

4. 拆分成更小的子问题

如果问题很大，从高层函数开始拆成小函数，逐个解决。这样不会被细节压垮，思路更清晰。

面试官也会看到你有结构化思路，即使你没来得及写完所有细节。

Example

Group Anagrams 可以拆成两步：给 string 做 hash；按 hash 分组。每步独立实现。可先写框架：

def group_anagrams(strings):
  def hash(string):
    # Fill in later
    pass

  def group_strings(strings_hashes):
    # Fill in later
    pass

  strings_hashes = [(string, hash(string)) for string in strings]
  return group_strings(strings_hashes)

然后再补每个函数的细节。但注意，有些最优解需要打破抽象，用一遍遍历完成多步。如果面试官要求优化，这是可讨论的方向。

5. 套用常见 data structures / algorithms

coding interview 的题通常规模较小，可在面试时间内解决，而且知识范围有限。一个实用方法是：遍历你知道的常见 data structures / algorithms，逐一尝试。

以下是最常见的数据结构（按出现频率）：

• Hash Maps：加速 lookup，几乎必用。
• Graphs：实体间关系可建图，用 graph algorithms。
• Stack / Queue：解析嵌套字符串（如数学表达式）常用 stack。
• Heap：涉及优先级排序，或找 Top K / Min K / Median。
• Tree/Trie：需要高效存储字符串并快速查询时使用。

Routines

• Sorting
• Binary search（有序数组时可更快查找）
• Sliding window
• Two pointers
• Union find
• BFS/DFS
• Traverse from the back
• Topological Sorting

以后会补充更多识别 data structures / routines 的技巧。

如何优化解法

当你给出初始解法后，面试官通常会问 “Can we do better”。下面是优化 time/space complexity 的常用方法。

如何优化 time complexity

1. 找出 Best Theoretical Time Complexity (BTTC)

BTTC 是理论上不可能被超越的时间复杂度。

简化例子：

• 数组求和 BTTC 是 O(n)，因为每个元素至少要看一次
• number of groups of anagrams 的 BTTC 是 O(nk)，n 是单词数，k 是单词最大长度
• matrix 里数 island 的 BTTC 是 O(nm)，n 行 m 列，每个 cell 至少看一次

知道 BTTC 的意义是避免去追求不可能比它更快的解。最优解最多到 BTTC，不可能更快。BTTC 不一定可实际达到，它只是理论下界。如果你的解法比 BTTC 慢，有优化空间（但不一定能完全达到）。

有些人以为 BTTC 就是元素数量，这是 不一定成立 的。经典例子：在 sorted array 查一个数，时间是 O(log n)（binary search），而不是 O(n)。找最大值甚至是 O(1)。因此必须仔细读题，别因为细节忽略而判断错 BTTC。

当你确定 BTTC 后，就知道优化目标范围了。如果你已经达到 BTTC，但面试官还让优化，通常有两件事：

• 做更少的工作（比如 O(n) 但做了两遍，改成一遍）
• 用更少空间（见下方 space complexity）

2. 找重复计算

暴力解法常重复做同样计算。当某个昂贵计算反复出现时，考虑复用结果。DP 是典型例子，但非 DP 问题也可能用这个技巧，只是需要预处理。

Example

Product of Array Except Self 的朴素解法是对每个 index 乘所有其他值，时间 O(n²)。但你会发现：

• result[n]: Product(nums[0] … nums[n-1]) * Product(nums[n + 1] … nums[N - 1])
• result[n + 1]: Product(nums[0] … nums[n]) * Product(num[n + 2] … nums[N - 1])

这里有大量重复计算。可以用 prefix array 复用结果，把时间降到 O(n)，代价是更多空间。

3. 换数据结构

数据结构选择影响巨大。它既能帮你找到解，也能优化解。

如果 lookup 是瓶颈，通常 hash table 能把 lookup 降到 O(1)。

Example

K Closest Points to Origin 可以先算距离再排序，时间 O(nlog n)。但用 Heap 可降到 O(nlog k)，因为 heap 操作是 O(log k)。换数据结构能大幅提升效率。

4. 去掉冗余工作

冗余工作不一定改变复杂度，但 coding 能力也会被评估，尽量写高效 code。

不要重复判断条件

• if not arr and len(arr) == 0 - 第二个条件多余。
• x < 5 and x < 10 - 第二个是第一个的子集。

注意判断顺序

• if slow() or fast() - 把 fast() 放左侧更高效。
• if likely() and unlikely() - 先执行更可能 false 的条件。

避免重复调用方法

如果某个属性需要函数计算，而值不变，就缓存。最常见是数组长度：length = len(array)，后续用 length。

Early termination

一旦找到答案就返回。例子：

def contains_string(search_term, strings):
  result = False
  for string in strings:
    if string.lower() == search_term.lower():
      result = True
  return result

可以优化成：

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True # 找到即返回
  return False

减少 loop 内工作

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True
  return False

search_term.lower() 每次 loop 都重复。可优化：

def contains_string(search_term, strings):
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

Be lazy

惰性计算：不必要就不算。例如：

def contains_string(search_term, strings):
  if len(strings) == 0:
    return False
  # 如果 strings 为空，不需要计算 search_term_lowercase
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

这是 micro-optimization，但能说明“只做必要计算”的思维。

如何优化 space complexity

一般来说 time 比 space 更重要。但当 time 已最优时，面试官可能要求你减少空间使用。以下是常用方法：

1. in-place 修改/覆盖输入

如果你创建了中间数据结构，会分配额外空间。一个 trick 是直接覆写输入数组，避免新分配。但要注意别破坏后续还需要的数据。

在真实工程里，mutating input 往往不推荐，因为难读难维护。所以这更多是面试技巧。

Example

Dutch National Flag 可以 O(n) time + O(n) space 解决，但面试官通常要 O(n) time + O(1) space，需要 in-place 排序。

First Missing Positive 也是例子：可以用原数组当 hash table，用负号标记数字是否出现。

2. 更换数据结构

是的，还是数据结构。是否用了最合适的结构？

Example

给你一组 strings，问多少个以某 prefix 开头。高效做法是用 Trie。

Next Steps

如果你还没看过，可以看看 coding interviews 全流程指南，其中包含：

• 高效学习计划：按剩余时间规划 topics 和题目
• Coding interview best practices cheatsheet：如何在面试中展示 hire signals
• Algorithms cheatsheets：各类 data structures 的 must-remembers