新建题目 Warehouse Inventory：区域汇总
题目 amazon-ood-warehouse-inventory · 新建（rev 1） · · 2026-10-25 20:23
body
@@ -1 +1,550 @@ -null +## TL;DR + +- **题**：Amazon SDE II 电话面试的 OOD 题。先写两个类，记每个仓库（warehouse）里每种商品有几件，支持增、删、查。之后面试官一条条加需求：按仓库和区域（region）查件数，在某个区域里从候选商品中找库存最少的那种。再往后的需求帖子没写（题目一节）。 +- **每一步先问**：「删」是减数量还是删整条，仓库属于哪个区域、对应关系从哪来，第二步是一次查询还是两种查询，并列、候选为空、库存为 0 怎么算（题目一节的表）。 +- **开场就建一个入口类** `InventorySystem`，数据放在它的几个字典里，后面加需求只是加字典、加方法（思路第 1 节）。 +- **三个字典**：`_region_of` 记仓库属于哪个区域，`_stock` 记每个仓库每种商品的 `Item`，`_region_total` 记每个区域每种商品的总件数（思路第 2 节）。 +- **区域总数单独存一份**：按区域查变成 O(1)，第三步变成 O(候选数)。代价是同一份库存记了两遍，每次改库存两份都要改（思路第 2、3 节）。 +- **两份保持一致**：改库存只经过私有方法 `_change`，检查都在第一次修改之前。漏改 `delete_item` 的打补丁版本，随机对拍 500 组错 122 组（思路第 4 节）。 +- **Follow-up**（推测）：调货，仓库换区域，不给候选找最少（堆加懒删除），多线程下检查和修改放进同一把锁。 + +## 题目 + +### 帖子里给了什么 + +面试官开场只让写两个类（class），背景是亚马逊的仓库管理系统：有很多仓库，要记下每个仓库里每一类商品（item）有多少件。楼主没写这两个类叫什么，帖子里只出现了 `Item` 这个名字。之后的需求是面试官一条条贴出来的，帖子按顺序记了这几步： + +1. 对 Item 做增加、删除、查询三种操作。方法名、参数、返回值帖子都没写。「删除」是把这条记录整个删掉，还是把数量减掉一部分，帖子也没说。 +2. 查某个仓库和区域（region）里某一种商品有多少。帖子只有这一句，没说区域和仓库是什么关系、这个关系从哪里给进来，也没说这是一次查询同时按两个条件过滤，还是按仓库查、按区域查两种查询。 +3. 给一组候选商品，在某个区域里找出库存最少的那一种。帖子在同一句里把候选叫 item、把结果叫 type，没交代两者是不是一回事。并列怎么办、候选为空怎么办、库存为 0 的算不算，帖子都没写。 +4. 后面面试官还加了需求，楼主时间不够没做，帖子没写是什么。 + +完整的题面没有人记下来。下面的接口和规则是本页为了写出能跑的代码设定的，**帖子里没有**。 + +### 本页设定的接口 + +两个类：`Item` 是某个仓库里一种商品的库存记录，有 `type`（种类名）和 `quantity`（件数）两个字段。`InventorySystem` 是整个系统的入口，所有操作都通过它调用，方法如下： + +| 方法 | 做什么 | 返回 | +| --- | --- | --- | +| `add_warehouse(warehouse, region)` | 登记仓库和它所属的区域（只属于一个），重复登记抛 `ValueError` | 无 | +| `add_item(warehouse, item_type, quantity)` | 加 `quantity` 件 | 无 | +| `remove_item(warehouse, item_type, quantity)` | 减 `quantity` 件，不够时什么都不改 | 够就是 `True`，不够是 `False` | +| `delete_item(warehouse, item_type)` | 整条删掉这条记录 | 原来有就是 `True`，没有是 `False` | +| `get_count(warehouse, item_type)` | 查这个仓库的件数 | 件数，没有记录是 0 | +| `get_region_count(region, item_type)` | 查这个区域所有仓库的总件数 | 件数，没有是 0 | +| `least_stocked(region, candidates)` | 在候选种类里找这个区域总件数最少的 | 种类名，候选为空时是 `None` | + +另外几条规则： + +- 仓库要先登记。对没登记的仓库调增、减、删、`get_count`，抛 `KeyError`。区域只能通过登记仓库出现，没有仓库的区域查什么都是 0。 +- `quantity` 必须是正整数（`int` 且大于 0），否则抛 `ValueError`。 +- `least_stocked` 里，区域里一件都没有的种类（包括没出现过的名字）按 0 比较，并列时返回名字按字符串比较最小的。 + +站方 AI 在帖子页面上也补过一份题面，写明是为了做成练习题补的约定。它把第二步拆成按仓库查、按区域查两个方法，库存不够时 remove 返回 false 且不改，并列取字典序最小，候选为空返回 null。本页和它大体一致，多了 `delete_item` 和「没登记的仓库抛异常」（它设定仓库保证已登记）。两份都是设定，面试时以面试官说的为准。 + +### 一个具体例子 + +仓库 w1、w2 在区域 east，w3 在区域 west，一开始都是空的。表里第 1、2、4、5、6 行取自站方 AI 的示例，其余几行是本页加的： + +| 操作 | 返回 | 说明 | +| --- | --- | --- | +| `add_item("w1", "book", 5)` | 无 | | +| `add_item("w2", "book", 3)` | 无 | | +| `add_item("w3", "pen", 4)` | 无 | | +| `get_count("w1", "book")` | 5 | | +| `get_region_count("east", "book")` | 8 | w1 的 5 本加 w2 的 3 本 | +| `least_stocked("east", ["book", "pen"])` | `"pen"` | east 里 pen 是 0，book 是 8 | +| `remove_item("w1", "book", 6)` | `False` | w1 只有 5 本，什么都不改 | +| `remove_item("w1", "book", 5)` | `True` | w1 的 book 变成 0，这条记录删掉 | +| `get_region_count("east", "book")` | 3 | 只剩 w2 的 3 本 | +| `least_stocked("west", ["pen", "book"])` | `"book"` | west 里 book 是 0，pen 是 4 | +| `least_stocked("east", [])` | `None` | 候选为空 | + +### 开写之前要问清楚的 + +需求是一步步给的，每一步贴出来时先问这一步的。下面几处面试官不会主动说，表里是本页的设定，以及答案不同时代码怎么改： + +| 什么时候问 | 要问的 | 本页的设定 | 答案不同时怎么改 | +| --- | --- | --- | --- | +| 开场 | 后面还会加需求吗？大概会按什么维度查？ | 帖子里后面确实一条条加了 | 答案决定怎么起步：会加，就先建一个所有操作都经过的入口类（思路第 1 节） | +| 第一步 | 「删」是减掉一部分数量，还是把整条记录删掉？ | 两种都做：`remove_item` 减数量，`delete_item` 删整条 | 只要一种，就删掉另一个方法 | +| 第一步 | 要减的比库存多怎么办？ | 返回 `False`，什么都不改 | 要求报错就改成 `raise ValueError`。要求有多少减多少，就截到现有件数，返回实际减掉的件数 | +| 第一步 | 仓库要先登记吗？ | 要先 `add_warehouse`，否则抛 `KeyError` | 允许第一次用到时自动建，第二步之后建仓库时得知道区域，`add_item` 要多一个 `region` 参数 | +| 第二步 | 一个仓库是不是只属于一个区域？对应关系从哪来？ | 只属于一个，在 `add_warehouse` 时给 | 属于多个区域，就让 `_region_of` 存一个列表，`_change` 对每个区域都改一次总数。区域如果是仓库里的分区（一片货架），库存的键就变成（仓库，分区，种类） | +| 第二步 | 是一次查询同时给仓库和区域，还是按仓库查、按区域查两种？ | 两种查询 | 一个仓库只属于一个区域的前提下，一次查询带两个条件的答案就是 `get_count(w, t)` 或 0（仓库不在这个区域），区域条件几乎多余，所以本页按两种查询理解【推断】 | +| 第三步 | 候选给的是商品种类，还是具体的商品？ | 种类，候选和结果是同一种东西 | 给的是具体商品，比如库存单位（stock keeping unit，SKU，每个规格一个编号，几个 SKU 属于同一种类），就多存一个「商品到种类」的字典，先把候选换成种类 | +| 第三步 | 几个并列最少返回哪个？候选为空呢？库存为 0 的种类算不算？没见过的名字呢？ | 名字最小的那个，空时返回 `None`，0 也算，没见过的按 0 | 并列取候选里靠前的，就让键只比件数（`min` 遇到相等保留先出现的）。0 不算，就先滤掉总数为 0 的候选，滤完为空返回 `None` | +| 任何时候 | 要考虑多线程吗？ | 单线程 | 见 Follow-up 第 4 条 | + +## 面经里怎么考的 + +只有一篇帖子，2026-10-19 发在一亩三分地。楼主在职跳槽，面 Amazon SDE II，通过。帖子头部的分类字段写面试在 2026 年 7–9 月（论坛按季度分类，楼主没写日期）。这一轮是电话面试（phone screen），帖子标题写的是 OOD 加 BQ。OOD 是面向对象设计（object-oriented design），考怎么拆类、怎么设计数据和接口。BQ 是行为面试题（behavioral questions），问过去的工作经历。 + +面试是这样进行的： + +- **开场**：面试官只让写两个类，讲了仓库管理的背景，第一步要求对 Item 做增、删、查。楼主一时没反应过来，以为之后还有算法题，不知道面试官想考什么。 +- **中途加需求**：面试官接着一条条贴新需求，在已有代码上接着加。帖子记了两条，再往后还有，楼主时间不够没做。 +- **楼主的反思**：这一轮和平时刷的 LeetCode 路数不一样，考的主要是 OOD 和数据结构设计。他认为考点是数据建模（data modeling，决定存哪些数据、用什么结构存、彼此什么关系）和状态一致性（state consistency，同一件事记在几处时，几处的数要始终对得上）。需求是中途加的，没法一开始就想好数据结构和接口，他没做过这类题，最初的设计不太合适，后面每加一条都很被动，只能来回改。他在回复里说自己答得不好，是面试官帮了一把，磕磕绊绊凑出了答案。 +- **代码有没有跑**：楼主说不需要运行，基本是口头把思路讲给面试官听。后面几个 follow-up 时间紧，只写了伪代码，他估计真跑的话跑不通。 + +回复里对「代码要不要能跑」有两种说法，各是各的经历，不能合成一条结论。楼主这一场是口头讲就行。另一位回复的人说，他理解的电话面试是在在线编辑器里写、预期能编译能跑，写完最好拿个小例子跑一遍，这是他对一般情况的理解。还有一位觉得 Amazon 电话面试考 OOD 的越来越多，这是一个人的印象。 + +同一轮还有一道 BQ，问一段能体现 Dive Deep 的经历。Dive Deep 是 Amazon 领导力准则（Leadership Principles）里的一条，大意是深入细节、把问题的根因查清楚。面试官追问了四点：常规的处理办法为什么不行，你自己具体做了哪些事，问题后来是不是真的解决了，最后结果怎么样。准备素材见 [[p:amazon/fit]]。 + +本页据此的建议【推断】：需求会中途加，开场就把所有操作放进一个入口类（思路第 1 节）。能不能跑说法不一，就按严的准备，写成能跑的，写完拿题目一节的例子走一遍。 + +## 思路 + +下面按面试官加需求的顺序走：每一步先写这一步需要的最少的东西，再看下一步来了哪里不够、怎么改。 + +### 1. 第一步：只有仓库和商品 + +第一步要存「哪个仓库里，哪种商品，有几件」，按（仓库，种类）查，所以用两层字典：`_stock[warehouse][item_type]` 就是这条库存记录，查、加、减都是平均 O(1)。键是元组 `(warehouse, item_type)` 的一层字典一样快，用两层是因为能直接列出一个仓库的所有商品（Follow-up 第 2 条要用）。 + +字典的值是一个 `Item` 对象，只有 `type` 和 `quantity`。存整数也够用，保留 `Item` 是因为面试官要求两个类，以后给商品加单价、重量也有地方放。 + +件数减到 0 时，把这条记录删掉。这样「字典里有这条记录」和「件数大于 0」是同一回事，字典不会因为卖完的商品越积越大。删掉以后再查拿不到，按 0 返回，结果不变。`remove_item` 先检查件数够不够，不够就返回 `False`、什么都不改，先减再检查的话件数会变成负数，还得加回去。 + +```python +class Item: + """某个仓库里一种商品的库存记录。""" + + def __init__(self, item_type, quantity=0): + self.type = item_type + self.quantity = quantity + + +class InventoryV1: + """第一步：只有仓库和商品。仓库第一次用到时自动建。""" + + def __init__(self): + self._stock = {} # warehouse -> {item_type -> Item}，只存件数大于 0 的 + + def add_item(self, warehouse, item_type, quantity): + items = self._stock.setdefault(warehouse, {}) + if item_type not in items: + items[item_type] = Item(item_type) + items[item_type].quantity += quantity + + def remove_item(self, warehouse, item_type, quantity): + item = self._stock.get(warehouse, {}).get(item_type) + if item is None or item.quantity < quantity: + return False # 不够就什么都不改 + item.quantity -= quantity + if item.quantity == 0: + del self._stock[warehouse][item_type] + return True + + def delete_item(self, warehouse, item_type): + items = self._stock.get(warehouse, {}) + return items.pop(item_type, None) is not None + + def get_count(self, warehouse, item_type): + item = self._stock.get(warehouse, {}).get(item_type) + return item.quantity if item else 0 +``` + +两个类怎么选，决定了后面改起来被不被动。另一种很自然的开头是 `Item` 加 `Warehouse`，每个 `Warehouse` 对象管自己的商品。第二步要按区域查，就需要一个能看到所有仓库、知道每个仓库属于哪个区域的东西，`Item` 和 `Warehouse` 都不是，只能再加一层，已有的方法跟着搬家【推断】。一开始就用一个入口类（这里的 `InventoryV1`，最终版本叫 `InventorySystem`），第二、三步只是在同一个类上加字典、加方法，调用方的代码不用动。 + +这个版本让仓库在第一次用到时自动建，只有仓库和商品时最省事。第 4 节会看到，它到第二步留下了一个坑。 + +### 2. 第二步：按区域查 + +第二步要回答「某个区域里某种商品一共几件」，先要知道每个仓库属于哪个区域。帖子没说这个关系从哪来，本页设定成登记仓库时给：`add_warehouse(warehouse, region)`，存进 `_region_of[warehouse] = region`。区域总数有两种算法。 + +做法 A 是查的时候现算。再存一个反向映射 `_warehouses_in[region]`（这个区域里所有仓库的集合），查询时把这些仓库的件数加起来。设 W 是区域里的仓库数，一次查询 O(W)。这个映射只在登记仓库时改，改库存时不用碰。 + +做法 B 是维护汇总计数（aggregate count），把每个区域每种商品的总数提前算好存进 `_region_total[region][item_type]`。每次改仓库件数时，顺手把所在区域的总数改掉同样的量，查询直接读，O(1)。 + +两种做法写操作都是 O(1)，B 每次多改一个字典项，多占的内存不超过（仓库，种类）记录的条数。B 的成本主要在别处：同一份库存记了两遍，仓库那份和区域那份必须始终对得上，任何一次改库存漏改了区域那份，查出来的数就错了。这就是楼主说的状态一致性。 + +> [!term] 不变式（invariant） +> 一个数据结构在任何两次操作之间都必须成立的性质。这里的不变式有两条。第一条：对每个区域 r 和种类 t，`_region_total[r][t]` 等于 r 里所有仓库的 t 件数之和。第二条：两个字典里只存件数大于 0 的项。每个写操作的责任，就是在它开始前不变式成立的前提下，保证它结束后不变式仍然成立。 + +只有第二步时，A 已经够用，也没有一致性的风险，面试官说区域查询很少的话选 A 也说得过去。第三步一来就倒向 B（下一节），本页选 B。把 B 加进第一步的代码，最顺手的写法是继承第一步的类、在 `add_item` 和 `remove_item` 后面补上区域总数： + +```python +class InventoryV2Patched(InventoryV1): + """第二步照着第一步的代码打补丁。这个版本有错，思路第 4 节讲。""" + + def __init__(self): + super().__init__() + self._region_of = {} # warehouse -> region + self._region_total = {} # region -> {item_type -> 区域总件数} + + def add_warehouse(self, warehouse, region): + self._region_of[warehouse] = region + self._region_total.setdefault(region, {}) + + def add_item(self, warehouse, item_type, quantity): + super().add_item(warehouse, item_type, quantity) + totals = self._region_total[self._region_of[warehouse]] + totals[item_type] = totals.get(item_type, 0) + quantity + + def remove_item(self, warehouse, item_type, quantity): + if not super().remove_item(warehouse, item_type, quantity): + return False + totals = self._region_total[self._region_of[warehouse]] + totals[item_type] -= quantity + return True + + # delete_item 沿用第一步的写法 + + def get_region_count(self, region, item_type): + return self._region_total.get(region, {}).get(item_type, 0) +``` + +它在题目一节的例子上全部答对（例子没用 `delete_item`，也没碰没登记的仓库），两个错在第 4 节跑给你看。 + +### 3. 第三步：在区域里找库存最少的种类 + +有了区域总数，第三步就是对每个候选读一次区域总数，取最小的： + +```python +class InventoryV3Patched(InventoryV2Patched): + """第三步：在第二步的版本上加 least_stocked。""" + + def least_stocked(self, region, candidates): + if not candidates: + return None + return min(candidates, key=lambda t: (self.get_region_count(region, t), t)) +``` + +`key` 返回元组（件数，名字）。Python 比较元组时先比第一个元素，相等再比第二个，所以 `min` 先挑件数最少的，并列时挑名字最小的。候选为空时 `min` 会抛 `ValueError`，所以先判空。没见过的种类在 `get` 里拿到 0，照常比较。重复的候选键完全相同，不影响结果。 + +设候选有 k 个，用做法 B 是 k 次字典读取，O(k)。用做法 A，每个候选都要把区域里 W 个仓库加一遍，O(k × W)。一个区域有 1000 个仓库、一次给 1000 个候选时，A 要做一百万次字典读取，B 只要一千次（1000 是站方 AI 补的规模上限，帖子没给规模）。这就是第三步倒向 B 的原因。 + +O(k) 不能更少了：任何一个没看过的候选都可能就是最少的那个。装着区域里所有种类的堆（heap）只能给出「所有种类里最少的」，给不出「这 k 个里最少的」，不给候选时才用得上（Follow-up 第 3 条）。 + +### 4. 改库存时怎么让两份数据对得上 + +`InventoryV3Patched` 是照着第一步的代码一条条打补丁打出来的，正好是楼主说的「来回改」。它有两个错，同一组操作在它和最终的 `InventorySystem`（代码一节）上并排跑： + +| 操作 | `InventoryV3Patched` | `InventorySystem` | +| --- | --- | --- | +| 登记 w1、w2 在 east，`add_item("w1", "book", 5)`，`add_item("w2", "book", 3)` | 无 | 无 | +| `delete_item("w1", "book")` | `True` | `True` | +| `get_region_count("east", "book")` | 8 | 3 | +| `add_item("w2", "pen", 5)` 之后 `least_stocked("east", ["book", "pen"])` | `"pen"` | `"book"` | +| `add_item("w9", "book", 5)`，w9 没登记 | 抛 `KeyError` | 抛 `KeyError` | +| 接着 `get_count("w9", "book")` | 5 | 抛 `KeyError` | + +第一个错：`delete_item` 沿用第一步的写法，只删了仓库那条记录，区域总数没减。east 的 book 总数还是 8，第三步拿着这个错数把 book 和 pen 比反了。加汇总时想起了 `add_item` 和 `remove_item`，忘了 `delete_item` 也改库存。 + +第二个错：第一步的 `add_item` 会自动建仓库，它先把 5 本 book 写进 `_stock["w9"]`，回到补丁里查 `_region_of["w9"]` 才发现没登记，抛了 `KeyError`。调用方看到失败，数据里却留下了半次修改：仓库那份有 5 本，区域那份没有。 + +两个错的原因相同：改库存的入口有好几个，各自负责改两份数据，检查也没有都放在修改之前。最终版本针对这两点： + +1. **改库存只有一个地方。**私有方法 `_change(warehouse, item_type, delta)` 把件数改变 `delta`（正数加，负数减），在同一个方法里同时改 `_stock` 和 `_region_total`，减到 0 的项两边都删。`add_item`、`remove_item` 分别传 `quantity`、`-quantity`，`delete_item` 先读出现有件数 n 再传 `-n`。以后多存一份数据（比如 Follow-up 第 3 条的堆），只改 `_change` 一处。 +2. **先检查，再修改。**仓库登记了没有、`quantity` 是不是正整数、库存够不够，都在调 `_change` 之前查完，不满足就抛异常或返回 `False`，这时一个字典都还没碰。`_change` 只做字典操作，用到的 `_stock[warehouse]` 和 `_region_total[region]` 登记仓库时就建好了，所以中途不会抛异常，单线程下要么没开始，要么全部做完。 + +这样写之后，不变式（第 2 节的框）每次操作后都成立，分情况看： + +- 刚建好时两个字典都是空的。`add_warehouse` 登记的新仓库没有库存，区域总数不变。两条都成立。 +- 一次 `_change(w, t, delta)` 让仓库 w 的 t 件数和 w 所在区域的 t 总数变化同样的 `delta`，别的项不动，所以第一条仍然相等。件数不会变成负数：`add_item` 的 `delta` 是正数，`remove_item` 事先查过件数够，`delete_item` 减的正好是现有件数。减到 0 的项两边都删了，第二条也成立。 +- 检查没通过的调用什么都没改。查询不改数据。 + +## 代码 + +面试时写这一版。2026-10-25 跑过，结果见测试用例一节。 + +```python +class Item: + """某个仓库里一种商品的库存记录。""" + + def __init__(self, item_type, quantity=0): + self.type = item_type + self.quantity = quantity + + +class InventorySystem: + def __init__(self): + self._region_of = {} # warehouse -> region + self._stock = {} # warehouse -> {item_type -> Item}，只存件数大于 0 的 + self._region_total = {} # region -> {item_type -> 区域总件数}，只存大于 0 的 + + # 写操作：检查都在前面，修改都交给 _change + + def add_warehouse(self, warehouse, region): + if warehouse in self._region_of: + raise ValueError(f"warehouse {warehouse!r} already exists") + self._region_of[warehouse] = region + self._stock[warehouse] = {} + self._region_total.setdefault(region, {}) + + def add_item(self, warehouse, item_type, quantity): + self._check(warehouse, quantity) + self._change(warehouse, item_type, quantity) + + def remove_item(self, warehouse, item_type, quantity): + self._check(warehouse, quantity) + if self.get_count(warehouse, item_type) < quantity: + return False # 不够：什么都没改 + self._change(warehouse, item_type, -quantity) + return True + + def delete_item(self, warehouse, item_type): + current = self.get_count(warehouse, item_type) # 没登记的仓库在这里抛 KeyError + if current == 0: + return False + self._change(warehouse, item_type, -current) + return True + + # 查询 + + def get_count(self, warehouse, item_type): + if warehouse not in self._stock: + raise KeyError(f"unknown warehouse {warehouse!r}") + item = self._stock[warehouse].get(item_type) + return item.quantity if item else 0 + + def get_region_count(self, region, item_type): + return self._region_total.get(region, {}).get(item_type, 0) + + def least_stocked(self, region, candidates): + if not candidates: + return None + return min(candidates, key=lambda t: (self.get_region_count(region, t), t)) + + # 内部 + + def _check(self, warehouse, quantity): + if warehouse not in self._region_of: + raise KeyError(f"unknown warehouse {warehouse!r}") + if not isinstance(quantity, int) or quantity <= 0: + raise ValueError(f"quantity must be a positive int, got {quantity!r}") + + def _change(self, warehouse, item_type, delta): + """唯一修改库存的地方：仓库那份和区域那份在这里一起改。""" + items = self._stock[warehouse] + if item_type not in items: + items[item_type] = Item(item_type) + items[item_type].quantity += delta + if items[item_type].quantity == 0: + del items[item_type] + + totals = self._region_total[self._region_of[warehouse]] + totals[item_type] = totals.get(item_type, 0) + delta + if totals[item_type] == 0: + del totals[item_type] +``` + +## 复杂度 + +O(1) 都是字典操作的平均情况。 + +| 操作 | 时间 | 原因 | +| --- | --- | --- | +| `add_warehouse` | O(1) | 三次字典写入 | +| `add_item`、`remove_item`、`delete_item` | O(1) | 检查是几次字典读取，`_change` 是两边各一两次字典读写 | +| `get_count`、`get_region_count` | O(1) | 两次字典读取 | +| `least_stocked` | O(k)，k 是候选数 | 每个候选读一次区域总数（思路第 3 节说了为什么不能更少） | + +空间是 O(仓库数 + P)，P 是件数大于 0 的（仓库，种类）记录条数。区域总数的项数不超过 P，因为每个有货的（区域，种类）至少对应一条有货的记录。 + +## 易错点 + +- **加了一份汇总，漏改一个改库存的入口**（思路第 4 节）：`delete_item` 只删仓库那条，区域总数还是旧的。办法是改库存只经过 `_change` 一处。 +- **先改后检查**（思路第 4 节）：改了仓库那份才发现仓库没登记，调用失败却留下半次修改。所有检查放在第一次修改之前。 +- **第一步让仓库自动建，第二步不知道它属于哪个区域**（思路第 1、4 节）：开场就要求仓库先登记，第二步只给 `add_warehouse` 加一个 `region` 参数。 +- **候选为空直接调 `min`**（思路第 3 节）：`min([])` 抛 `ValueError`，先判空。 +- **不检查 `quantity`**（代码一节的 `_check`）：不查正数，`add_item(w, t, -5)` 就能绕过 `remove_item` 的「够不够」检查，把件数减成负数。不查整数，加 0.1、加 0.2、再减 0.3 会剩下约 5.55e-17 件（浮点数加减有舍入误差），这条记录永远删不掉。 +- **件数减到 0 不删记录**（思路第 1 节）：字典越积越大。Follow-up 第 3 条的堆重建时直接压入 `_region_total` 的项，留着 0 的项，重建后就会把 0 当成「最少」返回。 + +## 测试用例 + +2026-10-25 用 `python -I` 跑，Python 3.12.10。测试脚本把本页所有 Python 代码块按出现顺序抽出来执行，再对里面的类做下面的检查，所以测的就是页面上的代码。 + +**页面上的例子**：题目一节例子表的 11 行，在 `InventorySystem`、`InventoryV3Patched`、`InventoryWithLeast`、`LockedInventory` 上都逐行一致。思路第 4 节并排表的 6 行，两个版本都和表里一样。 + +**参照实现**：测试脚本里写了一个最笨的版本当标准答案。所有库存记录放在一个列表里，每次操作从头扫，区域总数查询时现算，件数为 0 的记录也留着，Follow-up 的三个操作也用同样的扫法。它和正式实现的数据结构完全不同。 + +**随机对拍**：随机种子 20261025。每组建 1 到 5 个仓库，随机分到 r1、r2、r3（有的区域没有仓库），商品种类取 a 到 d，再做 20 到 60 次随机操作：加 1 到 5 件，减 1 到 8 件（常比库存多），整条删除，按仓库查，按区域查（还查没登记过的 r4），从候选里找最少（候选 0 到 5 个，可能重复，可能有没出现过的 z）。每次返回值（抛异常时比类型）都和参照实现比，一次不一样就算这一组错。正式实现每次操作后还从 `_stock` 重算区域总数和 `_region_total` 比，并检查没有件数小于等于 0 的项。每行各 500 组，每组约 43 次操作。 + +| 版本 | 操作 | 500 组里结果不一致的组数 | +| --- | --- | --- | +| `InventorySystem` | 上面全部 | 0，不变式每次都成立 | +| `InventoryV3Patched`（思路第 2、3 节，有错） | 上面全部 | 122 组，一共 169 次返回值不对 | +| `InventoryV3Patched` | 去掉整条删除 | 0 | +| `InventoryV1`（思路第 1 节） | 只有第一步的加、减、删、按仓库查 | 0 | +| `InventorySystem`，混入非法操作 | 再加没登记的仓库、`quantity` 为 0 或负数、重复登记 | 0，不变式每次都成立 | +| `InventoryWithLeast`（Follow-up 第 1 到 3 条） | 再加调货（可能调给自己）、换区域（可能换到 r4 或原区域）、不给候选找最少 | 0，不变式每次都成立 | +| `InventoryWithLeast`，混入非法操作 | 上一行再加非法操作，调货目标也可能没登记 | 0，不变式每次都成立 | + +`InventoryV3Patched` 只在有整条删除的序列上出错，和思路第 4 节的分析一致。 + +审稿时又另写了一个参照实现（按流水账记下每次增减，查件数时把流水加起来），换一组随机序列（种子 777，1 到 8 个仓库，6 种商品，每组 30 到 120 次操作，件数最大 10^9，非法的 `quantity` 还有 1.5、0.5 和字符串 `"3"`），每个版本各对拍 400 组，每次操作后还比较所有仓库、所有区域的每种件数。`InventorySystem`、`LockedInventory`（单线程）、`InventoryWithLeast` 在合法序列和混入非法操作的序列上都是 0 组不一致，`InventoryV3Patched` 有删除时错 154 组，去掉删除是 0。 + +**Follow-up 第 3 条的堆**：一个仓库、4 种商品随机加减 20000 次，堆最长 16 项，正好是门槛 2 × 4 + 8。另一个序列先让 100 种商品触发一次重建再逐个整条删除，下一次重建前没压过堆，调了 55 次 `_change`，有效项 45 个，符合按调用次数的分摊分析。 + +**Follow-up 第 4 条（多线程）**：测试脚本给 `get_count` 包了一层，读完件数停 50 毫秒，拉长「查到够」和「去减」之间的时间。w1 有 5 本 book，两个线程同时调 `remove_item("w1", "book", 5)`，各跑 10 次： + +| 版本 | 10 次的结果 | +| --- | --- | +| `InventorySystem`，不加锁 | 10 次都是两个线程都返回 `True`，仓库和区域都变成 -5 本 | +| `LockedInventory` | 10 次都是一个 `True`、一个 `False`，最后是 0 本 | + +另外 8 个线程共用一个 `LockedInventory`，各做 2000 次随机的加、减、整条删除、找最少，跑完后不变式成立。 + +## Follow-up + +帖子没写后面加了什么需求。下面四条是按考点推测的【推断】，考的都是改库存时几份数据怎么始终对得上。 + +### 1. 两个仓库之间调货 + +`transfer(src, dst, item_type, quantity)`：从仓库 src 调 `quantity` 件到仓库 dst，src 不够时返回 `False`、什么都不改。 + +做法还是先检查再修改：两个仓库都登记过、`quantity` 是正整数、src 够，全部满足才调两次 `_change`，一次从 src 减，一次往 dst 加。 + +```python +class InventoryWithTransfer(InventorySystem): + def transfer(self, src, dst, item_type, quantity): + self._check(src, quantity) + self._check(dst, quantity) + if self.get_count(src, item_type) < quantity: + return False + self._change(src, item_type, -quantity) + self._change(dst, item_type, quantity) + return True +``` + +分情况看它为什么对。src 和 dst 在不同区域时，两次 `_change` 把 `quantity` 从 src 的区域总数挪到 dst 的区域总数。在同一个区域时，区域总数先减后加，不变，货也确实还在这个区域。src 和 dst 是同一个仓库时，什么都没变，返回 `True`（要求报错就在开头加一条判断）。两次 `_change` 中间不会抛异常（思路第 4 节），所以不会出现「src 减了、dst 没加」的半次调货。仍是 O(1)。 + +### 2. 仓库换区域 + +`move_warehouse(warehouse, new_region)`：把一个仓库从原来的区域划到新区域。 + +货还在这个仓库里，`_stock` 不用变。要变的是区域总数：这个仓库的每种商品，要从旧区域减掉、加进新区域。做法是先把（种类，件数）抄一份，逐项调 `_change` 减掉，改 `_region_of`，再逐项加回来。 + +```python +class InventoryWithMove(InventoryWithTransfer): + def move_warehouse(self, warehouse, new_region): + if warehouse not in self._region_of: + raise KeyError(f"unknown warehouse {warehouse!r}") + snapshot = [(t, item.quantity) for t, item in self._stock[warehouse].items()] + for t, n in snapshot: + self._change(warehouse, t, -n) # 从旧区域的总数里减掉 + self._region_of[warehouse] = new_region + self._region_total.setdefault(new_region, {}) + for t, n in snapshot: + self._change(warehouse, t, n) # 加进新区域的总数 +``` + +必须先抄（种类，件数）再改，因为第一轮 `_change` 会把件数减到 0 并删掉 `Item`。测试脚本在「w1 有 5 本 book、2 支 pen，从 east 换到 west」上跑过两种省事的错写法： + +- 边遍历 `_stock[warehouse]` 边调 `_change`：删掉第一个 `Item` 时抛 `RuntimeError`（字典在遍历中改变了大小），这时 book 已经从 east 减掉了，数据停在半路。 +- 抄的是 `Item` 对象（`list(self._stock[warehouse].values())`）：第一轮把它们的件数改成了 0，第二轮按 0 加回去，w1、east、west 的 book 全是 0，货凭空没了。 +- 本页的写法：w1 的 book 还是 5，west 是 5，east 是 0。新区域和原区域相同时，减掉再加回来，结果不变。 + +直接改两个区域的总数能少做一半字典操作，本页仍然走 `_change`，因为下一条的堆也挂在 `_change` 上，绕过它，这里又成了一个容易漏改的入口。代价是 O(m)，m 是这个仓库里有货的种类数。做法 A（思路第 2 节）换区域只要改两个映射，O(1)，这是 B 为查得快付出的另一份代价。 + +### 3. 不给候选，直接找区域里库存最少的种类 + +`least_stocked_overall(region)`：在区域里件数大于 0 的种类中，返回总件数最少的，并列取名字最小的，一种都没有返回 `None`。本页设定只算大于 0 的，因为件数为 0 的名字有无穷多个。 + +直接遍历 `_region_total[region]` 是 O(这个区域的种类数)。要更快，就给每个区域维护一个最小堆（min-heap），堆里放（区域总件数，种类）。难处在于区域总数每次改库存都会变，而 Python 的 `heapq` 只能取堆顶、压入新元素，改堆中间的某个元素要先花 O(n) 找到它。 + +> [!term] 懒删除（lazy deletion） +> 堆里的元素过期了先不删，等它到了堆顶再检查，过期就弹出扔掉。这里是区域总数每变一次，就压入新的（新总数，种类），旧的留在堆里。查询时如果堆顶（n，t）的 t 现在的总数不等于 n，这一项就过期了，弹掉再看下一个。 + +```python +import heapq + + +class InventoryWithLeast(InventoryWithMove): + def __init__(self): + super().__init__() + self._heap = {} # region -> [(区域总件数, item_type)]，里面可能有过期的项 + + def _change(self, warehouse, item_type, delta): + super()._change(warehouse, item_type, delta) + region = self._region_of[warehouse] + heap = self._heap.setdefault(region, []) + total = self.get_region_count(region, item_type) + if total > 0: + heapq.heappush(heap, (total, item_type)) + live = self._region_total[region] + if len(heap) > 2 * len(live) + 8: # 过期的项太多，按当前的总数重建 + heap[:] = [(n, t) for t, n in live.items()] + heapq.heapify(heap) + + def least_stocked_overall(self, region): + heap = self._heap.get(region, []) + while heap and self.get_region_count(region, heap[0][1]) != heap[0][0]: + heapq.heappop(heap) # 堆顶过期了，扔掉 + return heap[0][1] if heap else None +``` + +这个做法对，靠的是这条性质：区域里每个件数大于 0 的种类 t，堆里一定有一项（t 现在的总数，t）。这一项是 t 最后一次变化时压进去的，之后 t 没变，所以一直有效。弹出只弹过期的项，重建按当前总数重建，都不会丢掉有效项。所以弹完过期项后的堆顶有效、又是堆里最小的，也就是所有有货种类里（件数，名字）最小的那个。件数减到 0 的种类，`get_region_count` 返回 0，和堆里的正数对不上，会被当成过期弹掉。同一种类可能有两项都「有效」（总数从 5 变 3 又变回 5），两项内容相同，不影响结果。 + +代价：每次改库存多一次压堆，O(log h)，h 是堆的大小。每一项最多被弹出一次，查询的弹出分摊到压堆上，也是 O(log h)。不重建的话过期项会让堆无限长大，所以堆的长度超过有效项数的两倍再加 8 时整个重建。重建的代价按 `_change` 的调用次数分摊：刚重建完，堆的长度等于有效项数 L，离门槛 2L + 8 还差 L + 8。一次 `_change` 最多把这个差距缩小 2（压一项让堆长 1，把一种商品减到 0 让门槛降 2，两件事不会同时发生），所以下一次重建前至少调了 (L + 8) / 2 次 `_change`。下一次重建的花费是那时的有效项数，不超过 L 加上这段时间的调用次数，也就不超过调用次数的 3 倍，分摊到每次 `_change` 是 O(1)。 + +### 4. 多个线程同时调用 + +不加锁时，最严重的问题出在 `remove_item`：它先读件数、确认够，再调 `_change` 减。这种「先检查、再按检查结果去做」的写法叫 check-then-act，两步之间另一个线程也做了同样的检查，两个线程都会以为够。比如 w1 有 5 本 book，线程 A 和 B 同时调 `remove_item("w1", "book", 5)`： + +| 步骤 | 线程 A | 线程 B | +| --- | --- | --- | +| 1 | 读到 5 本，够 | | +| 2 | | 读到 5 本，够 | +| 3 | `_change` 减 5，变成 0 | | +| 4 | | `_change` 减 5，变成 -5 | + +两个都返回 `True`，卖出 10 本，账上 -5 本。`_change` 内部也是好几步，别的线程在中间读，可能读到仓库那份改了、区域那份还没改。CPython 的全局解释器锁（GIL）只保证一条字节码不被打断，管不了几条语句之间被插进来，所以 Python 里照样会出错。 + +修法是给每个公开方法套上同一把锁（lock，同一时刻只有一个线程能拿着它，别的线程等），让每次调用从头到尾不被插进来。要用可重入锁（reentrant lock，`threading.RLock`）：`remove_item` 拿着锁时会调 `get_count`，后者也要拿锁，可重入锁允许已经拿着它的线程再拿一次，普通的 `Lock` 会让线程等自己放锁，永远等下去。Python 里锁的用法见 [[p:me/python-concurrency]]。 + +```python +import threading + + +class LockedInventory(InventorySystem): + """每个公开方法从头到尾拿着同一把锁。""" + + def __init__(self): + super().__init__() + self._lock = threading.RLock() + + def add_warehouse(self, warehouse, region): + with self._lock: + return super().add_warehouse(warehouse, region) + + def add_item(self, warehouse, item_type, quantity): + with self._lock: + return super().add_item(warehouse, item_type, quantity) + + def remove_item(self, warehouse, item_type, quantity): + with self._lock: + return super().remove_item(warehouse, item_type, quantity) + + def delete_item(self, warehouse, item_type): + with self._lock: + return super().delete_item(warehouse, item_type) + + def get_count(self, warehouse, item_type): + with self._lock: + return super().get_count(warehouse, item_type) + + def get_region_count(self, region, item_type): + with self._lock: + return super().get_region_count(region, item_type) + + def least_stocked(self, region, candidates): + with self._lock: + return super().least_stocked(region, candidates) +``` + +加锁以后每次调用都像单独运行一样，思路第 4 节已经证明单独运行的调用保持不变式。两次调用之间没有这个保证：先调 `get_count`、再调 `get_region_count`，中间别的线程可能改了库存。要同一时刻的几个数，就加一个方法在一次加锁里一起读。Follow-up 前三条的方法也要套这把锁。代价是所有调用排队执行，每次只做 O(1) 或 O(k) 的事，拿锁的时间很短。 + +要锁得更细（每个仓库、每个区域各一把，让不同仓库并行），`_change` 就要同时拿两把锁，所有方法按同一个顺序拿锁，才不会出现两个线程各拿一把、等对方放手的死锁（deadlock）。这一段没有写代码测试【推断】。 + +## 英文讲法 + +> [!say] Before I start, does remove mean taking away some quantity, or deleting the whole record? And will more requirements come later, like totals across warehouses? If so, I'll put everything behind one entry class from the start. + +> [!say] I'll keep three dictionaries. One maps each warehouse to its region. One maps each warehouse to its items and their quantities. The third keeps a running total for each region and item type, so a region query is a single lookup. + +> [!say] The cost is that the same stock is stored twice, and the two copies have to agree. So every change to stock goes through one private method that updates both, and every check happens before the first write. + +> [!say] For the least stocked query, I read the region total for each candidate and take the minimum by count, then by name. Any candidate I skip could be the answer, so linear time is the best I can do.
difficulty
@@ -1 +1 @@ -null +medium
kind
@@ -1 +1 @@ -null +practical
lc_numbers
@@ -1 +1 @@ -null +[]
meta
@@ -1 +1 @@ -null +{}
slug
@@ -1 +1 @@ -null +amazon-ood-warehouse-inventory
tags
@@ -1 +1,6 @@ -null +[ + "OOD", + "数据结构设计", + "哈希表", + "Amazon" +]
title
@@ -1 +1 @@ -null +Warehouse Inventory：区域汇总