Amazon VO 面试真题解析：Suggestion of Locker Sizes（locker sizing / box fitting）

An Amazon pickup location has a set number of lockers in which boxes are dropped off and picked up.

Boxes can come in many different sizes. Lockers come in a few pre-defined different sizes, with different heights, widths and lengths like these:

Suggestion of locker sizes:
S: 2,2,2 (width, height, length)
M: 4,4,4
L: 8,8,8

Model the lockers, boxes and pickup location and implement:

• An algorithm for efficiently finding the best possible empty locker for a given box (i.e. the smallest empty locker that can fit the box).
• Methods to store a box in a locker within a pickup location
• Methods to retrieve a box from a locker within a pickup location

这道题考察的是如何设计一个自助取件点的 locker 系统：需要根据箱子尺寸快速找到“能放下且最小”的空 locker，并支持存放与取回操作。核心思路通常是按 locker 尺寸分桶管理，用有序结构、优先队列或平衡树维护各尺寸的空闲 locker，从而在查询时优先选择刚好能容纳包裹的最小尺寸，避免浪费空间。实现时还要配合 box 到 locker 的映射，保证 retrieve 操作能 O(1) 或接近 O(1) 定位。