Q5 - The Waitlist
We believe variations of this interview question have recently been asked by Apple to software engineering candidates. Not every coding round is a clever algorithm. Some hand you a small system to build and watch how you model it. This one looks like a to-do app right up until the third part, where the obvious approach gets slow and you need one clean idea to keep it fast.
Scenario: You are building the sign-up system for a set of popular sessions (think classes, workshops, or events). Each session has a fixed number of seats. Guests sign up, and sometimes they cancel. Assume a guest signs up for a given session at most once.
🧩 You are handed a requirement, not an API. No class name, no method signatures, no return types. Deciding what to expose (signUp, cancel, and later position) and what to store is half of what is being graded. Say your model out loud first, then ask the questions that pin it down: what should signUp return when a session is full? Can the same guest sign up twice? When a confirmed guest cancels, does someone come off the waitlist automatically? Interviewers leave these blank on purpose and watch whether you fill them in.
Part 1. For a session with a given capacity, signUp(session, guest) gives the guest a seat and returns "confirmed" if a seat is free, or "full" if not. cancel(session, guest) frees that guest's seat.
Example 1: Part 1 (seats only)
open("yoga", 2)
signUp("yoga", "Ann") -> "confirmed"
signUp("yoga", "Ben") -> "confirmed" both seats taken
signUp("yoga", "Cara") -> "full" no seats, and no waitlist yet
cancel("yoga", "Ann") Ann's seat opens up
signUp("yoga", "Cara") -> "confirmed" Cara takes it
Part 1: Seats and a Set
Strip away the story and Part 1 is tiny. Each session needs a capacity and the set of guests currently holding a seat. A seat is free whenever that set is smaller than the capacity.
signUp: if the guest already has a seat, leave it be. Otherwise, if there is room, add them and return"confirmed"; if not, return"full".cancel: drop the guest from the seated set.
A set (not a list) matters: sign-ups and cancels are membership operations, so you want O(1) add, remove, and "is this guest already in?".
On a small session it plays out like this:
open("yoga", 2), then a stream of sign-ups and a cancel:
signUp Ann -> "confirmed" seats {Ann}
signUp Ben -> "confirmed" seats {Ann, Ben} (now full)
signUp Cara -> "full" no room, and no waitlist yet
cancel Ann seats {Ben} (a seat frees up)
signUp Cara -> "confirmed" seats {Ben, Cara}
class Waitlist:
def __init__(self):
self.capacities = {} # session -> capacity
self.confirmed = {} # session -> set of guests holding a seat
def open(self, session, capacity):
self.capacities[session] = capacity
self.confirmed[session] = set()
def sign_up(self, session, guest):
seats = self.confirmed[session]
if guest in seats:
return "confirmed" # already seated, ignore
if len(seats) < self.capacities[session]:
seats.add(guest)
return "confirmed"
return "full" # no seats, and no waitlist yet
def cancel(self, session, guest):
self.confirmed[session].discard(guest) # frees a seat
⏱️ Heads up: these are handed to you one part at a time. You solve Part 1, then they add a rule that makes you extend the model. Keep it simple and easy to grow, because Part 3 is where the interesting bookkeeping lives.
Part 2: A Waitlist That Promotes Itself
Now a full session should not just say "full". It should put the guest on a first-come waitlist and return "waitlisted". And when a confirmed guest cancels, the seat should not sit empty: the guest at the front of the waitlist is automatically moved up to confirmed. cancel returns whoever got promoted, or nothing if no one was waiting.
Order matters now, so alongside the confirmed set you need the waitlist in arrival order, which is a queue. The invariant to hold: a session is either at capacity or its waitlist is empty. You never leave a seat empty with someone still waiting.
The promotion is the new move: on a confirmed cancel, pull the front of the line into the freed seat.
def cancel(self, session, guest):
if guest in confirmed[session]:
confirmed[session].remove(guest)
if queue[session]: # a freed seat pulls the next in line
promoted = queue[session].popleft()
waiting[session].remove(promoted)
confirmed[session].add(promoted)
return promoted
return None
Example 2: Part 2 (the waitlist)
open("yoga", 2)
signUp Ann -> "confirmed"
signUp Ben -> "confirmed" session is full
signUp Cara -> "waitlisted" waitlist: [Cara]
signUp Dan -> "waitlisted" waitlist: [Cara, Dan]
cancel Ann -> promotes "Cara" the freed seat pulls the front of the line
signUp and cancel become:
# __init__ now also holds:
# self.waiting[session] = set() # guests currently on the waitlist
# self.queue[session] = deque() # the waitlist, in arrival order
def sign_up(self, session, guest):
if guest in self.confirmed[session]:
return "confirmed"
if guest in self.waiting[session]:
return "waitlisted"
if len(self.confirmed[session]) < self.capacities[session]:
self.confirmed[session].add(guest)
return "confirmed"
self.waiting[session].add(guest) # full, so join the waitlist
self.queue[session].append(guest)
return "waitlisted"
def cancel(self, session, guest):
if guest in self.confirmed[session]:
self.confirmed[session].remove(guest)
if self.queue[session]: # a freed seat pulls the next in line
promoted = self.queue[session].popleft()
self.waiting[session].remove(promoted)
self.confirmed[session].add(promoted)
return promoted
return None
Part 3: Guests Leave the Waitlist Too
The last rule: a waitlisted guest can also cancel, walking away before a seat ever opens. And you want a position(session, guest) that reports how many active guests are ahead of them in line.
The trap is the queue. Removing a guest from the middle of a queue is not cheap, and their leaving can happen long before you would ever reach them. Here is the clean idea: do not remove them from the queue at all. Just drop them from the waiting set. Their entry stays in the queue as a dead placeholder, and both the promotion loop and position simply skip anyone no longer in waiting. This is lazy deletion: mark now, ignore later. Each guest is enqueued once and dequeued at most once, so it stays fast.
The lazy skip is the whole trick: the promote loop walks past dead entries until it finds someone still waiting.
# a departed guest is just dropped from `waiting`; the queue entry stays as a dead placeholder
while queue[session]: # promote the first guest STILL waiting
candidate = queue[session].popleft()
if candidate in waiting[session]: # skip anyone who already left: lazy deletion
waiting[session].remove(candidate)
confirmed[session].add(candidate)
return candidate
Example 3: Part 3 (leaving, and the lazy skip)
open("yoga", 2); Ann, Ben confirmed; Cara, Dan waitlisted (waitlist: [Cara, Dan])
position("yoga", "Dan") -> 1 one active guest (Cara) is ahead of Dan
cancel("yoga", "Cara") -> null Cara just leaves the waitlist
position("yoga", "Dan") -> 0 Cara is skipped, so Dan is now first
cancel("yoga", "Ann") -> promotes "Dan" the promote loop skips Cara and takes Dan
Here is the complete class, with the two changes to cancel (it now handles a waitlisted guest leaving, and its promote loop skips the departed) and the new position:
from collections import deque
class Waitlist:
def __init__(self):
self.capacities = {} # session -> capacity
self.confirmed = {} # session -> set of guests holding a seat
self.waiting = {} # session -> set of guests still on the waitlist
self.queue = {} # session -> deque of guests in arrival order (may hold dead entries)
def open(self, session, capacity):
self.capacities[session] = capacity
self.confirmed[session] = set()
self.waiting[session] = set()
self.queue[session] = deque()
def sign_up(self, session, guest):
if guest in self.confirmed[session]:
return "confirmed"
if guest in self.waiting[session]:
return "waitlisted"
if len(self.confirmed[session]) < self.capacities[session]:
self.confirmed[session].add(guest)
return "confirmed"
self.waiting[session].add(guest)
self.queue[session].append(guest)
return "waitlisted"
def cancel(self, session, guest):
if guest in self.confirmed[session]:
self.confirmed[session].remove(guest)
while self.queue[session]: # promote the first guest still waiting
candidate = self.queue[session].popleft()
if candidate in self.waiting[session]: # skip anyone who already left
self.waiting[session].remove(candidate)
self.confirmed[session].add(candidate)
return candidate
return None
if guest in self.waiting[session]:
self.waiting[session].remove(guest) # leave; the queue entry goes dead
return None
def position(self, session, guest):
if guest not in self.waiting[session]:
return -1
ahead = 0
for candidate in self.queue[session]:
if candidate == guest:
return ahead
if candidate in self.waiting[session]: # count only guests still waiting
ahead += 1
return -1
Complexity Analysis
signUp:O(1). A couple of set lookups, one add, one append.cancel: amortizedO(1). One promotion can pop several dead entries, but each guest is added to the queue once and popped at most once over the whole run, so the popping cost isO(1)averaged out.position:O(w)for a waitlist ofwentries, since it walks the queue. If you need it faster, that is a good place to mention an order-statistics structure, but a scan is usually fine.- Space:
O(n)in the number of guests currently tracked across all sessions.
(One small language note: a couple of the samples above use an array with shift for the queue, which is O(n) per dequeue. In real code reach for a proper deque or linked list so the dequeue is O(1), which is what keeps cancel amortized O(1).)
Final Notes
We believe this waitlist problem, and close variations of it, have appeared frequently in recent interviews for software engineers at Apple. It tests whether you can build a small stateful system, pick containers that fit the operations, and hold an invariant steady as the rules pile up, which is most of everyday engineering.
- The model is the answer. Per session: a capacity, a set of confirmed guests, a set of guests still waiting, and a queue for arrival order. The move that makes it clean is splitting membership (a set, for
O(1)"are they in?") from order (a queue, for "who is next?"). - Cancel guards the invariant. A freed seat immediately pulls the front of the line, so you never sit on an empty seat while someone waits. State that invariant out loud, then make every method preserve it.
- Lazy deletion is the whole of Part 3. You cannot cheaply pull a guest out of the middle of a queue, so do not try. Drop them from the
waitingset and let their queue entry rot; the promote loop andpositionskip anyone no longer waiting. Enqueued once, dequeued once, so it stays fast. - Name your one assumption. This version assumes a guest signs up for a session at most once. If they could leave and re-join, two entries for the same guest could sit in the queue, and you would tag each entry with a version number so the stale one is ignored. Mentioning that is a strong signal.
- Ask before you build. What does a full
signUpreturn? Does cancelling auto-promote? Can a guest be waitlisted for two sessions at once? The prompt leaves these open, and settling them up front is half the job.
The reason a build-a-small-system question shows up at Apple is that day-to-day code is far more about modeling a messy requirement cleanly than about clever math. Get comfortable reaching for a set plus a queue, holding the "no empty seat with people waiting" rule, and letting the waitlist self-heal with a lazy skip. 🚀