“””
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 argument).
“””
This Google data-structure problem requires designing a dynamic waitlist that supports three operations efficiently: adding a party, removing a party at arbitrary time, and querying the earliest (in arrival order) party whose size is less than or equal to a given table capacity. A correct design often maintains ordering for fairness, but also needs a fast way to find the first group that fits, which typically leads to combining a queue-like structure with an auxiliary index—such as a hash map for O(1) removals and a size-bucketed list or balanced tree for efficient“find first that fits.”
