Microsoft OA，75 分鐘兩道題，全AC。T1 是經典二分答案，T2 是區間相交統計。以下是純思路複盤，不含程式碼。
考試概況
| 項目 | 詳情 |
|---|---|
| 時長 | 75 分鐘 |
| 題數 | 2 道 |
| 難度 | Medium |
| 職位 | Intern / New Grad SDE |
| 結果 | 全AC |
T1：合金最大生產量（二分答案）
題目核心
給定 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：區間重疊最大團隊
題目核心
給定每個員工的工作時間區間 [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]） - 有效區間數 = 右指針 - 左指針
複雜度分析
- 暴力：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 練習
| 題號 | 題目 | 對應考點 |
|---|---|---|
| 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 是我們的核心服務場景，高頻題庫覆蓋率極高。
立即加 WeChat：Coding0201
獲取：
- ✅ Microsoft OA 即時輔助（螢幕共享 + 即時打字提示）
- ✅ 真實題庫（覆蓋 80%+ 高頻題）
- ✅ 一對一模擬 OA + 詳細回饋
- ✅ VO 面試輔助（演算法 + 系統設計）
📱 WeChat：Coding0201 | 💬 Telegram：@OAVOProxy | 📧 [email protected]