题目重点：按 getConnections 接口求两位候选人的最少边数，明确有向/双向、不可达、可见性和生产查询规模。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码把 getConnections() 暴露的边当有向边，以 id 去重，start 与 target 同 ID 返回 0，不可达返回 -1；若真实 connection 对称，可在图构建层保证反向边。
- 题目未要求可见性过滤、双向 BFS、缓存或跨机分布式实现；它们只作为 production followup 的条件选项，不写成基础题固定约束。
解题路线
- 从 start 入队 (node,0)，visited 先标 start.id；每次出队扫描 getConnections()，第一次遇 target 就返回当前距离+1。BFS 分层保证首次命中路径边数最少。
- 按 ID 而非对象地址判重，避免同一候选人经多个对象实例进入队列；若 getConnections() 有分页/远端调用，不能假设一次拉全邻居，需控制批量、超时和 API 成本。
- 无向且能取反向邻居时，可从两端做双向 BFS、每次扩较小 frontier，通常减少高分支图访问量；有向图若 target 端没有反向索引，不能简单从 target 沿正向边搜。
- 多次查询的生产设计先定义权限可见范围和最大搜索深度，再考虑热点端点缓存、邻接分页、索引与批量预计算；权限或连接变化时按版本失效。高阶社交图的高出度节点需限流和合理截断，截断会把“精确距离”变成“距离≤D”判定，必须明示。
手动走一遍
训练图 A→B→C：A 到 C 为 2，C 到 A 不可达返回 -1；如果把每条边都视为无向，则 C 到 A 也是 2。这个差异来自题干未说明边方向，所以面试时先问。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract for getDistance(Candidate c1, Candidate c2).
The post gives id/getConnections and asks for BFS. Directionality, missing
nodes and access control are not specified; this model follows visible edges.
"""
from collections import deque
from dataclasses import dataclass, field
@dataclass
class Candidate:
id: int
connections: list["Candidate"] = field(default_factory=list)
def getConnections(self) -> list["Candidate"]:
return self.connections
def getDistance(start: Candidate, target: Candidate) -> int:
if start.id == target.id:
return 0
queue = deque([(start, 0)])
visited = {start.id}
while queue:
person, distance = queue.popleft()
for neighbor in person.getConnections():
if neighbor.id == target.id:
return distance + 1
if neighbor.id not in visited:
visited.add(neighbor.id)
queue.append((neighbor, distance + 1))
return -1
if __name__ == "__main__":
a, b, c = Candidate(1), Candidate(2), Candidate(3)
a.connections = [b]
b.connections = [c]
assert getDistance(a, c) == 2
assert getDistance(c, a) == -1 # Explicit directed training model.
复杂度
局部图有 V 个可达节点、E 条可见边时，普通 BFS 时间 O(V+E)、队列与 visited 空间 O(V)；若邻居通过网络拉取，实际延迟还受远端批量与 fanout 影响。双向 BFS 的收益取决于图无向性、度分布和反向索引，不保证统一的固定倍数。
易错点与追问
容易失分的边界
- 用 DFS 返回第一条找到的路径，未必最短。
- 入队后才判重，重复连接导致大量排队。
- 直接用对象地址判重，同 id 的不同实例重复访问。
- 在没有反向邻接索引的有向图中声称双向 BFS 总可行。
- 缓存距离时忽略用户可见性和图更新。
继续深挖
- 图是否无向？若有向，如何建立反向索引？
- 只需判断距离是否≤3，怎样更早停止？
- getConnections() 分页且单次网络请求成本很高怎么办？
- 隐私设置变化后缓存如何失效？
- 如何对高出度节点防止搜索爆炸？
