中国电信天翼云机考 三道编程题解析

《面试题目》

选择题

1. 单选题 25 道，涉及数据库 SQL、Agent、线程进程、Linux 命令、C++ 代码等。
2. 多选题 5 道。

编程题

3. 闸机许可模拟：每个许可有唯一编号和可使用次数上限，编号不存在或次数为 0 视为失效。现有 n 行指令，ISSUE 生成许可（仅当该许可失效时才能生成，否则拒绝），PASS 通过闸机（仅当所需许可存在且有效时可通过，否则拒绝），CANCEL 使一个许可立即失效（仅当许可存在且有效时，否则拒绝）。输出最终成功通过闸机次数、被拒绝命令次数、剩余有效指令数、所有有效指令可使用次数总和。

输入：
6
ISSUE 100 2
ISSUE 200 1
ISSUE 100 3
PASS 100
CANCEL 200
PASS 200
输出：
1 2 1 1

4. 有效排列构造：给正整数 n（1 ≤ n ≤ 2×10^5），{p_1, p_2, ..., p_n} 是 {1, 2, ..., n} 的一个排列，若任意 1 ≤ i < n 都满足 p_i + p_(i+1) 是合数，则称该排列有效。请输出任意一种有效排列，不存在则输出 -1。例如 n=1 时只有 {1}，输出 1；n=2 时 {1,2} 与 {2,1} 都不符合，输出 -1。

5. 平衡相位子数组：长度为 n 的数组 {a_n}，给定正整数 p（2 ≤ p ≤ 20）。对任意子数组 [l, r]，若 i ∈ [l, r] 且 (i - l) mod p = j，则称第 i 个元素属于第 j 个相位；每个相位的元素之和称为相位和。若该子数组的所有相位和相等，则称它满足平衡相位。求满足平衡相位的子数组的最大长度。

《参考解析》

闸机许可模拟：核心是用哈希表维护「编号 → 剩余次数」，并且把「不存在」和「次数为 0」统一看成失效。逐条处理命令：ISSUE id cnt 时，若该编号当前有效（存在且次数大于 0）则拒绝并计入拒绝数，否则写入 cnt 并让有效指令数加一；PASS id 时，若编号有效则次数减一、通过数加一，次数减到 0 时有效指令数减一，否则拒绝；CANCEL id 时，若有效则置为失效（次数清零、有效指令数减一），否则拒绝。四个输出量在每条命令后维护成增量，最后一次性输出，不要每次遍历统计。两个坑：次数是累加量，必须用 long（题目里的次数上限可能到 10^9 量级，int 会溢出导致部分用例失败）；有效指令总次数之和是各指令剩余次数求和，同样要用 long。

相邻和为合数的排列构造：先看小 n。n=1 只有一个元素、没有相邻对，输出 1。n=2、3、4 无解：奇偶性决定了相邻两数同奇偶时和为偶数（≥4 必为合数），异奇偶时和为奇数；而在 1~4 的范围里任意一对异奇偶之和只可能是 3、5、7，全是质数，所以任何排列都至少需要一个奇偶相邻对，必然失败，输出 -1。n ≥ 5 时构造变得简单：把奇数升序排成一段、偶数排成另一段，段内相邻两数同奇偶、和是不小于 4 的偶数，必为合数；只需要让接缝处那一对（最大奇数 + 段首偶数）之和是合数即可。例如 n=5 用 1 3 5 4 2（5+4=9），n=6 用 1 3 5 4 2 6，n=7 用 1 3 5 7 2 4 6（7+2=9），n=9 用 1 3 5 7 9 6 2 4 8（9+6=15）。实现上就是先输出所有奇数，再在偶数里挑一个使「最大奇数 + 该偶数」为合数的放到最前，其余偶数顺序排放即可，O(n) 完成。

平衡相位子数组：直接按定义枚举所有 [l, r] 是 O(n²p)，会超时。关键观察是：所有相位和相等意味着总和必须能被 p 整除，且每个相位和都等于 总长相位和 / p；当 r - l + 1 < p 时存在空相位，此时所有相位和都必须为 0。用前缀和按「下标模 p 的余数类」拆开：预处理 p 个数组 T_r[i]，表示前 i 个元素中所有下标 k ≡ r (mod p) 的元素之和（递推 T_r[i] = T_r[i-1] + (i % p == r ? a[i] : 0)，实际只需一个长度为 n+1 的二维表或 p 个滚动数组）。固定左端点 l 时，第 j 个相位的元素下标是 l + j, l + j + p, ...，其和等于 T_{(l+j) mod p}[r] - T_{(l+j) mod p}[l-1]。于是只要对每个 l 枚举 j 做 O(p) 次判断就能得到以 l 开头的最大合法 r，总复杂度 O(n·p) = 4×10^6，可以接受。优化技巧：先判断长度是否达到 p，长度不足 p 时要求所有已存在相位和都为 0（也就是子数组元素全为 0）；长度足够时先算总和判断能否被 p 整除，再逐相位比对，能提前剪掉大量分支。

选择题覆盖的复习范围：这次的选择题偏基础但面很杂。数据库 SQL 重点看多表 join 与聚合、GROUP BY 与 HAVING 的执行顺序、索引失效场景、事务隔离级别；Linux 命令重点看 grep/awk/sed 的组合用法、ps 与 top 看进程、df 与 du 看磁盘、权限与 chmod 数字含义；线程进程重点看进程与线程的区别、进程间通信方式、线程同步原语与死锁条件；C++ 重点看指针与引用、虚函数、构造析构顺序、static 与 const；Agent 相关的题多为概念判断，至少要知道工具调用、上下文、编排与 RAG 的基本术语。多选一律按「少选错选都不得分」的规则处理，不确定就不选。