SWE · Phone Screen Coding

Airbnb 二维列表 Iterator:remove 后游标为何会跳元素

Phone Screen 题目给完整 hasNext/next/remove 接口和异常语义;用行列游标、最近返回位置和删除后修正保证原地遍历。

题目重点:Phone Screen 题目给完整 hasNext/next/remove 接口和异常语义;用行列游标、最近返回位置和删除后修正保证原地遍历。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 外部代码在迭代期间不直接修改 nested list;若允许外部并发修改,需要另定义 fail-fast 或快照语义。
  • next/hasNext 在耗尽时分别抛异常/返回 False;remove 在 next 前或同一次 next 后第二次调用抛异常。
  • remove 删除上一次 next 返回的那个元素,不按值删除;重复值必须保留其他位置。

解题路线

  1. 保存 (row,col) 指向下一个候选位置,_advance_to_valid 只跳过空行和已到行尾的位置;hasNext 调用它但不返回/消耗元素。
  2. next 先归一化游标,耗尽则抛异常;记录 (last_row,last_col) 和 removeAllowed=True,再返回当前值并使 col 加一。
  3. remove 校验许可后从原始 nested[last_row] 删除 last_col;若删除发生在当前游标同一行且 last_col<col,则 col−=1,因为后续元素左移一位;清除许可。
  4. 证明:每次 next 返回后游标位于下一个尚未返回元素;remove 删除此前元素并只在同行调整列,所以游标仍指向同一个逻辑后继。
  5. 检查空行链、重复 hasNext、删除行首/尾、跨行后删除上一行、重复值、耗尽/重复 remove。

手动走一遍

题目数据 [[],[1,2,3],[4,5]]:next→1 后 col=1;next→2 后 col=2。remove 删除索引 1,原列表变 [[],[1,3],[4,5]],col 从 2 调回 1;下一次 next 返回 3。若不调回会跳到下一行 4。

规模与取舍

每个元素最多被 next 访问一次,空行跳过总计 O(R);但 Python list.pop(index) 会移动该行剩余元素,单次 remove O(该行后缀长度),多次删除最坏 O(N²)。额外状态 O(1),不复制输入。

易错点与追问

容易失分的边界

  • hasNext 通过 next 探测而消耗元素。
  • remove 按值删除导致重复值错位。
  • 删除后不修正 col。
  • 允许两次 remove 删除不同元素。
  • 说每个操作都 O(1) 而忽略 Python list 中间删除成本。

继续深挖

  • 如何支持外部修改检测?
  • 若要求每次删除均 O(1),底层结构要怎样变?
  • 如果 remove 后当前行为空会怎样?
✓已复制微信号!