Cracking The Coding Interview Together – Problem 3.3: Stack Of Plates

We are back in Cracking The Coding Interview — Together mode.

You already know the format.
You already know the drill.
We don’t rush.
We don’t jump to code.
We think like engineers.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Stack of Plates: Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (thatis, pop() should return the same values as it would if there were just a single stack).

Follow Up: Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.

Implement a data structure SetOfStacks that mimics this.

• SetOfStacks.push()
• SetOfStacks.pop()

These should behave exactly like a single stack.

Follow Up

Implement:

popAt(int index)

Which performs a pop operation on a specific sub-stack.

Analyse the problem statement together

We are not implementing one stack.

We are implementing:

👉 A stack of stacks.

Each individual stack has a capacity limit.

Once that limit is reached, we:

• Create a new stack
• Push future elements into that new stack

But here is the important part:

From the outside world, this should behave exactly like a single stack.

Which means:

• push() always pushes to the “top-most available position”
• pop() always removes the most recently inserted element overall

Not the most recently inserted element from a random sub-stack.

So conceptually:

If capacity = 3

And we push:

1, 2, 3, 4, 5, 6, 7

Internally we have,

Stack 0: 1,2,3
Stack 1: 4,5,6
Stack 2: 7

But externally?

It should behave as if we had:

1,2,3,4,5,6,7

And popping should return:

7 → 6 → 5 → 4 → 3 → 2 → 1

Clear?

Good.

Now let’s think like interview engineers.

Questions for the interviewer

Before writing a single line of code, we clarify.

Here are my questions.

You should have yours too.

1. What should happen if capacity is zero?
2. Should pop() remove empty sub-stacks automatically?
3. What should popAt(index) do if index is invalid?
4. When using popAt(index), do we need to perform “rollover”? (shift elements left)

Let’s assume interviewer says:

• Capacity will always be > 0
• Yes, empty stacks should be removed
• Invalid index → throw exception
• For follow-up, yes — implement rollover behavior

Now things are interesting.

Think about the Solution

Close your laptop.

Actually think.

What are we designing?

We need:

• A collection of stacks
• Each stack has a fixed capacity
• We dynamically create new stacks

So what data structure can hold multiple stacks?

👉 ArrayList<Stack<Integer>>

Or even better — since Stack is legacy in Java - we can use:

👉 Deque<Integer> (using LinkedList)

But conceptually, let’s keep it simple.

We need:

List<Stack<T>> stacks
int capacity

Push Logic

If:

• No stacks exist → create one
• Last stack is full → create new stack
• Otherwise → push to last stack

Simple.

Pop Logic

We always:

• Pop from the last stack
• If it becomes empty → remove that stack

Again simple.

But now…

The follow-up changes everything.

Follow-Up: popAt(index)

Now we are allowed to pop from a specific sub-stack.

Example:

Capacity = 3

Push:

1,2,3,4,5,6,7

Stacks:

[1,2,3]  
[4,5,6]  
[7]

Now if we call,

popAt(0)

We pop from stack 0:

[1,2]
[4,5,6]
[7]

But now structure is “imbalanced”.

The problem?

It no longer behaves like a single stack.

To maintain behavior, we need to:

• Remove bottom element from next stack
• Push it to previous stack
• Continue shifting (rollover)

This is the tricky part.

This is what separates surface-level understanding from deep understanding.

Brute Force Thinking

Let’s think naive first.

One simple approach: Flatten everything into one single stack after popAt.

But that would be: Time complexity → O(n)

And that defeats the purpose. We want efficient behavior.

So we must shift elements between stacks.

Correct Approach: Rollover Strategy

When popAt(index) is called:

1. Pop from stack[index]
2. For every stack after index:
   • Remove bottom element
   • Push it to previous stack
3. If last stack becomes empty → remove it

To remove bottom element efficiently, a regular stack is not enough.

Because stack gives access only to top.

So what should we use?

👉 Deque

Because:

• removeLast()
• removeFirst()
• addLast()
• addFirst()

That gives flexibility.

Now we are designing properly.

Write code and explain

Now let’s translate this idea into code.

Java code

import java.util.*;

public class SetOfStacks {
    private List<Deque<Integer>> stacks;
    private int capacity;

    public SetOfStacks(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Capacity must be > 0");
        }
        this.capacity = capacity;
        this.stacks = new ArrayList<>();
    }

    public void push(int value) {
        if (stacks.isEmpty() || stacks.get(stacks.size() - 1).size() == capacity) {
            Deque<Integer> newStack = new ArrayDeque<>();
            stacks.add(newStack);
        }
        stacks.get(stacks.size() - 1).addLast(value);
    }

    public int pop() {
        if (stacks.isEmpty()) {
            throw new EmptyStackException();
        }

        Deque<Integer> lastStack = stacks.get(stacks.size() - 1);
        int value = lastStack.removeLast();

        if (lastStack.isEmpty()) {
            stacks.remove(stacks.size() - 1);
        }

        return value;
    }

    public int popAt(int index) {
        if (index < 0 || index >= stacks.size()) {
            throw new IndexOutOfBoundsException();
        }

        int value = stacks.get(index).removeLast();
        shiftLeft(index);

        return value;
    }

    private void shiftLeft(int index) {
        for (int i = index; i < stacks.size() - 1; i++) {
            Deque<Integer> current = stacks.get(i);
            Deque<Integer> next = stacks.get(i + 1);

            int bottom = next.removeFirst();
            current.addLast(bottom);

            if (next.isEmpty()) {
                stacks.remove(i + 1);
                break;
            }
        }
    }
}

Explain the Code in Plain English

Now this is where you shine.

You must explain:

1. Why you used List<Deque>
2. Why ArrayDeque is better than Stack
3. Why rollover is needed
4. Edge case handling

You must talk about:

• Empty stack removal
• Index validation
• Maintaining stack behavior

Don’t just write code.

Explain it.

Time & Space Complexity

Time Complexity

push(): O(1)

pop(): O(1)

popAt(index):

Worst case:

• We shift elements across stacks

If there are k stacks:

• O(k)

If total elements = n
Worst-case popAt → O(n / capacity)

Space Complexity

We store all elements across stacks.

O(n)

No extra space apart from stack storage.

Final Thoughts

This problem is small.

But it carries a big lesson.

Most interview problems are not about code.

They are about:

• Can you reason about state?
• Can you design clean abstractions?
• Can you explain tradeoffs clearly?

If you understood this deeply,
you are no longer “just solving problems”.

You are designing systems.

And that is what interviews are actually testing.At first glance, this problem feels simple.

“Just use multiple stacks.”

But the follow-up exposes whether you truly understand stack behavior and abstraction.

That is the beauty of these problems.

We are not memorizing solutions.

We are training our thinking.

If you followed along properly, paused, thought through edge cases, and mentally executed the code — you are improving.

If you simply read through it…

You know the answer already.

I’ll see you in the next one.

Happy Coding.