英伟达面试

1. 字符串排列（迭代和递归）

知识点： 回溯算法、递归、排列组合

解答逻辑：

• 递归： 使用回溯法，每次选择一个字符，递归处理剩余字符
• 迭代： 使用字典序算法或交换法

参考示例：

### 递归解法
def permute_recursive(s):
 def backtrack(path, used):
 if len(path) == len(s):
 result.append(''.join(path))
 return
 for i in range(len(s)):
 if used[i]:
 continue
 used[i] = True
 path.append(s[i])
 backtrack(path, used)
 path.pop()
 used[i] = False
 result = []
 backtrack([], [False]*len(s))
 return result

2. 将零移到数组右侧

知识点： 双指针、数组操作

解答逻辑： 使用双指针，一个遍历数组，一个记录非零元素位置

参考示例：

def move_zeros(nums):
 j = 0
 for i in range(len(nums)):
 if nums[i] != 0:
 nums[j], nums[i] = nums[i], nums[j]
 j += 1
 return nums

3. 计算二叉树叶子节点数

知识点： 二叉树遍历、递归

解答逻辑： DFS遍历，统计无子节点的节点

参考示例：

def count_leaves(root):
 if not root:
 return 0
 if not root.left and not root.right:
 return 1
 return count_leaves(root.left) + count_leaves(root.right)

4. 合并重叠区间

知识点： 排序、贪心算法

解答逻辑： 先按起始位置排序，然后合并重叠区间

参考示例：

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

5. 实现快速排序

知识点： 分治算法、排序

解答逻辑： 选择基准，分区，递归排序左右子数组

参考示例：

def quick_sort(arr):
 if len(arr) <= 1:
 return arr
 pivot = arr[len(arr)//2]
 left = [x for x in arr if x < pivot]
 middle = [x for x in arr if x == pivot]
 right = [x for x in arr if x > pivot]
 return quick_sort(left) + middle + quick_sort(right)

6. 实现冒泡排序

知识点： 排序算法

解答逻辑： 相邻元素比较交换，每轮将最大元素移到末尾

参考示例：

def bubble_sort(arr):
 n = len(arr)
 for i in range(n):
 for j in range(0, n-i-1):
 if arr[j] > arr[j+1]:
 arr[j], arr[j+1] = arr[j+1], arr[j]
 return arr

7. 实现后序遍历算法

知识点： 二叉树遍历、栈操作

解答逻辑： 左右根顺序，可用递归或迭代实现

参考示例：

def postorder_traversal(root):
 result = []
 def dfs(node):
 if not node:
 return
 dfs(node.left)
 dfs(node.right)
 result.append(node.val)
 dfs(root)
 return result

8. 将二叉树转换为双向链表

知识点： 树与链表转换、中序遍历

解答逻辑： 中序遍历，维护前驱节点指针

参考示例：

def tree_to_doubly_list(root):
 def inorder(node):
 nonlocal first, last
 if not node:
 return
 inorder(node.left)
 if last:
 last.right = node
 node.left = last
 else:
 first = node
 last = node
 inorder(node.right)
 first, last = None, None
 inorder(root)
 first.left = last
 last.right = first
 return first

9. 在1-100数组中找重复数字

知识点： 数学方法、哈希表、位运算

解答逻辑： 求和法、哈希表法或Floyd环检测算法

参考示例：

def find_duplicate(nums):
 # 数学方法
 n = len(nums) - 1
 expected_sum = n * (n + 1) // 2
 actual_sum = sum(nums)
 return actual_sum - expected_sum

10. 计算二叉树高度

知识点： 递归、BFS/DFS

解答逻辑： 递归计算左右子树高度的最大值+1

参考示例：

def tree_height(root):
 if not root:
 return 0
 return 1 + max(tree_height(root.left), tree_height(root.right))

11. 将二叉树转换为特殊最大堆

知识点： 堆数据结构、树转换

解答逻辑： 先中序遍历获取有序数组，再按层次构建堆

参考示例：

def tree_to_max_heap(root):
 def inorder(node, values):
 if not node:
 return
 inorder(node.left, values)
 values.append(node.val)
 inorder(node.right, values)
 def build_heap(values, index):
 if index >= len(values):
 return None
 node = TreeNode(values[index])
 node.left = build_heap(values, 2*index + 1)
 node.right = build_heap(values, 2*index + 2)
 return node
 values = []
 inorder(root, values)
 values.sort(reverse=True) # 最大堆
 return build_heap(values, 0)

核心总结

Nvidia面试特点：

• 注重基础数据结构和算法
• 代码实现能力要求高
• 时间复杂度和空间复杂度分析重要
• 实际应用场景结合紧密

准备建议：

• 熟练掌握常见数据结构操作
• 理解算法的时间空间复杂度
• 练习递归和迭代两种实现方式
• 注重代码的简洁性和可读性