Microsoft 2025 Summer Intern 的一场校园 OA 在 Codility 上进行，100 分钟两题：让所有城市都能到达 0 号城市，以及相邻字符不同的树上最长路径。这场 Intern 笔试记录的两题都用树，但第二题需要同时维护向上传的状态和整棵树的答案。
这是历史校园批次，帖子未标注国家。美国 Senior 岗位另有面试官共享 Codility 链接的记录；带面试官的技术面与独立 OA 要分开准备。
第一题：把道路方向改成通往 0 号城市
题目描述
n 个城市由 n−1 条单向道路连接，忽略方向后是一棵树。每次能反转一条路，求让所有城市都能沿道路到达城市 0 的最少反转次数。
解题思路
把每条原始道路 u→v 存成两条遍历边：u 到 v 的代价为 1，v 到 u 的代价为 0。从 0 出发遍历，跳过父节点，把经过的代价相加。这里代价 1 表示道路朝离开根的方向，需要反转。
自拟例子：0→1、2→1、2→3。反转 0→1 和 2→3 后，所有城市都能到 0，答案为 2。树中每个节点到根只有一条无向路径，所以每条方向错误的边都必须修改，计数就是最优解。用显式栈可避开长链递归过深的问题。时间和空间均为 O(n)。
第二题：相邻字符不同的最长路径
题目描述
用 parent 数组给出一棵根为 0 的树，每个节点带一个字符。找一条节点不重复的路径，要求路径上每对相邻节点字符不同，返回最多能经过多少个节点。路径可以经过根，也可以完全留在某棵子树里。
解题思路
后序处理每个节点 u。先求所有子树的答案，再从与 u 字符不同的孩子中取最长的两条向下链 a、b。经过 u 的候选长度是 1+a+b；传给父节点的值只能是 1+max(a,b)，因为父节点接过来后不能再分叉。
自拟例子：parent=[−1,0,0,1,2]，字符依次为 a、b、c、c、b。路径 3→1→0→2→4 长度是 5。若每次只拿一条子链更新总答案，就会漏掉这条跨过根的路径。
父子字符相同时，停止的是两者之间的拼接，子树仍须完整计算。例如根和孩子都是 a，孩子下面接 b、c，两条分支能在孩子处组成长度 3 的路径。时间和空间均为 O(n)。
Microsoft OA 练习安排
可以用 100 分钟做一次模拟：两题各留 35 分钟，余下时间检查单节点、长链、星形树和全相同字符。再用口头表达解释第一题为何逐边计数最优、第二题为何只能向上传一条链，比重复抄 DFS 模板更有用。
另一场 Microsoft OA 的候选人遇到过两道算法题加一道调试题。题数、时长和平台操作以自己的邀请为准；样例通过后，仍要验证边界和最大输入。
FAQ
第一题为什么不用最短路算法？
底层结构是树，到 0 的无向路径唯一。目标是统计必须反向的道路，没有多条路线需要比较。
第二题返回边数还是节点数？
返回节点数。单节点答案是 1，合并两条子链时要加上当前节点。
字符相同就跳过整个子树吗？
不能。只禁止跨过这条父子边，子树内部仍能产生最长路径。
参考来源
- LeetCode：Microsoft Summer Intern 校园 OA 两题记录
- Reddit：Microsoft Codility OA 提交经历
- Taro：Microsoft 美国 Senior 工程师 Codility 技术面
关于 CSINTERVIEWHELP
准备 Microsoft OA 时，可以通过 CSINTERVIEWHELP 预约模拟练习和答题反馈。无论是 OA 题型解析、OA 辅导、VO 模拟面试、项目深挖还是系统设计训练，都可按具体岗位安排：CSINTERVIEWHELP · 服务详情
