Rubrik OA 面试真题解析：有向图中查找有 IP 的节点及可达节点

Given a starting node in a directed graph of immutable nodes, find a set of nodes that either:

• have an IP address, or
• can reach a node having an IP address.

Node in the graph is represented as:

Node {label -> String // unique in the graph
  connections -> List[Node]
  hasIpAddress -> Boolean
}

(t) -> Node has IP address

(f) -> Node doesn’t have an IP address

这道题本质上是在有向图里做一次可达性标记：从起点出发，找到所有“自己有 IP 地址”或“能够沿着有向边到达某个有 IP 地址节点”的节点集合。由于节点是不可变结构，并且图可能存在共享子图，通常会用 DFS 或反向传播的思路，配合 visited 去避免重复遍历和环导致的死循环。关键点在于不仅要当前节点是否满足条件，还要把“能到达满足条件的后继节点”的祖先一并收集起来，最终返回满足条件的所有节点。