上周刚面完 Google 的一轮远程技术面，现在还心有余悸。作为一名在湾区卷了多年的华人码农，本以为对各种算法题型早已刀枪不入，但当面试官在共享文档上悠悠地敲出那道题时，我还是结结实实地捏了一把汗。
它没有考什么高深的动态规划，也不是复杂的图论，而是一个我们生活中再熟悉不过的场景。
面试题的原文如下：
Implement a restaurant waitlist data structure. It should support the following features:
- A party of customers can join the waitlist.
- A previously joined party can leave the waitlist at any time.
- The restaurant can ask the data structure for the first party that fits a given table size (a table size is given as an argum1ent).
这道题的核心是实现一个餐厅的排队系统。功能要求很明确：第一，客人可以加入等位列表；第二，已经在了列表里的客人，可能因为等不及了，可以随时离开；第三，餐厅有空桌时，可以从等候队伍里找到第一个人数符合要求的客人团队。
看到题目，脑子里第一个闪过的念头就是用队列（Queue）来实现，毕竟排队嘛，先进先出是天经地义的。但“随时离开”这个要求就像一个大大的“Stop”标志，瞬间拦住了我的思路。普通的队列或者数组，如果要删除中间的某个元素，需要先遍历找到它，再执行删除，整个过程的时间复杂度是 O(n)，效率太低了。在 Google 的面试中，这种性能的解法显然是无法过关的。
我的思绪开始飞转，如何在保证客人排队顺序的同时，又能实现快速的“插队”和“离队”呢？
哈希表（HashMap）倒是能实现 O(1) 复杂度的快速查找和删除，但它的问题在于本身是无序的。我没法知道谁是“第一个”来的客人，这与排队的公平原则相悖。
把两种数据结构的优点结合起来？一个念头划过脑海。我需要一个有序的结构来保证“先来后到”，又需要一个“索引”来支持快速定位。
于是，我向面试官提出了我的核心解题思路：双向链表 (Doubly Linked List) + 哈希表 (HashMap) 的组合拳。
具体来说，我用一个双向链表来真实地模拟客人的排队顺序。每个链表节点就代表一个客人团体，节点里存着这个团体的人数。新来的客人团体，就在链表尾部添加一个新节点。
而哈希表的角色，则是一个高效的“登记簿”。它的键（key）是每个客人团体的唯一ID，值（value）则直接指向这个团体在双向链表中所对应的那个节点。
这套组合拳的威力在于：
当一个团体要加入排队时，我们就在链表尾部增加一个节点，并在哈希表中登记它的信息，两个操作都是 O(1) 的，非常快。
当一个团体要随时离开时，就到了这套方案大显身手的时候。我可以通过哈希表，用 O(1) 的时间找到它在链表中的具体位置（节点），然后利用双向链表的特性，在 O(1) 时间内将该节点从链表中移除。完美解决了那个最棘手的效率问题。
而当餐厅需要找人就坐时，我只需要从双向链表的头部（也就是最早来的客人）开始向后遍历，找到第一个人数小于等于桌子大小的团体即可。这个查找过程虽然是 O(n)，但它完全符合“先到先服务”的业务逻辑，是必要的成本。
当我把这套思路清晰地讲出来后，能感觉到面试官对这个方案是认可的。我们后续又简单探讨了一些边界条件的处理，整个面试的氛围也轻松了起来。
回想起来，G 家的面试真的很有意思。它不一定用难题、偏题来考验你，而是通过这种看似简单的生活化场景，来深入考察你对基础数据结构和算法的理解是否扎实，以及你是否具备那种权衡利弊、优雅地解决问题的工程师思维。希望
本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我
