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
# 注意：上面对同一行内 dp[j-1] 的引用需保证已更新为本行值
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