The Number of Students Unable to Eat Lunch problem gives you a queue of students (each preferring sandwich type 0 or 1) and a stack of sandwiches. A student eats only if the top sandwich matches their preference; otherwise they go to the back of the queue. The process ends when no student in the queue wants the current top sandwich. Count the remaining hungry students. This easy coding problem uses counting instead of simulation.
Microsoft, Meta, Amazon, Google, and Bloomberg ask this because the naive simulation can be O(n²) but a clever observation makes it O(n): the process terminates when neither sandwich type 0-preferring nor 1-preferring students remain for the top sandwich. Count how many students prefer each type and compare with the sandwich stack. The array, queue, simulation, and stack interview pattern is directly demonstrated.
Count-based shortcut. Count preferences: cnt[0] = students wanting type 0, cnt[1] = students wanting type 1. Process sandwiches from top of stack: if the top sandwich type s has cnt[s] > 0, decrement cnt[s] (a student takes it). If cnt[s] == 0, no student wants it → the process stops. Return cnt[0] + cnt[1].
students=[1,1,0,0], sandwiches=[0,1,0,1]. cnt=[2,2].
students=[1,1,1,0,0,1], sandwiches=[1,0,0,0,1,1]. cnt=[2,4]. Sandwich 1: cnt[1]=3. Sandwich 0: cnt[0]=1. Sandwich 0: cnt[0]=0. Sandwich 0: cnt[0]=0 → STOP. Remaining=0+3=3.
cnt[0]+cnt[1].This problem is a perfect example of finding a mathematical shortcut to avoid simulation. Instead of simulating queue rotation, observe: as long as students wanting the current sandwich exist, one will eventually reach the front. When no students want it, the process terminates. The count-based approach reduces O(n²) simulation to O(n). Practice identifying when a queue/stack simulation can be replaced by a counting argument — this insight appears across many scheduling simulation problems.