微軟面試題 ｜ 微軟 26 NG OA ｜12 月最新 Hard 題完整覆盤

今年 12 月的微软 26NG OA ，依舊是 HackerRank 平臺的兩道程式設計題。整體風格：medium-hard、考點扎實、細節決定生死。
我這次也是順順利利一次 AC，趁熱把題目 & 思路一起分享，希望你們也能一次過。

微軟 2026 NG OA 真題（12 月最新）

Problem 1 — Discounted Prices

You are given an array prices where prices[i] is the original price of the i-th item. For each item i, its selling price is prices[i] - prices[j], where j is the index of the first item to the right of i such that prices[j] <= prices[i].
If there is no such j, the item is sold at its original price.
Return:

• the total sum of all selling prices
• the list of indices sold at original price (0-based)

右側第一個 <= 的折扣問題（單調棧經典變體）

題目核心就是找：
每個元素右邊，第一個 <= 它的值。

這是典型的「下一更小或等於元素」問題，用 單調遞增棧 from right to left 一次解決。

核心思路

• 從右往左掃價格；
• 用一個 從底到頂遞增 的棧，存已經處理過的價格 index；
• 每次遇到一個新價格，把所有 嚴格大於它 的棧頂彈掉，因為它們不可能成為這個商品的折扣；
• 最終棧頂如果是 <= 它的，就是它的折扣；如果棧空就沒有折扣；
• 順手累加總價，記錄無折扣下標；
• 最後輸出總價 + 原價出售的 index 列表。

時間複雜度

O(n)，每個元素最多進棧 / 出棧一次。

易錯點

• 注意是 <=，不是 <。
• 從右往左處理，更方便維護單調結構。
• 無折扣下標按題目要求處理排序即可（面試官一般不卡，但寫時要說清楚）。

Problem 2 — Prefix Permutation Segment Check

Given a permutation p of 1..n, for every k from 1 to n, determine whether there exists a contiguous subarray that forms a permutation of 1..k.
Output a binary string s of length n where s[k-1] = '1' if such a segment exists.

Permutation Prefix 判斷（字首視窗 min/max）

給定一個排列 p，問每個 k 是否存在一段連續 subarray，是 1..k 的排列。

關鍵觀察

如果 1..k 這一堆數字在整個陣列中的位置是：

最小位置 = L
最大位置 = R
且 R – L + 1 == k

那麼它們正好佔滿了一個視窗，就是一個合法 segment。

演算法

• 先記錄每個數字的位置 pos[x]；
• 遍歷 k = 1..n：
  • 更新當前的 cur_min, cur_max（就是字首數字出現的最早/最晚位置）；
  • 如果 cur_max - cur_min + 1 == k，則輸出 ‘1’，否則 ‘0’。

時間複雜度

O(n)

易錯點

• pos 陣列必須是 0-based，一致性別搞錯
• k=1 的時候 min=max=pos[1]，一定是 ‘1’

微軟 OA 的兩道題有多“微軟味”？

微軟 OA 風格一直比較穩定：

• 套路並不刁鑽，但非常注重“程式碼質量 + 複雜度 + 邊界處理”。
• 當場寫程式碼通常沒太多時間 debug，所以 O(n) 方法要寫得非常熟練。
• 第二題屬於微軟常見的 permutation reasoning 類問題，很考邏輯嚴謹度。

如果你平時訓練不夠，這類題會覺得“腦子想到了但寫不順”；但只要做對方向，程式碼都不復雜。

ProgramHelp 微軟 2026 NG OA 專項助攻

今年微軟 2026 NG 的 OA 明顯更“卷”，Hackerrank 兩題雖然不算超綱，但邏輯細、坑點多、時間緊，這也是很多同學掉點的原因。我們這邊已經積累了多批次學員的真場景回放，包括 12 月最新版本的題型變化、常見卡點、最容易誤判的邊界情況。
如果你想更穩，我們可以提供：

• 實時語音助攻：做題過程中給你方向提醒、邊界提示，不會替你操作，但能讓你避免大多數陷阱。
• 0 痕跡遠端聯機輔導：全程安全，不觸發平臺檢測，用的是我們穩定驗證過的技術方案。