这是一道 Google 的真实面试题，题目本身不复杂，但对数据结构设计有一定要求。

英文原题

restaurant waitlist that queue parties with party ID and party size, party can leave early, when table is available we get the oldest waiting party that fits a given table ID and table size

设计一个餐厅候位系统。

每组客人进入等待队列时，会有一个 partyId 和 partySize。等待中的客人可以提前离开。

当某张桌子空出来时，会给定 tableId 和 tableSize，系统需要找到当前等待时间最久、并且人数能够坐下这张桌子的那组客人。

比如当前等待顺序是：

A：4人
B：2人
C：6人
D：3人

如果现在空出来一张 3 人桌，那么 A 坐不下，应该选择 B，而不是简单取队首。

这道题看起来像普通 Queue，但实际上不能直接使用 FIFO。因为我们既要保留到达顺序，又要根据桌子大小跳过不合适的 party。

最直接的实现方式，是维护一个按照加入时间排序的 waitlist。桌子空出来时，从前往后扫描，找到第一个满足：

partySize <= tableSize

的 party。

因为扫描顺序就是等待顺序，所以第一个符合条件的人，自然就是题目要求的：

oldest waiting party that fits

例如：

Party seat(int tableSize) {
    Iterator<Party> it = waitlist.iterator();

    while (it.hasNext()) {
        Party party = it.next();

        if (party.size <= tableSize) {
            it.remove();
            return party;
        }
    }

    return null;
}

这个方案逻辑很直观，但每次分配桌子最坏都需要扫描整个等待队列。

如果面试官继续追问规模变大怎么办，就可以进一步优化。

一种比较自然的方案，是按照 partySize 分组维护多个队列。比如分别维护 1 人、2 人、3 人、4 人等候队列，每个队列内部仍然按照到达顺序排列。

如果现在来了一张 4 人桌，只需要查看人数为 1 到 4 的几个队列的队首，然后从这些候选人中选择到达时间最早的那个。

例如：

2人队列：10:01 P1
3人队列：09:58 P2
4人队列：10:03 P3

现在来一张 4 人桌，最终应该选择 P2，因为它在所有能坐下这张桌子的 party 中等待时间最长。

题目里还有一个条件：

party can leave early

所以系统还需要支持通过 partyId 删除等待中的客人。

这里可以额外维护一个：

Map<String, Party>

用来快速定位 party。

如果不希望频繁从队列中间删除，也可以使用 lazy deletion。客人离开时只把状态标记为 inactive，之后这个 party 到达队首时再真正移除。

这样整体结构就会变成：

按 partySize 维护等待顺序
partyId 用 HashMap 做索引
离开可以使用 lazy deletion
桌子空出来时比较多个候选队首

这道题比较典型的地方在于，第一版其实不难。真正的重点是面试官不断加入新的要求之后，能不能从一个简单的 Queue，逐步调整成更适合查询、删除和匹配的数据结构。

这类题在 Google 面试里很常见，往往不是要求一开始就写出最复杂的方案，而是看候选人能不能根据 follow-up 持续优化。

csoahelp 目前也提供实时文本面试辅助和 Mock Interview。像这类题，实际面试里最难的通常不是第一版代码，而是 interviewer 临时加入约束后，如何快速判断原来的方案哪里需要改、复杂度会发生什么变化，以及下一步该怎么优化。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~