白板编程完全攻略：征服现场面试的终极考验

void findPaths(TreeNode* root) {
    // 写了5行后卡住
    // 擦掉重写
    // 又写了8行，发现逻辑错误
    // 再擦掉...
}

面试官：这道题需要找出所有从根到叶子的路径。
我理解是深度优先搜索，每到一个叶子节点就记录一条路径。
我打算用递归实现，维护一个当前路径的列表。
时间复杂度是O(n)，因为要访问每个节点。
空间复杂度最坏是O(n)，当树退化为链表时。
您觉得这个思路可以吗？

def is_palindrome(s: str) -> bool:
    # 移除非字母数字字符，转小写
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    # 直接比较反转
    return cleaned == cleaned[::-1]

# 测试
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

面试官，这道题我分两步处理：

第一步：预处理字符串
- 移除非字母数字字符
- 统一转为小写

第二步：判断回文
- 使用双指针，从两端向中间移动
- 比较对应字符是否相同

时间复杂度：O(n)
空间复杂度：O(n)（预处理）或O(1)（双指针直接处理）

我先写预处理版本：

def is_palindrome(s):
    # 预处理
    cleaned = ""
    for c in s:
        if c.isalnum():
            cleaned += c.lower()
    
    # 双指针判断
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True

（边写边解释）这里我先用一个循环预处理字符串，
然后用双指针从两端比较...

面试官：找出数组中第K大的元素。

候选人：好的，让我确认一下：
- 数组中是否有重复元素？
- K的范围是1到数组长度吗？
- 是否要求原地操作？

面试官：可能有重复，K在有效范围内，不要求原地。

候选人：明白了。我打算用快速选择算法，
平均时间复杂度O(n)，最坏O(n²)。
或者用最小堆，时间复杂度O(n log k)。
考虑到数组可能很大，我倾向于快速选择。
您觉得这个方向可以吗？

面试官：可以，开始吧。

伪代码：
function findKthLargest(arr, k):
    left = 0, right = len(arr) - 1
    target = len(arr) - k  // 第K大 = 第(n-k)小
    
    while left <= right:
        pivot_index = partition(arr, left, right)
        
        if pivot_index == target:
            return arr[pivot_index]
        elif pivot_index < target:
            left = pivot_index + 1
        else:
            right = pivot_index - 1

// 这样写完后，再补充partition函数

候选人（边写边说）：
"这里我初始化左指针为0，右指针为数组长度减1...
然后计算中间位置mid...
比较中间元素和目标值...
如果相等，直接返回mid...
如果中间元素小于目标值，说明目标在右半部分，
所以left = mid + 1..."

def f(a, b):
    c = 0
    for i in a:
        if i == b:
            c += 1
    return c

def count_occurrences(arr, target):
    count = 0
    for num in arr:
        if num == target:
            count += 1
    return count

// 主函数
function mergeSort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    
    return merge(left, right)  // 假设merge已实现

// 现在实现merge
function 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 log n)
- 每层递归需要O(n)时间合并
- 递归深度是log n层
- 所以总时间是O(n log n)

空间复杂度：O(n)
- 需要额外的数组存储结果
- 递归栈深度是O(log n)
- 所以总空间是O(n)"

面试官：很好，能优化空间吗？

def binary_search(arr, target):
    # 边界条件：空数组
    if not arr:
        return -1
    
    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  # 未找到

候选人：
"让我用一个例子测试一下。
数组是[1, 3, 5, 7, 9]，目标是5。

第一轮：left=0, right=4, mid=2
arr[2]=5，等于目标，返回2。
正确！"

面试官：试试目标不存在的情况。

候选人：
"好的，目标是6。

第一轮：left=0, right=4, mid=2
arr[2]=5 < 6，所以left=3

第二轮：left=3, right=4, mid=3
arr[3]=7 > 6，所以right=2

第三轮：left=3 > right=2，退出循环
返回-1。正确！"

┌─────────────────────────────────┐
│                                 │
│  // 主函数                      │
│  function solve(arr):          │
│      ...                       │
│                                 │
│  // 辅助函数                    │
│  function helper():            │
│      ...                       │
│                                 │
│  // 测试用例                    │
│  Input: [1, 2, 3]              │
│  Output: 6                     │
│                                 │
└─────────────────────────────────┘

（拿到题目后，沉默5分钟，开始写代码）
（写代码过程中，一言不发）
（写完后，说）"写完了。"

"这道题是...我的理解对吗？"
"我打算用...方法，时间复杂度是..."
"这里我遇到了一个问题，让我想想..."
"我写完了，让我用一个例子测试..."

"这个思路您觉得可行吗？"
"我这样处理边界条件对吗？"
"还有更优的解法吗？"

"这里我不太确定，让我再想想..."
"这个优化我暂时没想到，能给个提示吗？"
"这道题我之前没见过，但我可以尝试..."

"让我重复一下题目，确保我理解正确..."
"这道题有几个关键点..."
"我想确认一下边界条件..."

"这道题可以用...方法解决"
"我考虑了三种方案..."
"最优解应该是..."

"我先写主函数..."
"这里需要一个辅助函数..."
"我处理一下边界情况..."

"让我用一个例子测试..."
"边界情况是..."
"时间复杂度是...，空间复杂度是..."

AI面试官："请实现一个LRU缓存。"

你："这道题需要...（开始思考）"

AI面试官："很好，你提到了哈希表和双向链表。
          能详细说说它们如何配合吗？"

你："哈希表提供O(1)查找，
    双向链表维护访问顺序..."

AI面试官："正确！开始写代码吧。"

你写了代码，但有一个bug。

AI面试官："你的代码在...情况下会出错，
          能找出来吗？"

你："让我想想...（思考）"

AI面试官："提示：考虑缓存满的情况。"

你："哦！我忘记删除尾节点了！"

你写出了O(n²)的解法。

AI面试官："你的解法是正确的。
          但能优化到O(n log n)吗？"

你："让我想想...可以用排序..."

AI面试官："很好！还有更优的吗？"