IMC 的 SWE OA 幫大家跑了一遍，題量不大，但難度在線，這裡總結一份給準備中的同學做參考。一共 2 道 coding，120 分鐘，HackerRank 自選語言，難度中等偏上，主要考察演算法基礎、工程思維以及高效實作能力。需要 OA輔助 或 OA代面 的同學，也可以照著這份複盤對齊節奏。
OA 概覽與時間分配
| 維度 | 詳情 |
|---|---|
| 平台 | HackerRank，自選語言 |
| 時長 | 120 分鐘 |
| 題量 | 2 道 coding |
| 難度 | 中等偏上 |
| 考察 | 演算法基礎、工程思維、高效實作 |
兩道題共 120 分鐘，關鍵是避免前半小時在第一題裡繞得太久，導致第二題沒有留下讀題和補邊界的時間。建議按這個節奏推進：
- 先完整讀兩題，判斷哪題狀態更清晰。
- 第一題爭取在 35 到 45 分鐘內寫出可過範例和主測試的版本。
- 第二題優先寫出正確狀態，再處理壓縮空間、剪枝或複雜度最佳化。
- 最後預留 10 分鐘，檢查空輸入、極值、重複元素、整數溢位與初始化。
Q1：帶通行券的網格路徑計數
題意
給定一個由 0 和 1 組成的網格，機器人從左上角 (0,0) 出發，只能向右或向下移動，目標是到達右下角。1 表示可以正常通過，0 表示障礙，但機器人最多可以使用 k 次通行券，每次通過一個障礙消耗一張，包括起點和終點。要求計算所有合法路徑的數量，並對 10^9 + 7 取模。
思路
使用三維動態規劃，定義 dp[i][j][t] 表示到達位置 (i,j) 且已經使用 t 張通行券的路徑數量：
- 當前位置為
1時，狀態可以直接從上方和左側的dp[*][*][t]轉移。 - 當前位置為
0時需要消耗一張通行券，因此從dp[*][*][t-1]轉移。 - 初始化起點時，根據起點是否為障礙設定
dp[0][0][0]或dp[0][0][1]。
最後累加終點使用 0 到 k 張通行券的所有狀態。時間複雜度 O(nmk)，空間複雜度 O(nmk)，也可以用滾動陣列最佳化到 O(mk)。
Python 實作
MOD = 10**9 + 7
def count_paths(grid, k):
"""grid: 0/1 二維網格；k: 通行券上限（障礙與起點終點都算消耗）。
返回從左上到右下、向右/向下移動的合法路徑數 % 1e9+7。"""
n, m = len(grid), len(grid[0])
# dp[j][t] 表示當前列到達行 j、已用 t 張券的路徑數（滾動陣列）
dp = [[0] * (k + 1) for _ in range(m)]
start_cost = 0 if grid[0][0] == 1 else 1
if start_cost <= k:
dp[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 # 障礙需消耗一張券
ndp = [0] * (k + 1)
for t in range(cost, k + 1):
total = 0
if j > 0:
total += dp[j - 1][t - cost] # 從左側來（已是本列）
if i > 0:
total += dp[j][t - cost] # 從上方來（dp[j] 仍是上一列）
ndp[t] = total % MOD
dp[j] = ndp
return sum(dp[m - 1]) % MOD
需要留意滾動陣列裡「左側」與「上方」引用的時序：處理到 (i,j) 時，dp[j-1] 應已是本列更新後的值，dp[j] 仍是上一列的值。若擔心時序繞暈，考場上直接用完整三維陣列 dp[i][j][t] 寫最穩妥，AC 後再壓空間。
時間複雜度：O(nmk)。空間複雜度：滾動陣列 O(mk)，完整版 O(nmk)。
Q2：按容量限制的加權 LFU 快取
題意
實作一個按容量大小限制的加權 LFU 快取。每條資料包含 key、value、size，所有資料的 size 總和不能超過 capacity：
GET key：鍵存在時返回對應值，同時將存取頻率加一並更新最近存取順序；不存在則返回-1。PUT key value size：新增或更新資料。新資料的初始頻率為 1；更新已有資料時只修改值和大小，不改變頻率，但需要更新最近使用順序；若單條資料的size大於總容量則忽略操作。- 空間不足時，優先淘汰存取頻率最低的資料，頻率相同則淘汰最久未使用的資料，直到容量足夠。
思路
用一個 HashMap 保存 key 到快取節點的映射，再按存取頻率維護多組雙向鏈結串列，每條串列內部按最近使用順序排列，同時記錄 min_freq 和目前總大小：
GET時把節點從原頻率串列移除，將頻率加一後放入新串列頭部。PUT更新已有資料時調整總大小並刷新其串列位置；新增資料則以頻率 1 插入。- 容量超限時，從
min_freq對應串列尾部不斷刪除最久未使用的節點，並同步更新映射和總大小。
借助雜湊表與雙向鏈結串列，單次存取、更新和淘汰都可以做到平均 O(1)。這裡用 Python 的 OrderedDict 按頻率分桶，天然維護每個頻率桶內的 LRU 順序，程式碼更短且等價於手寫雙向鏈結串列。
Python 實作
from collections import defaultdict, OrderedDict
class WeightedLFU:
def __init__(self, capacity):
self.capacity = capacity
self.size_used = 0
self.node = {} # key -> [value, size, freq]
self.freq = defaultdict(OrderedDict) # freq -> OrderedDict[key]，頭部最久未用
self.min_freq = 0
def _remove_from_bucket(self, key, f):
"""把 key 從頻率桶 f 摘出，桶空則清理並按需上移 min_freq。"""
del self.freq[f][key]
if not self.freq[f]:
del self.freq[f]
if self.min_freq == f:
self.min_freq = f + 1 # 該桶已空，最低頻率上移
def _bump(self, key):
"""存取命中：把 key 從頻率 f 桶移到 f+1 桶尾部（最近使用）。"""
item = self.node[key]
f = item[2]
self._remove_from_bucket(key, f)
item[2] = f + 1
self.freq[f + 1][key] = None # 尾部 = 最近使用
def get(self, key):
if key not in self.node:
return -1
self._bump(key)
return self.node[key][0]
def _evict(self, need):
"""淘汰直到能容納 need：取 min_freq 桶頭部（最久未用）刪除。"""
while self.size_used + need > self.capacity and self.node:
bucket = self.freq[self.min_freq]
old_key, _ = bucket.popitem(last=False) # 頭部 = 最久未使用
self.size_used -= self.node[old_key][1]
del self.node[old_key]
if not bucket:
del self.freq[self.min_freq]
# 下一輪若還需淘汰，會從新的 min_freq 桶繼續
def put(self, key, value, size):
if size > self.capacity:
return # 單條超容量，忽略
if key in self.node: # 更新：值和大小變，頻率不變，刷新順序
item = self.node[key]
f = item[2]
self._remove_from_bucket(key, f) # 先摘出，避免被自身淘汰
self.size_used += size - item[1]
item[0], item[1] = value, size
self._evict(0) # 變大後可能超容，先騰空間
self.freq[f][key] = None # 放回原頻率桶尾部（最近使用）
if f < self.min_freq or not self.freq.get(self.min_freq):
self.min_freq = min(self.freq) if self.freq else f
return
self._evict(size) # 新增：騰出空間
self.node[key] = [value, size, 1]
self.freq[1][key] = None
self.size_used += size
self.min_freq = 1
更新已有鍵時的關鍵點：先把舊節點從其頻率桶摘出再觸發淘汰，避免剛更新的鍵被誤刪；淘汰完再放回原頻率桶（頻率不變）並刷新為最近使用，同時按剩餘的最小鍵修正 min_freq。
複雜度：get / put 均攤 O(1)（雜湊查找 + 頻率桶內 OrderedDict 的頭尾操作都是 O(1)）；淘汰單個節點 O(1)，修正 min_freq 用 min(self.freq) 在桶數很少時可視為常數。
備考策略
- 時間分配是第一生產力：兩題各留出讀題和補邊界的時間，別在 Q1 死磕到沒時間碰 Q2。
- DP 先求對再壓空間：Q1 這類計數 DP，考場先用完整三維陣列 AC，確認無誤再考慮滾動陣列，別一上來就壓空間把自己繞暈。
- LFU 建模抓兩把鑰匙：雜湊表做 O(1) 定位、頻率分桶 + 桶內 LRU 做淘汰，
min_freq的維護和「更新不改頻率」是最容易踩的兩個坑。 - 邊界清單：空輸入、極值、重複 key、整數溢位（記得取模）、單條 size 超容量——最後 10 分鐘逐條過。
FAQ
Q1：IMC 的 SWE OA 難度如何？和 LeetCode 相比是什麼水平？
兩道題、120 分鐘，難度中等偏上。演算法本身不算最難那檔，但更看重工程實作的完整度和邊界處理——DP 計數要把通行券消耗和取模處理乾淨，LFU 要把頻率桶、LRU 和容量淘汰的狀態維護對，比純 LeetCode 中等題更考細緻。
Q2：IMC SWE OA 用什麼平台、多長時間、幾道題？
HackerRank 平台，自選語言，120 分鐘，2 道 coding。時間相對寬裕，但兩題都需要一定的建模和邊界處理時間，節奏管理很重要。
Q3：Q1 的通行券路徑計數必須用三維 DP 嗎？
是的，因為「已用幾張券」是一個必須記錄的狀態維度。dp[i][j][t] 三維最直觀；AC 後可用滾動陣列把列維度壓掉，降到 O(mk) 空間。注意障礙、起點、終點都算消耗券。
Q4：加權 LFU 和普通 LFU 有什麼區別？
普通 LFU 按條數淘汰，加權 LFU 按每條資料的 size 累加，總和不能超過 capacity，所以一次 PUT 可能要淘汰多條才能騰出空間。此外「更新已有鍵不改變頻率、單條 size 超容量直接忽略」是加權版本的兩個特有規則。
Q5：如何準備 IMC 這類偏工程實作的 OA？
重點練兩類題：一是帶額外狀態維度的 DP（如本題的通行券），二是 LRU/LFU 這類需要雜湊表 + 鏈結串列組合的系統模擬題。練習時強制自己先寫正確狀態再最佳化，並養成最後過一遍邊界清單的習慣。
正在準備 IMC 或其他量化 / 交易類公司的 SWE OA？ 我們熟悉 HackerRank 自選語言、兩題 120 分鐘這類節奏，能陪你把帶狀態維度的 DP、LFU/LRU 系統模擬題的建模和邊界一次打磨到位，提供全程 OA輔助 與 OA代面 支援。
立即加入微信 Coding0201，取得一對一客製備考方案。
聯絡方式
- 微信：Coding0201
- Email：[email protected]
- Telegram：@OAVOProxy