Microsoft OA 真题解析：两道 Coding 真题与解题思路

这次分享的是两道 Microsoft OA 真题。两道 Coding 题分别考察了 Prefix Sum、二分查找以及 Graph、Dijkstra 等算法，涉及数组查询优化和城市间最低燃油成本计算。解题的关键在于利用题目给出的条件，找到合适的算法来提高计算效率。

下面会结合两道题的具体题意，分别分析解题思路、算法选择和复杂度，帮助正在准备 Microsoft OA 的同学梳理核心考点，理解这类问题的解题方法。

Question 1：购物预算与商品选择

Alex 在 Ozone Galleria Mall 购物，商场内有 $n$ 个购物隔间，每个隔间的商品价格固定，并且从左到右按照价格非递减的顺序排列。给定一个整数数组 prices，其中 prices[i] 表示第 i 个隔间的商品价格。

接下来需要处理 $q$ 个查询，每个查询包含两个整数：pos 表示 Alex 开始购物的位置，amount 表示他拥有的预算。Alex 从第 pos 个隔间开始，依次访问后面的所有隔间，直到第 $n$ 个隔间。每个隔间最多只能购买一件商品，且所有商品的总花费不能超过预算。对于每个查询，需要计算 Alex 最多可以买多少件商品，并返回对应的结果。

示例：

n = 5
prices = [3, 4, 5, 5, 7]
q = 3
queries = [[2, 10], [1, 24], [5, 5]]

对于第一个查询，pos = 2，amount = 10。Alex 可以从第 2 个隔间开始购物，选择价格为 4 和 5 的两件商品，总花费为 9；也可以选择两个价格均为 5 的商品，总花费为 10。因此，最多可以买 2 件商品。对于第二个查询，pos = 1，amount = 24。Alex 可以购买全部 5 个隔间的商品，总花费为 $3+4+5+5+7=24$，刚好用完预算，因此最多可以买 5 件商品。对于第三个查询，pos = 5，amount = 5。Alex 只能访问第 5 个隔间，但该隔间的商品价格为 7，超过了预算，因此无法购买商品，结果为 0。

预期输出：[2, 5, 0]

解题思路

1. 利用数组升序的特点

由于 prices 是非递减数组，如果想在预算范围内购买尽可能多的商品，就应该优先选择价格最低的商品，也就是从指定位置 pos 开始，优先购买后面价格较低的商品。因此，答案对应的是从 pos 开始的一段连续商品，而不需要枚举所有购买组合。

2. 预处理前缀和

为了快速计算商品总价，可以先对原数组 prices 计算前缀和，得到 sum 数组。其中，sum[i] 表示原数组前 i 个元素的总和。对于每个查询，起始下标为 s = pos - 1，需要考虑的范围是 prices[s ... n-1]。如果从这个位置开始购买 k 件商品，那么总花费可以通过前缀和快速计算：sum[s + k] - sum[s]这样就不需要每次查询时重新累加商品价格。

3. 使用二分查找确定答案

由于原数组的价格非递减，从 pos 开始的片段前缀和也具有单调递增的特点。因此，可以使用二分查找，在 0 到 n - s 的范围内寻找最大的 k，使得：sum[s + k] - sum[s] <= amount满足预算限制的最大 k，就是当前查询能够购买的最多商品数量。

复杂度分析： 前缀和预处理需要 (O(n)) 时间，每个查询通过二分查找需要 (O(\log n)) 时间。因此，总时间复杂度为 (O(n + q\log n))，空间复杂度为 (O(n))。相比每次查询都逐个累加商品价格的暴力方法，这种做法能够更高效地处理大量查询。

Question 2：城市间的最低燃油成本

Hackerland 是一个由 g_nodes 个城市组成的国家，城市编号从 1 到 g_nodes。这些城市通过 g_edges 条双向道路连接，第 i 条道路连接城市 g_from[i] 和 g_to[i]，行驶这条道路需要消耗 g_weight[i] 单位燃油。车辆的燃油容量没有限制，因此可以携带任意数量的燃油。每个城市的燃油单价可能不同，其中 arr[i] 表示第 i 个城市的燃油价格。Alex 可以在任何城市购买任意数量的燃油。

给定两个城市 A 和 B，其中 $1 \le A,B \le g\_nodes$1≤A,B≤g_nodes，请计算从城市 A 前往城市 B 所需的最低燃油总成本。如果两个城市之间不存在可行的行驶路线，则返回 -1。

示例

g_nodes = 5
g_from = [4, 5, 4, 1, 3, 4, 4]
g_to = [1, 3, 5, 5, 1, 2, 3]
g_weight = [1, 1, 8, 1, 3, 9, 5]
arr = [9, 11, 3, 2, 10]
A = 3
B = 2

其中，arr 表示各城市的燃油价格。每条道路的燃油消耗量由 g_weight 中对应的元素决定，所有道路均为双向道路。城市及其燃油价格的表示方式为 城市编号:燃油单价。目标是求出从城市 3 出发到达城市 2 的最低燃油成本。如果无法到达城市 2，则返回 -1。

解题思路

