DoorDash 随机选骑手：数组/索引表删除调试

题意与假设

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

• 每个 dasher_id 唯一，重复 add 和不存在的 remove 返回 False；空池 pick 返回 None。题目只说随机返回应等概率，没有统一空池返回契约。
• 示例按当前池内每个骑手等概率选择，不根据距离、在线状态或工作负载加权；可见题面未要求加权派单。
• 示例是单线程训练实现。多线程生产版本需让 add/remove/pick 在同一锁或快照机制下观察一致的数组与索引表。

解题路线

1. 维护紧凑数组 ids 和映射 position[id]→数组下标。add 把新 id 追加到末尾并记位置；pick 在 [0,len(ids)) 均匀抽下标。
2. remove 先查要删的下标，把末尾 id 移到该下标，更新末尾 id 的位置，再弹出末尾。若删除的本来就是末尾，只弹出，不做多余换位。
3. 调试重点是位置映射、数组长度与元素一一对应的不变量；每次操作后断言 len(ids)=len(position)，且 ids[position[id]]=id。

手动走一遍

ids=[A,B,C]，删 B：把 C 放到下标 1，更新 position[C]=1，再弹出末尾，得到 [A,C]。删 C 时它就是末尾，直接弹出得 [A]。若错把 last_index 算成 len(ids) 或在 pop 后再次减 size，会触发越界或遗漏索引。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Uniform random Dasher selection with expected O(1) add/remove/pick."""

import random


class DasherPool:
    def __init__(self, rng: random.Random | None = None) -> None:
        self.ids: list[str] = []
        self.position: dict[str, int] = {}
        self.rng = rng if rng is not None else random.Random()

    def add(self, dasher_id: str) -> bool:
        if dasher_id in self.position:
            return False
        self.position[dasher_id] = len(self.ids)
        self.ids.append(dasher_id)
        return True

    def remove(self, dasher_id: str) -> bool:
        index = self.position.pop(dasher_id, None)
        if index is None:
            return False
        last_index = len(self.ids) - 1
        last_id = self.ids[last_index]
        if index != last_index:
            self.ids[index] = last_id
            self.position[last_id] = index
        self.ids.pop()
        return True

    def pick(self) -> str | None:
        if not self.ids:
            return None
        return self.ids[self.rng.randrange(len(self.ids))]

复杂度

哈希映射均摊下 add/remove/pick 为 O(1) 时间，存储 O(n)。等概率成立因为紧凑数组每个存活 id 恰有一个下标，随机数在 0…n−1 均匀；Python 的 randrange 提供均匀整数索引。

易错点与追问

容易失分的边界

• 删除时若先 pop 末尾，再使用旧 last_index 更新映射，容易在删除末尾或只剩一个元素时越界。
• 忘记更新被搬来的最后一个 id 的 position，后续 remove 会找错下标，随机选择也可能重复或漏人。
• 若随机取 map 的键或仅用 hash 结果取模，而哈希桶分布/空洞不均，不能直接保证每名骑手等概率。
• 一个线程正在 pick 时另一个线程缩短 ids，先读长度再按旧下标访问会越界；单锁是最简单的正确性基线。

继续深挖

• Round Robin 轮询是另一种公平策略，不等于随机等概率；相关面经把两者都放在 Debugging 轮，但题目代码未公开，不能把 Round Robin 的具体 bug 说成此题的 bug。
• 如果骑手有权重或区域过滤，紧凑数组均匀抽样不再足够；需按权重维护前缀和/树或按区域建独立池，并处理动态更新。