英伟达半导体校招软件工程师面试经验——求职精灵（finsight.work）

先问清：是否有重复字符、是否按字典序输出。

• 回溯：固定第 i 位，与后面每个字符交换，递归 i+1 后换回，本层用集合去重。
• 迭代：字典序法，先排序，反复找最右升序对、交换、反转后缀，天然有序。
• 复杂度：结果 n! 个，时间 O(n·n!)，栈深 O(n)。

def permute(s):
    res=[]
    def dfs(i):
        if i==len(s): res.append(''.join(s)); return
        for j in range(i,len(s)):
            s[i],s[j]=s[j],s[i]; dfs(i+1); s[i],s[j]=s[j],s[i]
    dfs(0); return res

去重版在循环前加 seen 判断即可。

边界：空数组、全零、无零；是否要求原地修改，这决定空间复杂度。

• 双指针：j 指向待填位置，i 遍历数组，遇到非零就交换并让 j 自增，零被挤到末尾且非零顺序不变。
• 复杂度：时间 O(n)，空间 O(1)；开新数组的写法更简单，但空间 O(n)，要先问是否允许。

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

若题目不要求保序，可用首尾指针减少交换次数。

先定义：叶子是左右子节点都为空的节点，空树返回 0。

• 递归：空返回 0，左右都空返回 1，否则返回左右子树之和。
• 迭代：用栈做深度优先，遇叶子计数，避免深树爆栈。
• 复杂度：时间 O(n)，空间 O(h)，链状最坏 O(n)。

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

若追问「第 k 层的叶子」，把深度一起传下去即可。

先确认：输入是否按起点有序、端点相接算不算重叠，这决定边界写法。

• 按起点排序后，后一个区间只可能与结果末尾重叠；重叠就把终点取较大值，否则另起一段。
• 复杂度：排序 O(n log n)，合并 O(n)，结果数组空间 O(n)。

def merge(iv):
    if not iv: return []
    iv.sort(key=lambda x:x[0]); res=[iv[0][:]]
    for s,e in iv[1:]:
        if s<=res[-1][1]: res[-1][1]=max(res[-1][1],e)
        else: res.append([s,e])
    return res

输入本身有序时可省掉排序，总时间降到 O(n)。

先说清返回新头节点；空链表和单节点要能直接返回。

• 三指针：每步先暂存 next，再把 cur.next 指向 prev，最后 prev 与 cur 同步后移，prev 即新头。
• 递归：先反转后面的部分，再让 head.next.next 指回 head，并把 head.next 置空。
• 复杂度：时间 O(n)；迭代空间 O(1)，递归 O(n)。

def reverse(h):
    prev,cur=None,h
    while cur:
        nxt=cur.next; cur.next=prev; prev,cur=cur,nxt
    return prev

易错点：忘记暂存 next 会断链，忘记置空会成环。

前提：原地、升序、稳定；长度小于 2 直接返回。

• 外层跑 n-1 轮，内层相邻比较交换，每轮把最大值送到末尾。
• 优化：加 swapped 标志，某轮无交换就提前结束，最好降到 O(n)。
• 复杂度：平均与最坏 O(n²)，最好 O(n)，空间 O(1)，稳定。

def bubble(a):
    for i in range(len(a)-1):
        ok=True
        for j in range(len(a)-1-i):
            if a[j]>a[j+1]:
                a[j],a[j+1]=a[j+1],a[j]; ok=False
        if ok: break
    return a

大数据量工程上用快排或归并，这题考基本功。

后序是左右根，递归和迭代都要会写。

• 递归：先递归左子树，再右子树，最后访问根。
• 迭代：按根右左的顺序入栈遍历，结果整体反转，就得到左右根。
• 复杂度：时间 O(n)，递归空间 O(h)，迭代最坏 O(n)。

def postorder(root):
    res,st=[],[root] if root else []
    while st:
        n=st.pop(); res.append(n.val)
        if n.left: st.append(n.left)
        if n.right: st.append(n.right)
    return res[::-1]

若追问「不反转结果怎么写」，用 prev 指针模拟调用栈。

先问：是否原地改指针、是否要循环链表。

• 中序即升序，遍历时用 last 记前驱，last.right 指当前、当前.left 指 last。
• 结束后若做循环链表再首尾相接，否则头.left 与尾.right 置空。
• 复杂度：时间 O(n)，空间 O(h)。

def to_list(root):
    first=last=None
    def dfs(n):
        nonlocal first,last
        if not n: return
        dfs(n.left)
        if last: last.right,n.left=n,last
        else: first=n
        last=n; dfs(n.right)
    dfs(root); return first

改指针前没暂存右子树，遍历会断。

先问条件：值域是 1 到 n 还是 1 到 100、只有一个重复还是多个、能否改数组，这三点决定解法。

• 求和：总和减去 1 到 n 之和，时间 O(n)、空间 O(1)，但只在「恰好一个重复、其余各出现一次」时成立。
• 快慢指针：下标当指针、值当跳转，环的入口即重复数，时间 O(n)、空间 O(1)，要求值域在 1 到 n。
• 哈希或取负标记：通用性最好，代价是 O(n) 空间或修改原数组。

def dup(a):
    s=f=0
    while True:
        s=a[s]; f=a[a[f]]
        if s==f: break
    s=0
    while s!=f: s,f=a[s],a[f]
    return s

多个重复时只能用哈希或排序。

先对齐定义：高度按节点数还是边数算，空树是 0 还是 -1，不同定义答案差一。

• 递归：空返回 0，否则左右子树较大值加一，代码最短。
• 迭代：层序遍历，每处理完一层计数加一。
• 复杂度：时间 O(n)；递归空间 O(h)，层序空间最坏 O(n)。

def height(r):
    if not r: return 0
    return 1+max(height(r.left),height(r.right))

若追问「判断是否平衡」，改成后序一次遍历同时返回高度与标记，避免 O(n²)。定义先对齐。

先确认结构能否改变：要求完全二叉树时，中序取升序、反转、按层序填充。

• 中序得升序数组，反转即降序，再按 2i+1、2i+2 建树，父下标小于子下标，父值必不小于子值。
• 时间与空间均 O(n)。

def to_heap(root):
    v=[]
    def ino(n):
        if n: ino(n.left); v.append(n.val); ino(n.right)
    ino(root); v.reverse()
    def build(i):
        if i>=len(v): return None
        n=TreeNode(v[i])
        n.left,n.right=build(2*i+1),build(2*i+2)
        return n
    return build(0)

形状必须保留时，只能自底向上交换值。