最近做了 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