Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Generate the first q primes. Run q rounds: in round i, scan the current pile and split it into plates divisible by the i-th prime (pile B) and the rest (the next pile A). Pop B onto the answer after each round, then continue with A. After all q rounds, pop whatever remains in A onto the answer. Each round is a single linear partition — O(n·q) total.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can compose a prime generator with a clean iterative stack-partitioning loop, and get the LIFO emit order right.
Where candidates slip
Using the wrong prime in a round, re-processing the divisible plates, or emitting piles in the wrong (non-popped) order — and generating primes inefficiently.
How to stand out
Separate concerns: a small prime sieve, then a single-responsibility partition-and-emit loop. Note each round is O(n) and the emit is a stack pop, so the LIFO order is intrinsic.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewprimes = first q primesmore rounds?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Naive Prime Test Per Round (Baseline)
1Hint 1Explore hintHide hint
Two sub-problems: (1) get the first q primes, (2) repeatedly partition the pile by each prime.
2Hint 2Explore hintHide hint
A simple way to get primes is trial division: test each candidate against all smaller primes up to its square root.
3Hint 3Explore hintHide hint
For each round, walk the current pile, bucket plates into divisible vs not, then empty the divisible bucket onto the answer.
A · Core idea
The structure is the same as the optimal — the only difference is how we obtain the primes.
Finding primes by trial division. Starting at 2, test each candidate for primality by dividing by every prime already found that is ≤ √candidate. Collect until we have q of them. This is simple and, for q up to ~1200 (the 1200th prime is under 10000), perfectly fast.
Partition each round. With the primes in hand, run q rounds. In round i, scan the current pile and append each plate either to B (divisible by primes[i]) or to A (not). Empty B onto the answer by popping, then set the current pile to A.
Why it's a fine baseline. The partition loop is already optimal at O(n) per round. The trial-division prime finder is the only mildly wasteful piece, and even that is well within limits. We present the sieve version as the cleaner alternative, but correctness is identical.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
number = [3, 4, 7, 6, 5], q = 1Array state
scan
3→A, 4→B, 7→A, 6→B, 5→A
[6, 4, 5, 7, 3]C · Code with teaching comments
Reference implementation previewimport java.util.*; public List<Integer> firstPrimesTrial(int q) { List<Integer> primes = new ArrayList<>(); int cand = 2;Explore the full codeHide the full code
D · Why it works and complexityO(n·q + cost of finding q primes naively) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The problem cleanly decomposes into 'generate primes' and 'partition by prime'. Keeping those two concerns separate makes the code obviously correct; the only real choice is sieve vs trial division for the primes.
ComplexityO(n·q + cost of finding q primes naively) time, O(n) space — Each round scans up to n plates → O(n·q) for partitioning. Naive trial-division prime finding adds a separate cost; both are acceptable for the given limits but the prime part is the part most worth optimising.
E · Edge cases and pitfalls6no plate divisible by any prime — Every B is empty; plates survive to the final pop of A.Explore edge casesHide edge cases
Edge cases handled
no plate divisible by any primeEvery B is empty; plates survive to the final pop of A.q larger than neededLater rounds simply produce empty B piles; correctness is unaffected.
Pitfalls
- Recomputing primes from scratch inside the round loop instead of once up front.
- Re-including divisible plates in the next round.
- Emitting piles in scan order instead of popped (LIFO) order.
- Off-by-one in choosing the prime: round i uses primes[i], the i-th prime.
Approach 2 of 2 · Optimal
Sieve of Eratosthenes + Partition Loop (Optimal)
1Hint 1Explore hintHide hint
Generating q primes is faster with a sieve than repeated trial division — sieve up to a bound that safely contains the q-th prime.
2Hint 2Explore hintHide hint
The q-th prime is below about q·(ln q + ln ln q); for the given limits a bound near 10⁵ is comfortably safe.
3Hint 3Explore hintHide hint
Then the workflow is unchanged: q rounds, each an O(n) partition, popping the divisible pile onto the answer.
A · Core idea
Same two-part structure, but generate the primes with a Sieve of Eratosthenes for speed and clarity.
Choosing the sieve bound. We need the first q primes. By the prime counting bound, the q-th prime is below roughly q·(ln q + ln ln q). For q ≤ 1200 a bound around 10⁵ is more than enough; in general compute a safe upper bound and sieve up to it, then take the first q primes found.
The sieve. Mark multiples of each prime starting from 2; the unmarked numbers are prime. Collect them in increasing order and keep the first q. This is the standard, cache-friendly way to enumerate small primes.
The partition rounds. Identical to the baseline: for round i, scan the current pile and bucket each plate into B (divisible by primes[i]) or A (not). Empty B onto the answer by popping, then continue with A. After the final round, empty A.
Why popping gives the required order. Each pile behaves as a stack: plates are pushed during the scan and popped onto the answer, so the last plate added to a pile is placed first. That LIFO behaviour is exactly the 'remove from the top' semantics the problem describes for emptying a pile onto the answer.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
number = [3, 3, 4, 4, 9], q = 2Array state
round 1 (p=2)
B=[4,4] → pop → 4,4; A=[3,3,9]
[4, 4, 9, 3, 3]C · Code with teaching comments
D · Why it works and complexityO(n·q + L log log L) where L bounds the q-th prime timeO(n + L) spaceOpen the invariant and proofExplore the proofHide the proof
The whole solution is two well-known building blocks wired in series: a sieve to produce primes, and a stack-partition loop to route plates. Recognising that 'empty the pile onto the answer' means a stack pop is what makes the output order fall out automatically — no manual reversing logic needed beyond popping.
ComplexityO(n·q + L log log L) where L bounds the q-th prime time, O(n + L) space — The sieve over a bound L runs in O(L log log L). Each of the q rounds scans up to n plates → O(n·q). Space is the sieve array plus the piles.
E · Edge cases and pitfalls6all plates divisible in round 1 — A becomes empty after round 1; remaining rounds and the final pop produce nothing more.Explore edge casesHide edge cases
Edge cases handled
all plates divisible in round 1A becomes empty after round 1; remaining rounds and the final pop produce nothing more.number = [11, 13, 15], q = 1Prime 2 divides none → B empty; final pop of A yields 15, 13, 11.
Pitfalls
- Sieve bound too small to contain the q-th prime — size it from the prime-counting estimate.
- Starting the multiple-marking below i² (correct but wasteful) or above it (misses some).
- Forgetting to empty the final surviving pile A after the last round.
- Integer overflow on i*i when computing the first multiple — use long for the bound.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.util.*; public List<Integer> firstPrimes(int q) { int limit = 100000; // safely above the q-th prime for the constraints boolean[] composite = new boolean[limit + 1];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Emitting a pile in the wrong order
The problem removes plates from the top of a pile (LIFO). Appending a pile to the answer in scan order reverses the intended output; you must pop it.
Explore the code comparisonHide the code comparison
Emitting a pile in the wrong order
The problem removes plates from the top of a pile (LIFO). Appending a pile to the answer in scan order reverses the intended output; you must pop it.
Don't write this
for plate in b:
answer.append(plate) # scan order — wrongWrite this instead
while b:
answer.append(b.pop()) # popped (LIFO) order — correct2Forgetting to flush the last pile
Plates not divisible by any of the q primes survive every round and sit in the final pile A. If you stop after the loop without emptying A, those plates are missing from the answer.
Explore the code comparisonHide the code comparison
Forgetting to flush the last pile
Plates not divisible by any of the q primes survive every round and sit in the final pile A. If you stop after the loop without emptying A, those plates are missing from the answer.
Don't write this
for (int i = 0; i < q; i++) {
// ... partition and pop b ...
cur = a;
}
return answer; // forgot to flush cur (the survivors)Write this instead
for (int i = 0; i < q; i++) {
// ... partition and pop b ...
cur = a;
}
for (int j = cur.size() - 1; j >= 0; j--) answer.add(cur.get(j));
return answer;Revise
Carry the pattern into the interview
Pattern to remember
Iterative stack partition by successive primes
Code pattern to memorize
primes = first q primes
cur = number
for i in range(q):
A, B = [], []
for plate in cur:
(B if plate % primes[i] == 0 else A).append(plate)
while B: answer.append(B.pop()) # empty B (popped order)
cur = A
while cur: answer.append(cur.pop()) # empty the last pileRules to remember
- 1Use the i-th prime (2, 3, 5, 7, …) as the divisor in round i — precompute the first q primes.
- 2Each round splits the current pile into
B(divisible) andA(not divisible), preserving the pile's order during the scan. - 3Empty
Bonto the answer by popping it (last pushed first) after each round. - 4The pile that feeds round i+1 is
Afrom round i; never re-include the plates already routed toB. - 5After the final round, empty the remaining pile
Aby popping it too.
Use this pattern when
- Repeatedly partition a pile by a sequence of criteria, emptying one part each round
- Stack-based bucketing where order of removal (LIFO) defines the output
- Problems pairing a number-theory generator (primes) with a stack workflow
- Multi-pass filtering where each pass uses the leftovers of the previous
Choose another pattern when
- A single fixed divisor → one partition pass, no prime sequence needed
- You need all prime factors of each plate → factorisation, not divisibility by the i-th prime
- Output order is FIFO, not LIFO → use a queue and don't reverse on emit
Interview takeaway
Waiter is a disciplined loop: precompute primes, then each round partition the current pile by the next prime, pop the divisible part to the answer, and recurse on the rest. The only traps are using the right (i-th) prime per round and emitting each pile by popping (LIFO).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCompose a prime sieve with an iterative stack-partition loop: each round buckets the current pile by the next prime, pops the divisible bucket onto the answer, and recurses on the rest. The LIFO output falls out of treating each pile as a stack.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Equal StacksAnother multi-stack reduction problem — trim three stacks to equal heights.
- Count PrimesComing soonThe same Sieve of Eratosthenes used here to enumerate primes efficiently.
- Queue Using Two StacksReinforces how moving elements between stacks reverses order — the LIFO emit idea here.