Microsoft的题基本在一个不大的池子里轮换，复现率相当高。今年秋招还是 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)。
写在最后
这三道题正好是Microsoft OA 的三个稳定方向：DP（打家劫舍变形是常客）、字符串贪心扫描、堆 + 哈希模拟。共同点是题面包装得花，破局靠认出模型——值域打家劫舍、段吞噬、惰性删除堆，认出来全是熟题。微软的数据卡边界卡得狠，写完一定拿题面例子手推一遍再交。
这三道我全在 InterviewShow 的题库里提前见过原型，做的时候基本是默写，这也是 20 分钟能出两题的真正原因——微软题池小、复现率高，刷对地方比刷得多重要。
Microsoft Coding Assessment FAQ
1. Microsoft Coding Assessment 一般考几道题？
Microsoft Coding Assessment 的题目数量和考试时长会根据岗位、招聘批次及考试平台有所不同。本文整理的 HackerRank 面经包含三道 Coding 真题，分别考察动态规划、字符串贪心和 Token 认证系统模拟。准备时建议以实际收到的 OA 邀请和考试说明为准。
2. Microsoft Coding Assessment 常考哪些算法？
Microsoft Coding Assessment 常见的备考方向包括 Dynamic Programming、字符串处理、双指针、Hash Map、Heap 和图算法等。本文的三道题分别对应值域打家劫舍变形、连续字符段扫描，以及使用最小堆和哈希表实现 Token 过期管理，重点在于识别题目背后的算法模型。
3. Microsoft HackerRank Coding Assessment 难吗？
难度取决于具体岗位和题目。本文涉及的题目不一定需要复杂的算法，但对边界条件和实现细节要求较高。例如，动态规划题需要正确处理数值之间的相邻关系，字符串题需要理解字符覆盖规则，Token 认证题则要注意过期时间恰好等于当前时间的情况。