中国电信 计算机类 笔试

《面试题目》

1. 笔试共两小时，140 分，约 50~60 道单选加 3 道编程。
2. 第一部分行测（单选）：推理、找规律、分析题。
3. 第二部分专业知识（单选）：计算机网络、操作系统、Transformer、算法。
4. 编程题一：用 HashSet 统计打开的数量。
5. 编程题二：区间问题（差分数组）。
6. 编程题三：有向图最短路径（反向图 + BFS）。

《参考解析》

1. 时间分配：50~60 道单选加 3 道编程塞进两小时，平均每道选择题不到 1 分钟，必须先把编程题的时间预留出来（作者留了 55 分钟）。行测的推理和找规律题容易陷进去，遇到题干长或第一遍没思路的直接标记跳过，最后统一蒙，别在一道题上耗掉编程题的时间。
2. 差分数组：适合处理”多次区间加减、最后统一查询”的题型，做法是维护差分数组 d，区间 [l, r] 加 v 就执行 d[l] += v、d[r+1] -= v，全部操作完做一次前缀和还原出真实值，单次修改 O(1)。用的时候注意下标从 1 开始避免边界特判、还原后是否还需要在线查询（要在线就得换线段树/树状数组）、以及累加值的取值范围。
3. 大数溢出这个坑：这道题第一次只过了 85%，排查十几分钟才发现是 Java 的 long 溢出，换成 BigInteger 才过。经验是看到”区间加和”这类题先估上界：区间长度乘以单次增量再乘以操作次数，超过 2^63-1 就必须上大数类型；C++ 里同理要提前考虑 __int128。溢出不会报错，只会静默给出错值，所以写之前做一次量级估算比事后调试便宜得多。
4. 反向图 + BFS：求有向图中”从某点出发到目标点”的最短路径，如果要对多个起点反复查询，最省事的做法是把所有边反向建图，从目标点做一次 BFS，得到的就是每个点到目标点的距离，复杂度 O(V+E)，比每个起点各跑一次快得多。这题的边界在于不可达点的处理、重边与自环，以及 BFS 的队列实现别递归溢出。