Salesforce PhoneDirectory：内存中按号码分配与领取空号

题意与假设

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

• 训练版号码全集为整数 0..capacity−1，初始化时全部空闲；题目未明确范围，因此必须先问有限范围、号码格式和初始占用状态。
• assign 对空闲号码返回 True，对已分配号码返回 False；越界抛 ValueError；get 无空号返回 None。题目只定义成功动作，返回约定是训练补充。
• 单进程单线程内存实现，暂不提供 release；若要并发或进程重启持久化，需增加同步和存储方案，不能从本题的‘禁止外部数据库’推断已具备这些能力。

解题路线

1. 维护每个号码是否空闲，以及一个只含空闲号码的双向链表。prev/next 数组保存链指针，head 指向第一个空号；初始构建需 O(N) 时间与空间。
2. assign(number) 先校验范围，再检查 free[number]；若空闲，借前驱和后继在 O(1) 时间把该号码从空闲链摘掉并设为已分配。重复 assign 直接返回 False，不改变状态。
3. get() 若 head 为空返回 None；否则摘掉 head 并返回号码。循环不变量：链表恰好包含所有 free=True 的号码，且每个号码只出现一次；摘除更新 head、前驱、后继与标志，使不变量保持。
4. 这版按初始号码升序领取，但题目只要求返回任意空号，顺序是训练选择。若希望回收已占号码，则 release 要明确合法性与放回链表的位置，避免双重释放。

手动走一遍

capacity=4，初始空号 0→1→2→3。assign(2) 返回 True 并摘掉 2，链成 0→1→3；再 assign(2) 返回 False。get() 依次得到 0、1、3，此后返回 None。capacity=0 时 head=-1，get() 立即返回 None。

Python 参考实现

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

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

class PhoneDirectory:
    """In-memory assign(number) and get() over numbers 0..capacity-1."""

    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.free = [True] * capacity
        self.prev = [i - 1 for i in range(capacity)]
        self.next = [i + 1 if i + 1 < capacity else -1 for i in range(capacity)]
        self.head = 0 if capacity else -1

    def _remove(self, number: int) -> None:
        before, after = self.prev[number], self.next[number]
        if before == -1:
            self.head = after
        else:
            self.next[before] = after
        if after != -1:
            self.prev[after] = before
        self.free[number] = False
        self.prev[number] = self.next[number] = -1

    def assign(self, number: int) -> bool:
        if number < 0 or number >= self.capacity:
            raise ValueError("number is outside the directory")
        if not self.free[number]:
            return False
        self._remove(number)
        return True

    def get(self) -> int | None:
        if self.head == -1:
            return None
        number = self.head
        self._remove(number)
        return number

复杂度

N=capacity。初始化 O(N) 时间和空间；assign 与 get 在单线程训练模型下都是最坏 O(1) 时间，且不靠惰性堆栈的均摊论证。若号码空间极大且实际分配稀疏，O(N) 预分配不可接受，应换区间集合、位图分段或外部号码池，复杂度随数据结构变化。

易错点与追问

容易失分的边界

• 只用一个 set 储存空号并宣称 get 任意元素都 O(1) 最坏：哈希通常是均摊语义，且迭代取元素的接口细节会影响成本。
• 从链表摘头时忘记把新头的 prev 置为 -1，下一次 assign 可能破坏链结构。
• 把已分配号码再次 assign 后仍返回成功，或把它再次放入空闲池，造成重复发号。
• 将单机内存解法当作多实例全局唯一分配服务；跨进程会重复发相同号码。

继续深挖

• 若新增 release(number)，怎样处理重复释放与恢复升序领取？可按头部插入 O(1) 但不再保持升序，或用有序结构付出 O(log N)。
• 多线程并发 get/assign 如何加锁或原子状态转移？把检查与摘除放在同一临界区，不能先检查后释放锁再摘除。
• 号码池跨服务实例共享且要求故障后不重复发号时，讨论持久化、租约或范围预留；这超出题目的纯内存要求。