2026-03-09 某宇宙厂暑期算法实习一面复盘

整体节奏：自我介绍 → 项目深挖 → 算法题 → ML题。这场一面最后没过。

面试安排在北京时间3月9日10

题目与我的作答

1. 项目：把选择权交给了面试官

面试官让我自己选一个项目讲。我装了，又把球踢回去，让面试官选一个他最想了解的。结果他真的选了个我不太想讲、准备不充分的项目，这一块就比较被动。

这件事其实很好避免：提前准备好一个最想讲、也最能经得住追问的项目，有机会自己选的时候就直接讲它。

2. 树的直径

题目是求树上的最长链，也就是树的直径，并证明算法正确。我当时用两遍 DFS 写出来了。

做法是先从任意点出发，找到距离最远的点 A；再从 A 出发，找到最远的点 B。A 到 B 的距离就是树的直径。

我当时留下的证明只记了“反证法”，没有把过程展开。下面把证明和参考实现补完整。

3. 用 SGD 求 sqrt(x)

这道题挺有意思，但我当时完全没想出来。感觉像以前 Deep Learning 课上做过的作业，只是具体怎么做已经忘了。

我只想到要定义一个 loss，写成了 (y - x)²，没有写出实现。这个 loss 最小的时候是 y=x，不是 y=√x，建模这一步就没对上目标。

复盘与重做

1. 树的直径：为什么两遍 DFS 就够？

关键是证明：从任意点出发，找到的最远点一定可以作为某条直径的端点。直径可能不唯一，不需要它属于预先指定的那一条。

把第一次的起点 S 当根，dep[u] 表示点 u 的深度。任取一条直径 U—V，设 U、V 的最近公共祖先是 C。因为 A 是离 S 最远的点，所以 dep[A] 不小于 dep[U] 和 dep[V]。

分两种情况：

• A 在 C 的子树里：U、V 至少有一个与 A 的最近公共祖先是 C，设这个端点是 U。那么 dist(A,U)=dep[A]+dep[U]-2dep[C]，不小于 dep[V]+dep[U]-2dep[C]，也就是原直径长度。
• A 不在 C 的子树里：A 与 U 的最近公共祖先在 C 上方，所以 dist(A,U) 同样不小于原直径长度。

树上任何路径都不可能比直径更长，因此这条从 A 出发的路径也是直径。再从 A 找最远点，就一定能得到直径长度。

下面按无权树写核心函数，节点从0编号；这是事后参考实现，不是当时留下的提交代码。两次遍历都是 O(N)。

def tree_diameter(graph):
    n = len(graph)
    if n == 0:
        return 0

    def farthest(start):
        dist = [-1] * n
        dist[start] = 0
        stack = [start]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    stack.append(v)
        end = max(range(n), key=dist.__getitem__)
        return end, dist[end]

    a, _ = farthest(0)
    _, diameter = farthest(a)
    return diameter

2. 求平方根：先把方程写对，再构造 loss

目标是找到非负的 y，使 y²=x。所以误差应该定义在 y² 和 x 之间：

$L(y)=(y^2-x)^2.$

求导得到：

$\frac{dL}{dy}=4y(y^2-x).$

然后按梯度下降更新：

$y\leftarrow y-\eta\cdot4y(y^2-x).$

这题虽然叫 SGD，但这里只有一个标量方程，没有要随机采样的一批训练样本；这里先把梯度下降的建模和更新过程讲清楚。

有两个细节要注意。第一，不能把初值设成0：对于正数 x，这时梯度也是0，会一直卡住。第二，学习率不能随便固定成一个数就认为对所有 x 都有效。数值变大以后，梯度可能很大，一步就跑飞了。

下面的参考代码从正数开始，学习率随 x 和当前 y² 的规模缩放，避免拿一个固定步长处理所有数值。重点仍然是上面的 loss 和梯度。

def sqrt_gd(x, steps=1000, tol=1e-10):
    if x < 0:
        raise ValueError('x must be nonnegative')
    if x == 0:
        return 0.0

    y = 1.0
    for _ in range(steps):
        error = y * y - x
        if abs(error) <= tol * x:
            break
        grad = 4 * y * error
        lr = 1 / (16 * max(x, y * y))
        y -= lr * grad
    return y

牛顿法可以作为事后补充。直接对 f(y)=y²-x 求根：

$y\leftarrow y-\frac{y^2-x}{2y}=\frac12\left(y+\frac{x}{y}\right).$

它和“先构造 loss 再沿梯度下降”是两条推导路线。面试要求用 SGD 时，先把要求的建模答清楚，再讨论别的方法。

这次最具体的两个教训也就这些：项目要自己提前选好；遇到优化题，先检查 loss 的最优点是不是自己真正想求的东西。