微软 OA 最近又发了一批，8 月这场两道 Microsoft OA coding question 难度不算高，考的不是偏门算法，更多是实现能力和规则理解。但这两道都有很容易踩的边界坑——题 1 容易漏段长的判断，题 2 容易把”恰好到期”当成”还没过期”。
把两道题的题意和做法完整分享出来，帮正在准备微软 OA 的同学提前感受一下他家的题风。
OA 前可以先确认的几件事
正式开考前建议留出几分钟把环境捋顺，比一上来就刷题更管用。
- 设备与网络：尽量有线或稳定 Wi-Fi，关掉容易弹窗的软件；浏览器只留考试页，避免误触切屏。
- 规则与时间：看清时限、是否允许本地 IDE、能否用纸笔；微软这类有时不强制所有用例本地跑通，但提交前至少自己走过样例。
- 读题顺序：先通读两题，哪道规则更长、边界更多心里有数；实现题往往坑在「恰好相等算不算过期」这类一句话上。
- 输出与类型：返回值是整数、数组还是 long，题目怎么写就怎么接，避免格式问题白白丢分。
- 心态：遇到读着绕的题，先在草稿上用样例推一遍再写，比边写边猜更省时间。
题 1：字符串覆盖操作的最大次数
题意：给一个小写字母字符串 s，可以反复做这个操作：选三个连续位置 i、i+1、i+2，满足 s[i] == s[i+1] 且 s[i+1] != s[i+2]，然后把 s[i+2] 改成 s[i]。问最多能做多少次。
示例：s = “accept”，依次变成 acccept → acccct → accccc，共 3 次，之后无法再操作。字符串长度最大 2×10⁵，暴力模拟会超时。
思路：操作的本质是：两个相同的字母，可以向右”吞掉”紧跟着的不同字母，把它变成自己。不需要真的模拟每次修改，直接用双指针把字符串压成”连续相同字母段”，记下每段的字母和长度。
能发起操作的只有长度 ≥ 2 的段，因为需要两个相同字母才能往右推。对于每个位置，看它左边第一个长度 ≥ 2 的段是什么字母：如果和当前字母相同，这个位置不额外贡献；如果不同，贡献次数等于左边长度 ≥ 2 的段的个数。把所有位置的贡献累加就是答案。
这样按段统计是 O(n)，不用每次重新扫整个字符串。最容易漏的坑：段长为 1 的段不能发起操作，别把它算进去。
题 2：带 TTL 的 Session Token 管理
题意：实现一个 session 认证系统，每个 token 有创建时间，过期时间 = 创建时间 + TTL（秒）。支持三种操作：
generate：在当前时刻生成一个 token；renew：若 token 未过期则续期，否则忽略；count：返回当前时刻未过期的 token 数量。
关键规则：同一时刻先判定过期再执行操作；过期时间恰好等于当前时间，视为已过期——不能 renew，也不计入 count。
思路：题目保证时间戳非降，所以可以懒删除——不用每次主动清理，等处理查询时顺手把过期的清掉。
用哈希表存 token_id → 过期时间，小根堆按过期时间维护所有 token。每条查询进来，先把堆里过期时间 ≤ 当前 t 的全部弹出、同步从 map 里删掉。
generate：写入 map，过期时间 = t + TTL，入堆。renew：如果 id 在 map 中且过期时间 > t，更新为 t + TTL，再入堆。count：清理完过期后返回 map 的大小。
注意堆里可能有”过时条目”（renew 之后原来的过期时间还在堆里），清理时以 map 里记录的时间为准，不要直接信任堆顶。
最容易踩的坑：过期时间 == 当前时间，这个 token 已经死了，不能 renew，count 也不算它。
Microsoft OA coding question – FAQ
Q：第一题一定要压成段吗？ 不必死记「必须分段」，但分段能把「谁有资格向右覆盖」说清楚，也方便 O(n) 统计。直接模拟修改在长度 2e5 时过不去。
Q：第二题堆里有重复 id 怎么办？ 懒删除即可：弹出时若堆里的过期时间和 map 不一致，说明是旧记录，直接丢弃。不必每次 renew 都在堆里精确删除旧节点。
Q：count 很多时会不会慢？ 每次 count 前摊还清理过期，总复杂度与操作次数和 token 数量近线性，通常可过。
不同厂的 OA 风格差一截：有的偏算法建模，有的像这场，更像小型业务模块实现。若你正在排微软、Amazon 或其它家的笔试，又想先摸清题型和坑点，可以看看 InterviewShow 整理的近期北美OA真题笔记，按自己的进度取用就好。
加油，祝笔试顺利。