面经分享｜餐厅 WaitingList：用分桶 + 有序字典设计“最早且坐得下”的排队系统

Google面试中的一道数据结构设计题：设计一个餐厅的等位系统，支持顾客组加入、离开和安排就餐。题目不长，但“最早加入”和“人数不超过桌子容量”这两个条件一起出现，就很考数据结构的选择：用一个队列就满足不了全部操作。下面按面试中的讲法整理。
题目
设计一个餐厅 WaitingList，支持顾客加入、离开和安排就餐。每组顾客有 group_id 和 group_size。给定 table_size，需要选择最早加入、且人数不超过桌子容量的顾客组。
先想一想：为什么不能只用一个队列
如果只用一个按加入顺序排的队列，安排就餐时要从头找第一个“坐得下”的组，最坏要扫描全部顾客，而且中间某个组离开时还要在队列中间删除，都不够快。所以要换一个结构：把“按人数”和“按加入顺序”分开管理。
思路
我用了三个结构配合：
•       waitlist：记录 group_id 到 group_size 的映射，用来判断某个组是否已在等候，以及离开时查到它属于哪个分桶；
•       size_queues：按 group_size 分桶，每个桶是一个有序字典，记录该人数下所有组的 gr

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

60;  ticket 为什么不用时间戳：递增编号唯一且严格递增，不会因为同一毫秒内多人加入而出现平局。
•       为什么桶用有序字典：需要同时满足“查队首”和“按 group_id 从中间删除”两个操作，普通队列只能做前一个，有序字典两个都是 O(1)。
•       可选的另一种思路：用最小堆维护 ticket，配合惰性删除，但人数条件不好处理，所以分桶更自然。
•       并发：真实系统里 join、leave、serve 可能同时发生，需要加锁。
•       扩展问题：如果要求“结构不同的桌子”、“同一组人可以拆桌”、“给顾客预估等候时间”，都可以在这个结构上继续演进。