1. Dijkstra 变形使用 Dijkstra 算法，但 dist[] 不再记录最短距离，而是记录从起点到达每个城市的最低花费。
2. 确定加油策略当前位于城市 u，该城市的油价为 arr[u]。如果前往邻接城市 v 需要消耗 w 单位燃油，可以根据沿途油价安排加油：如果 v 的油价比 u 贵，可以在 u 多买一些油，尽量避免在更贵的城市加油。如果 v 的油价比 u 便宜，可以先在 u 购买刚好够到达 v 的燃油，再到 v 以更低的价格购买。
3. 使用优先队列将 (总花费, 当前城市) 作为状态放入优先队列，每次优先取出当前累计花费最小的状态。
4. 更新最小花费从城市 u 前往邻接城市 v，如果道路需要消耗 w 单位燃油，那么按照出发城市的油价计算，这段路的花费为 w * arr[u]。如果 dist[v] > dist[u] + w * arr[u]，就更新 dist[v]，并将新的状态加入优先队列。
5. 返回结果当目标城市 B 从优先队列中以当前最小花费取出时，直接返回 dist[B]。如果队列为空仍然无法到达 B，则返回 -1。

Microsoft Company Recruitment Process

Microsoft 的招聘流程通常从在线申请开始，经过简历筛选和面试评估，符合岗位要求的候选人可能收到 Offer。对于 Software Engineer（SDE）岗位，技术面试是重要的评估环节，但具体流程会根据岗位级别、团队和招聘项目有所不同。Microsoft 官方也说明，进入面试阶段后的安排取决于申请的具体职位。

Microsoft SDE 招聘流程

1. Online Application（在线申请）

候选人通过 Microsoft Careers 提交简历和申请信息。招聘团队会根据职位要求、候选人的技能和相关经历进行筛选，部分岗位可能安排初步沟通。

2. Online Assessment（在线测评）

部分 Software Engineer 岗位可能要求候选人完成 Online Assessment（OA），通过 Coding 题评估算法基础、问题分析和编程能力。具体是否安排 OA、使用什么平台以及考试时长，应以实际收到的招聘通知为准。

3. Technical Interview（技术面试）

技术面试可能包括 Coding、Problem Solving、System Design，以及与岗位相关的技术讨论。对于 SDE 候选人，除了写出正确的代码，面试官也会关注解题思路、代码质量、边界情况和测试能力。不同岗位和级别的技术考察重点可能有所不同。

4. Behavioral Interview（行为面试）

候选人可能需要结合过往项目或工作经历，说明自己如何解决问题、与团队合作、处理不同意见，以及在面对挑战时作出决策。回答时可以使用 STAR（Situation、Task、Action、Result）结构，清楚说明背景、个人行动和实际结果。

5. Hiring Decision and Offer（招聘决策与录用）

完成面试后，招聘团队会综合评估候选人与岗位的匹配程度，并由 Recruiter 沟通后续安排。如果获得录用，候选人将收到相关 Offer 文件及入职指引。

需要注意的是，上述步骤是帮助候选人理解招聘环节的参考框架，并不代表每位 Microsoft SDE 候选人都必须依次经历全部阶段。实际面试轮数、OA 安排和技术面试内容应以 Recruiter 的通知为准。

Microsoft OA 考点总结

这两道题分别考察了数组查询优化和图论中的最短路径问题。第一题需要利用数组价格非递减的特点，通过前缀和快速计算商品总价，再用二分查找确定预算内最多能购买的商品数量。第二题则需要结合不同城市的燃油价格，将道路的燃油消耗转换为行驶成本，再使用 Dijkstra 算法求出两座城市之间的最低花费。

从整体来看，这两道题都强调利用题目条件优化解法，而不是直接采用暴力遍历。备考时可以重点复习 Prefix Sum、Binary Search、Graph Traversal 和 Dijkstra 等常见算法。

如果你正在准备 Microsoft 或其他大厂的 OA 或面试，除了刷题，也可以结合真实面经熟悉常见题型和考察方向。InterviewShow 整理了 Microsoft、Amazon、Google、Stripe、TikTok 等科技公司的面试资料，并提供 OA 辅助和面试辅助，可以查看服务介绍，覆盖 Coding、System Design 和 BQ。需要的话，可以直接联系我们。

FAQ

What Is the Microsoft OA?

Microsoft OA（Online Assessment）是微软针对部分岗位设置的在线测评环节，主要考察候选人的 Coding 能力、算法基础和 Problem Solving 能力。对于 Software Engineer（SDE）岗位，题目可能涉及 Array、Binary Search、Dynamic Programming、Graph 等常见算法，具体题型和考试时长取决于岗位及招聘安排。

How Long Does Microsoft Take to Respond After an OA?

Microsoft 在 OA 结束后没有统一的反馈时间。部分候选人可能在几天内收到回复，也可能需要等待更长时间，具体取决于招聘团队的安排、测评结果和岗位进度。如果长时间没有收到消息，可以联系 Recruiter，了解当前的申请状态和后续流程。

Is a Microsoft Interview Tough?

Microsoft SDE 面试具有一定挑战性，尤其是对 Coding、算法分析和问题解决能力有较高要求的岗位。技术面试可能涉及 Data Structures、Algorithms、System Design 和 Behavioral Questions，具体考察内容会根据岗位级别和团队有所不同。建议提前练习常见算法题，熟悉复杂度分析，并训练自己清晰解释解题思路和测试边界情况的能力。