Dinner Plate Stacks

HardHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Picture an unbounded row of stacks numbered from 0 left to right, each holding at most capacity plates. Implement DinnerPlates(capacity): - push(val) puts val on the **leftmost** stack that is not full (a new stack at the right end is used if all existing ones are full). - pop() removes and returns the top plate of the **rightmost** non-empty stack, or -1 if every stack is empty. - popAtStack(index) removes and returns the top plate of stack index, or -1 if that stack is empty or does not exist. Popping from the middle can leave gaps; later pushes fill the leftmost gap first. Aim for O(log n) per operation.

Examples

Input: ["DinnerPlates","push","push","push","push","push","push","push","popAtStack","popAtStack","push","pop","pop","popAtStack","push","push","pop","pop"] [[3],[1],[2],[3],[4],[5],[6],[7],[1],[1],[8],[],[],[2],[9],[10],[],[]]
Output: [null,null,null,null,null,null,null,null,6,5,null,7,8,-1,null,null,10,9]
Pushes give stacks [1,2,3], [4,5,6], [7]. Popping stack 1 twice returns 6 and 5, and 8 fills that gap: [4,8]. pop returns 7 (stack 2), then 8. Stack 2 is now empty. 9 lands on [4] and 10 opens a new stack 2, so the last pops return 10 then 9.
Input: ["DinnerPlates","pop","push","push","popAtStack","push","pop","pop","pop","popAtStack"] [[1],[],[4],[5],[0],[6],[],[],[],[7]]
Output: [null,-1,null,null,4,null,5,6,-1,-1]
With capacity 1, 4 and 5 go to stacks 0 and 1. After stack 0 is emptied, 6 refills it. pop takes 5 from stack 1, then 6, then finds nothing.

Constraints

  • 1 <= capacity <= 2 * 10^4
  • 1 <= val <= 2 * 10^4
  • 0 <= index <= 10^5
  • At most 2 * 10^5 calls in total

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems