这次分享的是两道 Microsoft OA 真题。考试通过 HackerRank 平台完成，限时约 75 分钟。这次遇到的两道 Coding 题分别考察了 Dynamic Programming 和二分查找，整体更偏向基础算法和对问题的转化能力。
下面我会把这两道题分别拆解，包括题目思路、解题方法以及具体考察的知识点，方便正在准备 Microsoft OA 的同学参考。
第一题：带问号的数字串，相邻不能相同
题意
题目给你一个只包含数字和 ? 的字符串，要求把每个 ? 替换成 0-9 的数字，并且任意相邻两个位置的数字不能相同。答案可能很大，最后要对 取模。
解题思路
这题本质是计数，暴力肯定超时，所以用动态规划来做。维护一个长度为 10 的数组，记录上一个位置填 0 到 9 时分别有多少种合法方案。每走到下一个字符，先把上一步所有方案数加起来得到总和。如果当前是问号，就对每个可能的数字用总和减去上一位填同一个数字的方案数，这样自然避开了相邻相同；如果当前是固定数字，就只保留那个数字对应的方案数。一路更新到结尾，最后把数组里所有值加起来再取模，就是答案，时间线性，空间几乎是常数，完全能过。
第二题：流水线服务扩容，最大化瓶颈吞吐量
题意
有 n 台服务串成流水线，整体吞吐量由最慢的那台决定。每台服务有初始吞吐量和每次扩容的成本，你有一个总预算，问在预算内能把整体吞吐量（也就是最慢那台的吞吐量）提到多高。
解题思路
这题很适合用二分查找。直接猜一个最终能达到的吞吐量 mid，然后计算每台服务要达到这个吞吐量需要扩几次、总共要花多少钱。把所有成本加起来，如果没有超过预算，说明这个吞吐量可以实现，就继续往更大的方向找；如果超出预算，就把目标调小。这样不断缩小范围，最后找到的就是预算内能够达到的最大吞吐量。每次检查都要遍历一遍服务，所以整体效率还是比较高的。
这两道 Microsoft OA 题目考察什么？
第一题考的是对动态规划状态转移的理解，尤其是「如何用前一个位置的信息推出当前位置」以及取模处理。本质是经典的字符串计数 DP，能看出你是否习惯用数组滚动记录状态，而不是一上来就想递归或暴力。
第二题则更偏思维层面，考察你能不能快速识别「答案具有单调性」并转化为二分。同时还要求你能正确写出可行性判断函数——把「每台服务要达到目标需要多少成本」算清楚。这种题在 OA 里很常见，目的是看你能不能在有限时间内把问题拆干净。
两道题合在一起，其实就是在测基础算法功底和问题转化能力，难度不算特别高，但细节容易翻车。
Microsoft OA 应该如何准备
准备 Microsoft OA，最有效的还是把常见题型练熟。优先刷字符串 DP、二分查找、前缀和/差分数组这几类，因为这几年反复出现。做题时别只追求 AC，多想一下「如果约束再紧一点、如果要返回具体方案而不是数量，该怎么改」。
时间控制也很重要。OA 通常两道题给 70-90 分钟，建议先花 5 分钟快速读完两题，先挑自己更有把握的那道写。写完一定要自己用几个边界例子测一下，别急着提交。
另外，HackerRank 的输入输出格式有时候会坑人，建议提前熟悉一下它的模板写法，避免因为读入问题浪费时间。平时可以每周固定做 2-3 套限时模拟，把心态和手感都练出来。真正考试时就会稳很多。
总结
这两道题分别对应动态规划和二分查找两个高频考点，思路本身并不复杂，关键在于把状态定义清楚、把检查函数写对。
准备 Microsoft 或者其他大厂的 OA时，建议把这类题当模板反复练，真正理解「为什么这样转移」「为什么能二分」，而不是死记代码。掌握了底层思路后，遇到变种也能快速反应过来。
如果你正在准备Microsoft 或其他大厂的 OA 和面试，除了刷题，也可以结合真实面经熟悉常见题型和考察方向。InterviewShow 整理了 Microsoft、Amazon、Google、Stripe、TikTok 等科技公司的面试资料，并提供一对一面试辅导，覆盖 Coding、System Design 和 Behavioral Interview。需要的话，可以直接联系我们，针对目标公司进行准备。
FAQ
Microsoft OA 一般考几道题？
这个要看具体岗位和当次 OA 的安排。这次分享的 Microsoft OA 是两道 Coding 题，考试时间大约 75 分钟。两道题的思路不太一样，一道是 Dynamic Programming，另一道是 Binary Search。
Microsoft OA 难吗？
这次遇到的题目不算特别难，真正做起来比较考验的是读题和找思路的速度。第一题需要想到用 DP 统计不同情况下的方案数，第二题则要发现吞吐量和预算之间存在单调关系，然后用二分去找答案。如果一开始没有想到对应的方向，还是比较容易花掉不少时间。
Microsoft OA 需要准备哪些算法？
可以先把 Array、String、Hash Table、Sorting、Binary Search、Dynamic Programming 这些基础题型过一遍。Microsoft OA 不一定会原样考某一道经典题，但题目经常会换一个场景，所以最好不要只背题，看到新题时能够判断它更接近哪一种解法。
Microsoft OA 应该怎么控制时间？
如果是两道题的 OA，建议拿到题目后先快速看一遍，不要在第一道题上卡太久。确定思路后尽快开始写，留一点时间检查边界情况和代码。尤其是第二题这种需要写 feasibility check 的题，代码写完后最好自己带几个简单的例子跑一下，比较容易发现边界问题。
Microsoft OA 做完题就可以了吗？
不建议只看最终能不能 AC。做完之后可以回头想一下，为什么这道题要用 DP，为什么另一道题可以二分答案。这样遇到换了题目背景的类似问题时，才比较容易重新找到思路。