微软的题基本在一个不大的池子里轮换，复现率相当高。今年秋招还是 HackerRank 两题制，难度 medium 往上，26/27 届 intern 和 NG 都会碰到。这篇把近期 Microsoft coding assessment 里出现频率最高的三道真题集中拆解——一道 DP、一道字符串贪心、一道模拟。我自己实测 20 分钟出两题，思路对了都不难，坑全在细节。
真题一：Maximum Escape Game Score
题意
给一个整数数组，反复操作直到清空：选一个值 v，删掉所有的 v，得 v × count(v) 分；同时所有 v+1 和 v-1 也被删除，但不得分。求最大得分。
比如 [5,6,6,4,11]：取 11 得 11 分，取两个 6 得 12 分（5 和 7 白白清掉），最后取 4 得 4 分，一共 27。
再比如 [1,2,3,4]：取 2（清掉 1、3），再取 4，总分 6。跳过相邻值反而更优。
思路
第一反应”每次贪心拿最大的”是错的。选了 v，v±1 就全废了——这就是值域上的打家劫舍，值差 1 的互斥。注意是值相差 1，不是排序后下标相邻。
做法：统计每个值的频次，去重升序排成 keys，然后线性 DP。keys[i] 和 keys[i-1] 差 1 就只能从 dp[i-2] 转移，差 ≥ 2 就能从 dp[i-1] 转移。只用看前两项，因为排序去重后 keys[i] 顶多和 keys[i-1] 冲突。O(m log m)。
三个坑：收益是 v × count 别只加一个 v；”相邻”指值差 1；开头两个值恰好相邻且第二个更肥时，要允许丢掉第一个单独取第二个——漏了这项，[1,2] 接 [3,4,4,4] 这种数据就 WA，弱数据能过强数据挂，巨难查。
顺手把 LC 213（环形）和 337（树形）一起过了，是这题的两个经典变种。
真题二：字符串最大覆盖操作次数
题意
小写字母串 s，可以任意次操作：选三个连续字符，若 s[i] = s[i+1] 且 s[i+1] ≠ s[i+2]，就把 s[i+2] 改成 s[i]。问最多能操作几次。
比如 “accept”：cce → 改成 acccpt，再改成 acccct，再改成 accccc，一共 3 次，之后没得做了。
思路
把规则翻译一下就是：长度 ≥ 2 的连续相同字母段可以往右逐个”吞”字符，每吞一个算一次，吞完段更长还能接着吞。
所以先双指针扫出所有 ≥2 的段，然后算每个位置能贡献几次：基本上就是它左边 ≥2 段的个数，但如果这个位置的字符和左边最近那个段的字母相同，第一次覆盖不成立（改前改后一样），贡献减一。累加完事，O(n)。
难点全在把操作规则翻译成”段吞噬”这个模型，翻译对了代码十几行。
真题三：Session Token 认证系统
题意
实现一个 token 认证系统，统一 TTL，过期时间 = 创建时间 + TTL。三种操作：generate 创建、renew 给未过期的续期（过期或不存在就忽略）、count 返回当前未过期数量。
关键规则：过期判定发生在同一时间戳的任何操作之前，过期时间恰好等于当前时间的算已过期，不能续也不计数。
例子：TTL=5，generate aaa 1 → renew aaa 2 → count 6 → generate bbb 7 → renew aaa 8 → renew bbb 10 → count 15，输出 [1, 0]。
思路
题目保证时间戳递增，所以套路是：最小堆按过期时间存 token，map 存每个 id 的最新过期时间。每次处理操作前，先把堆里 ≤ 当前时间的全 pop 掉。
renew 的旧记录不用真删，惰性处理——pop 出来发现和 map 里对不上就直接丢。两个坑：pop 条件是 ≤ 不是 <（恰好等于就算过期）；惰性删除的比对逻辑别写反。O(q log q)。
写在最后
这三道题正好是微软 OA 的三个稳定方向：DP（打家劫舍变形是常客）、字符串贪心扫描、堆 + 哈希模拟。共同点是题面包装得花，破局靠认出模型——值域打家劫舍、段吞噬、惰性删除堆，认出来全是熟题。微软的数据卡边界卡得狠，写完一定拿题面例子手推一遍再交。
这三道我全在 InterviewShow 的题库里提前见过原型，做的时候基本是默写，这也是 20 分钟能出两题的真正原因——微软题池小、复现率高，刷对地方比刷得多重要。