携程9.20笔试四题：实时榜单与min-gcd迭代器

《面试题目》

1. 题目一：字母 a 的位置
2. 题目二：实时榜单
3. 题目三：双门控加权器
4. 题目四：min-gcd 迭代器

《参考解析》

题目一（字母 a 的位置）：固定长度、固定字符集的定位题，直接顺序扫描即可，O(n) 时间、O(1) 空间，属于热身题。识别信号是「别想复杂」——五分钟内写完，把时间留给后面的题。

题目二（实时榜单）：数据范围只有 100×100，维护「每人每题的最高分」（二维数组按 max 更新）再查询时暴力遍历所有人求和并按分数排序就够了，更新 O(题数)、查询 O(人数 log 人数)，完全在限制内。这题的考点其实是先看数据范围再选数据结构——规模小的时候，「不需要额外数据结构」本身就是正确答案。作为延伸可以说明真到千万级用户、高频更新时该怎么做：Redis ZSet（ZINCRBY 更新、ZREVRANGE 取 TopN，O(log n)）、分数范围小时用分段桶计数（O(1) 更新 + O(桶数) 查询）、或者堆维护 TopN；再大规模就要考虑分片榜单 + 定期合并。

题目三（双门控加权器）：这题的核心不在「想算法」，而在把一条计算链完整、正确地实现出来：门控计算 → Top-k 选择 → 归一化 → 与主分支相乘。边界主要在四处：① s_max ≤ 0 时归一化的分母可能为 0 或负数，要约定输出（置零或加 eps 并说明）；② Top-k 的并列处理——并列是否都保留、截断时按什么次序（用稳定排序保持原序），不同约定结果不同，要按题目要求并在代码注释里写明；③ 浮点稳定性，算 softmax 前先减去最大值再取 exp；④ 掩码用 0/1 还是 -inf 会影响后续乘法与归一化的语义，选错结果全错。实现建议把每一步拆成独立小函数便于对拍测试，这类题失分基本都是细节而不是思路。

题目四（min-gcd 迭代器）：核心观察是 gcd(a + i, b) 在很长一段连续 i 上保持不变——因为 gcd 的取值只会随 i 跨过与 b 的约数相关的位置而跳变，而 b 的约数只有 O(√b) 个（整除分块 / 调和级数思想）。所以不要逐个迭代求 gcd，而是：已知当前值 v，求最小的 d > 0 使 gcd(v + d, b) ≠ gcd(v, b)，把这一整段压成一次跳跃并一次性累加计数，跳到 v + d 继续。这样每次跳跃要么让 gcd 严格下降，要么跨过一个约数边界，总复杂度是 O(√b · log) 量级，是唯一能过大数据的做法。实现时注意 64 位溢出与 gcd 的边界（b = 0 时 gcd(v, 0) = v）。

笔试节奏建议：四题制的常见分配是「热身题 5 分钟 + 中档题各 15 分钟 + 难题留 25 分钟」，先把能拿的分全部拿到。每题写完先跑样例与边界（空输入、单元素、全相等、极大极小值）再提交——这类题的失分大多来自边界而不是算法。