Microsoft OA，75 分钟两道题，全AC。T1 是经典二分答案，T2 是区间相交统计。以下是纯思路复盘，不含代码。
考试概况
| 项目 | 详情 |
|---|---|
| 时长 | 75 分钟 |
| 题数 | 2 道 |
| 难度 | Medium |
| 岗位 | Intern / New Grad SDE |
| 结果 | 全AC |
T1：合金最大生产量（Alloy Production Binary Search）
题目核心
给定 n 种金属，每种金属有：
composition[i]：生产 1 单位合金所需该金属的数量stock[i]：当前库存cost[i]：购买该金属的单价
预算为 budget，求最多能生产多少单位合金。
解题思路
关键观察：生产数量 x 越大，所需总成本单调递增。这正是二分答案的适用条件。
二分答案框架：
- 二分范围：左边 0，右边设足够大的上界（如 10^9，或根据预算和最小单价估算）
- 对每个候选答案
x，执行check(x)判断是否可行
check(x) 校验逻辑：
- 对每种金属
i，计算需要的总量：total = x * composition[i] - 若
stock[i] ≥ total，库存足够，无需购买 - 否则需购买
(total - stock[i])单位，花费(total - stock[i]) * cost[i] - 累加所有金属的购买成本，判断是否
≤ budget
二分结果：找到最大的满足 check(x) 的 x。
复杂度分析
- 时间复杂度：O(n log C)，C 为二分上界，n 为金属种数
- 空间复杂度：O(1)
关键洞察
单调性是二分的前提：生产量越多，成本越高，这一单调性保证了二分的正确性。check(x) 是一次线性扫描，整体复杂度极低。注意二分上界要设得够大——可以用 (budget / min_cost + max_stock) 来估算安全上界。
T2：区间重叠最大团队（Max Team with Center Employee）
题目核心
给定每个员工的工作时间区间 [startTime[i], endTime[i]]，两个员工若区间有重叠则可以互动。
要求找到一个团队，使得存在一个**「中心员工」，他能与团队内所有人都有时间重叠。求最大团队人数**。
解题思路
问题等价转化：找一个员工 i，使得与 i 的区间相交的员工数最多（含 i 自身）。
区间相交判断：两个区间 [s1, e1] 和 [s2, e2] 相交，当且仅当：
max(s1, s2) ≤ min(e1, e2)
等价于：s2 ≤ e1 且 e2 ≥ s1。
暴力做法：枚举每个员工 i 作为中心，统计满足相交条件的员工数，取最大值。O(n²)，数据量小时可过。
优化做法（O(n log n)）：
- 将所有区间按
start排序 - 枚举每个区间
i作为中心：- 满足
start[j] ≤ end[i]的区间：可用二分找右边界 - 同时需要
end[j] ≥ start[i]：已排序后，从左往右用双指针维护左边界（剔除结束时间过早的区间）
- 满足
- 有效区间数 = 右指针位置 - 左指针位置
扫描线思想：将 start 和 end 拆成事件点，但本题不是求全局最大重叠数，而是「某个区间作为中心时覆盖的区间数」，直接双指针更简洁。
复杂度分析
- 暴力：O(n²)
- 优化：O(n log n)，排序 + 双指针线性扫描
- 空间复杂度：O(n)
关键洞察
「中心员工能与所有人重叠」等价于「找覆盖其他区间数最多的区间」。排序后双指针是解决「某区间与多少其他区间相交」的标准模式。
两题核心思路对比
| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| T1 合金生产 | 二分答案 + 线性校验 | O(n log C) | O(1) |
| T2 最大团队 | 排序 + 双指针区间相交统计 | O(n log n) | O(n) |
常见思维误区
| 题目 | 误区 | 正确方向 |
|---|---|---|
| T1 | 直接枚举生产数量 | 认识到单调性，用二分答案 |
| T1 | 二分上界设太小导致答案截断 | 用预算估算安全上界 |
| T2 | 用 BFS/图连通分量求解 | 本题不是连通，而是「某点覆盖最多」 |
| T2 | 暴力 O(n²) 超时 | 排序后双指针降到 O(n log n) |
Microsoft OA 应试策略
Microsoft OA 特点
- 时长：75 分钟，题目数量少但质量高
- 题目风格：二分、区间、贪心，考察算法思维清晰度
- 核心考点：能否识别问题结构（单调性、区间性质）并选择正确算法框架
- 数据规模较大，O(n²) 通常无法通过
临场策略
- 看到「最多/最少满足条件」类问题：先想单调性，单调则二分答案
- 看到区间重叠/覆盖类问题：先排序，再考虑双指针或扫描线
- T1 二分上界要想清楚，避免截断答案
- T2 相交条件
max(s1,s2) ≤ min(e1,e2)要记牢，等价于两个不等式 - 写完跑样例，边界情况（单个员工、全部相交、无相交）都测一下
相关 LeetCode 练习
| 题号 | 题目 | 对应 Microsoft OA 考点 |
|---|---|---|
| 2861 | Maximum Number of Alloys | T1 完全相同题型 |
| 875 | Koko Eating Bananas | T1 二分答案经典题 |
| 2779 | Maximum Beauty of an Array | T2 区间覆盖计数 |
| 56 | Merge Intervals | T2 区间排序处理 |
🚀 需要 Microsoft OA 辅助？
oavoservice 专注北美大厂 OA/VO 全程辅助，Microsoft OA 是我们的核心服务场景，高频题库覆盖率极高。
立即添加微信：Coding0201
获取：
- ✅ Microsoft OA 实时辅助（屏幕共享 + 实时打字提示）
- ✅ 真实题库（覆盖 80%+ 高频题）
- ✅ 一对一模拟 OA + 详细反馈
- ✅ VO 面试辅助（算法 + 系统设计）
📱 微信：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]