最近做了 IMC 的 SWE OA，兩道程式題、120 分鐘，在 HackerRank 上完成，可以自選語言。整體難度中上，考的不是花俏技巧，而是演算法基本功、工程思維和高效實作。這篇復盤把兩道題的思路、Python 解法和複雜度都寫清楚，也順帶聊聊時間該怎麼分配。如果你也在排隊等 IMC 的 OA，希望這份筆記能幫你把節奏和心態調到位。
OA 環境與形式概覽
整場 OA 在 HackerRank 完成，語言不限，兩道題都會給若干可見範例和隱藏測試點，最終看通過率。題目描述偏工程化，邊界條件寫得比較克制，需要自己把角落情況想全。
| 項目 | 詳情 |
|---|---|
| 平台 | HackerRank（自選語言） |
| 形式 | 線上程式題，範例 + 隱藏測試點計分 |
| 總時長 | 120 分鐘 |
| 題量 | 2 道 |
| 難度 | 中上 |
| 考點 | 演算法基本功、工程思維、高效實作、邊界處理 |
時間管理建議
兩道題 120 分鐘，看似寬鬆，但第二題一旦想複雜了很容易超時。我的做法是：
- 開局先把兩道題都讀一遍，判斷哪道思路更清晰，就先做哪道，避免在難題上空耗。
- 第一題爭取 35–45 分鐘拿下，先寫出能過範例和主要測試點的版本，再回頭補邊界。
- 第二題先求正確、再談最佳化：先寫一個邏輯正確的樸素版本跑通範例，然後再最佳化空間、加剪枝、降複雜度。
- 最後留 10 分鐘做檢查：空輸入、極端規模、重複元素、整數溢位、變數初始化，這幾類問題最容易在隱藏測試點上翻車。
Problem 1：帶通行券的網格路徑計數
題目背景
給定一個由 0 和 1 組成的網格，機器人從左上角 (0, 0) 出發，只能向右或向下移動，目標是右下角。1 表示可通行，0 表示障礙，但機器人手裡有最多 k 張通行券，每張券可以讓它強行穿過一個障礙格（包括起點和終點格）。求所有合法路徑的數量，對 1e9+7 取模。
思路
這是網格路徑計數的加強版，多了一個「通行券」維度，很自然地想到三維 DP：
dp[i][j][t]表示到達(i, j)且累計用了 t 張通行券的路徑數。- 進入某個格子時，如果它是
1，不消耗券，狀態從dp[*][*][t]（上方 + 左方）轉移；如果它是0，進入時消耗一張券，狀態從dp[*][*][t-1]轉移。 - 起點要單獨初始化：起點是
1就設dp[0][0][0] = 1，起點是0就設dp[0][0][1] = 1（進入起點也算消耗一張券）。 - 最終答案是終點格在
t = 0..k上的求和。
把「進入格子消耗的券數」抽象成 cost（1 格為 0，0 格為 1），轉移就統一成 dp[i][j][t] = dp[i-1][j][t-cost] + dp[i][j-1][t-cost]。
Python 解法
from typing import List
MOD = 10**9 + 7
def count_paths(grid: List[List[int]], k: int) -> int:
"""統計從左上角到右下角、最多用 k 張通行券的路徑數，對 1e9+7 取模。
dp[i][j][t] = 到達 (i, j) 且累計使用 t 張通行券的路徑數。
格子為 1 時進入不消耗券；格子為 0 時進入消耗一張券。
"""
n, m = len(grid), len(grid[0])
# dp[i][j][t]，t 取值 0..k
dp = [[[0] * (k + 1) for _ in range(m)] for _ in range(n)]
# 初始化起點：起點是障礙則進入時就消耗一張券
start_cost = 0 if grid[0][0] == 1 else 1
if start_cost <= k:
dp[0][0][start_cost] = 1
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
continue
cost = 0 if grid[i][j] == 1 else 1
# 券數不夠消耗 cost 的狀態無意義，從 cost 開始列舉
for t in range(cost, k + 1):
total = 0
if i > 0:
total += dp[i - 1][j][t - cost] # 從上方來
if j > 0:
total += dp[i][j - 1][t - cost] # 從左方來
dp[i][j][t] = total % MOD
# 終點處對 t = 0..k 求和
return sum(dp[n - 1][m - 1][t] for t in range(k + 1)) % MOD
時間複雜度：O(n·m·k)，每個格子對每個券數各算一次。
空間複雜度：O(n·m·k)。因為第 i 列只依賴第 i-1 列，可以用滾動陣列把空間壓到 O(m·k)。
Dry run 演示
用一個 2×2 的小網格最能說明券的作用：grid = [[1, 0], [0, 1]]，k = 1。起點 (0,0) 是 1，所以 dp[0][0][0] = 1。
| 格子 | 類型 | cost | 轉移 | 結果 |
|---|---|---|---|---|
(0,1) |
0 |
1 | dp[0][1][1] = dp[0][0][0]（左） |
dp[0][1][1] = 1 |
(1,0) |
0 |
1 | dp[1][0][1] = dp[0][0][0]（上） |
dp[1][0][1] = 1 |
(1,1) |
1 |
0 | t=0: 上 0 + 左 0；t=1: 上 1 + 左 1 |
dp[1][1][0]=0, dp[1][1][1]=2 |
終點對 t = 0..1 求和 = 0 + 2 = 2。對應兩條路徑：先右後下（穿過障礙 (0,1)）、先下後右（穿過障礙 (1,0)），各用掉一張券。
主動補充要驗證的邊界：
- 起點或終點是障礙：靠
start_cost與終點求和統一涵蓋，無需特判。 - k = 0：退化成普通網格路徑，
0格完全不可通行。 - 超大網格：每一步轉移都取模，避免整數溢位（Python 雖是大整數，但取模能防結果膨脹、也符合題意）。
Problem 2：按容量加權的 LFU 快取
題目背景
實作一個按大小加權的 LFU 快取。每個條目有 key、value、size 三個屬性，所有條目的 size 之和不能超過總容量 capacity。要求支援兩個操作：
get(key)：命中就回傳value，同時把該條目的存取頻率 +1 並刷新近用順序；未命中回傳-1。put(key, value, size)：新增或更新。新條目初始頻率為 1；更新已有條目只改 value 和 size、不改頻率，但要刷新近用順序；若單個條目的size就超過總容量，直接忽略該操作。當空間不足時，淘汰頻率最低的條目，頻率相同則淘汰最久未使用的，直到騰出足夠空間。
思路
經典 LFU 的加權版，核心資料結構不變：
- 一個雜湊表
key -> Node，做 O(1) 定位。 - 每個頻率維護一個雙向鏈結串列，按近用順序排列，頭部最新、尾部最舊。
- 維護
min_freq（當前最低頻率）和total（當前佔用的容量）。
各操作要點：
get：把節點從原頻率串列取出，頻率 +1，插到新頻率串列頭部。put更新已有 key：只改value、size，頻率不變，但要把節點移到同頻率串列頭部刷新近用順序；size變化後按需淘汰其他條目騰空間。put新增 key：先按需淘汰騰出空間，再以頻率 1 插入。- 淘汰：從
min_freq串列尾部取出條目，同步更新雜湊表和total，直到空間足夠。
Python 解法
from collections import defaultdict
class Node:
"""快取節點，同時作為雙向鏈結串列節點。"""
__slots__ = ("key", "value", "size", "freq", "prev", "next")
def __init__(self, key=None, value=None, size=0):
self.key = key
self.value = value
self.size = size
self.freq = 1
self.prev = None
self.next = None
class DoublyLinkedList:
"""維護同一頻率下的節點，按近用順序排列：頭部最新，尾部最舊。"""
def __init__(self):
self.head = Node() # 哨兵頭
self.tail = Node() # 哨兵尾
self.head.next = self.tail
self.tail.prev = self.head
self.count = 0 # 串列內節點個數
def add_front(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
self.count += 1
def remove(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
self.count -= 1
def remove_last(self) -> Node:
node = self.tail.prev # 最久未使用
self.remove(node)
return node
def is_empty(self) -> bool:
return self.count == 0
class WeightedLFUCache:
"""按 size 加權的 LFU 快取，get / put 平均 O(1)。"""
def __init__(self, capacity: int):
self.capacity = capacity
self.total = 0 # 當前佔用的容量
self.min_freq = 0 # 當前最低頻率
self.nodes = {} # key -> Node
self.freqs = defaultdict(DoublyLinkedList) # freq -> 串列
def _bump(self, node: Node) -> None:
"""頻率 +1，並從舊頻率串列移到新頻率串列頭部。"""
old = node.freq
self.freqs[old].remove(node)
if self.freqs[old].is_empty() and old == self.min_freq:
self.min_freq += 1
node.freq += 1
self.freqs[node.freq].add_front(node)
def _evict_until(self, need: int) -> None:
"""騰出足夠空間容納 need：從最低頻串列尾部逐個淘汰。"""
while self.nodes and self.total + need > self.capacity:
while self.freqs[self.min_freq].is_empty():
self.min_freq += 1
victim = self.freqs[self.min_freq].remove_last()
del self.nodes[victim.key]
self.total -= victim.size
def get(self, key):
if key not in self.nodes:
return -1
node = self.nodes[key]
self._bump(node)
return node.value
def put(self, key, value, size: int) -> None:
# 單個條目就超過總容量，直接忽略
if size > self.capacity:
return
if key in self.nodes:
# 更新已有條目：頻率不變，只改 value / size 並刷新近用順序
node = self.nodes[key]
old_freq = node.freq
self.freqs[old_freq].remove(node)
self.total -= node.size
del self.nodes[key] # 暫時移出，避免淘汰到自己
self._evict_until(size)
node.value, node.size = value, size
self.freqs[old_freq].add_front(node)
self.nodes[key] = node
self.total += size
self.min_freq = min(self.min_freq, old_freq)
return
# 新增條目：先騰空間，再以頻率 1 插入
self._evict_until(size)
node = Node(key, value, size) # 新節點頻率為 1
self.freqs[1].add_front(node)
self.nodes[key] = node
self.total += size
self.min_freq = 1
時間複雜度：get 與 put 平均 O(1)（淘汰是攤還 O(1)）。
空間複雜度：O(快取中條目數)，用於雜湊表和各頻率串列。
Dry run 演示
設 capacity = 6，依序執行以下操作：
| 操作 | 結果 | total | 快取狀態（頻率） |
|---|---|---|---|
put(a, 1, 3) |
— | 3 | a@1 |
put(b, 2, 3) |
— | 6 | a@1, b@1 |
get(a) |
回傳 1 |
6 | b@1, a@2 |
put(c, 3, 3) |
空間不足，淘汰 b | 6 | a@2, c@1 |
get(b) |
回傳 -1 |
6 | a@2, c@1 |
關鍵點：get(a) 後 a 頻率升到 2；插入 c 需要 3 的空間但已滿，min_freq = 1 且頻率 1 的串列裡只有 b，於是淘汰 b（而不是頻率更高的 a）。這正是「先按頻率、頻率相同再按最久未使用」的淘汰規則。
主動補充要驗證的邊界：
- 單條目超容量：
put(x, v, 100)而capacity = 6，直接忽略，不影響已有資料。 - 更新導致體積變大：更新已有 key 且新
size更大時，會淘汰其他條目騰空間，但不會淘汰自己。 - 頻率相同的平局：靠雙向串列的近用順序，尾部即最久未使用，天然處理平局。
備考策略
IMC 的 OA 不玩偏門，考的是扎實的基本功 + 乾淨的工程實作。兩道題分別落在兩個高頻方向：
- 動態規劃：網格路徑、背包、區間 DP、狀態壓縮要練到能快速定義狀態和轉移。多加一維（如通行券、剩餘次數）是常見變體，關鍵是想清楚「進入某狀態時消耗了什麼」。
- 資料結構設計：LRU / LFU、跳表、並查集、堆積這類題考的是能否把雜湊表和串列 / 堆積組合出 O(1) 或 O(log n) 的操作。平時就按「先寫正確樸素版，再最佳化到目標複雜度」的順序練。
另外，邊界處理和整數溢位是隱藏測試點的常客，寫完一定要用具體資料 dry run 一遍。
FAQ
Q1：IMC 的 SWE OA 有幾道題、多長時間？
兩道程式題，總時長 120 分鐘，在 HackerRank 上完成，可以自選語言。難度中上，考演算法基本功、工程思維和高效實作。
Q2：120 分鐘兩道題，節奏怎麼安排？
先把兩道題都讀一遍，挑思路更清晰的先做。第一題爭取 35–45 分鐘拿下能過範例和主測試點的版本；第二題先寫正確的樸素版，再最佳化空間和複雜度；最後留 10 分鐘檢查邊界。
Q3：帶通行券的網格路徑為什麼要用三維 DP？
因為除了位置，還要記錄「已用幾張券」這個額外狀態。dp[i][j][t] 把位置和券數一起編碼，進入 0 格時消耗一張券（從 t-1 轉移），進入 1 格不消耗（從 t 轉移），最後對 t = 0..k 求和即可。空間可用滾動陣列壓到 O(m·k)。
Q4：加權 LFU 和普通 LFU 的區別在哪？
普通 LFU 按條目個數限制容量，加權版按每個條目的 size 之和限制。淘汰時可能要連續踢出多個低頻條目才騰得出空間，因此淘汰邏輯寫成「迴圈從 min_freq 尾部淘汰，直到空間足夠」。
Q5：LFU 裡更新已有 key 會不會改變頻率？
不會。更新只改 value 和 size 並刷新近用順序，頻率保持不變。實作上要注意：size 變大時可能需要淘汰其他條目，為避免誤淘汰自己，可以先把該節點暫時移出對映，騰完空間再放回原頻率串列頭部。
Q6：最後 10 分鐘檢查最該看哪些點？
空輸入、極端規模、重複元素、整數溢位、變數初始化。這幾類問題最容易在隱藏測試點上翻車，用具體資料走一遍最穩。
正在準備 IMC 的 SWE OA？ 我們熟悉 HackerRank 的計分方式和這類中上難度題的踩坑點，能陪你把 DP 和資料結構設計的高頻題型打磨到位。
立即加入微信 Coding0201，取得一對一客製備考方案。
聯絡方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy