PPractick

The problem

A firmware team can't use the standard library on their microcontroller, so they need their own fixed-capacity stack backed by a plain array for tracking nested interrupt handlers. It must support push, pop, top, isEmpty and size, all in O(1). A stack only ever changes at one end, so a single index topIndex pointing at the last filled slot is all the bookkeeping needed. The details interviewers look for are the boundary cases: popping from an empty stack (return −1 here) and pushing onto a full one (report failure instead of writing out of bounds).

Example: push(2), push(3), pop() → 3, push(4), pop() → 4.

Function signature

class ArrayStack {
public:
    explicit ArrayStack(int capacity);
    bool push(int x);      // false if full
    int pop();             // -1 if empty
    int top() const;       // -1 if empty
    bool isEmpty() const;
    int size() const;
};

Test cases

Operations	Output	Explanation
push(2) push(3) pop() push(4) pop()	3 4	Last in, first out
pop() on an empty stack	-1	Underflow
capacity 2: push(1) push(2) push(3)	true true false	Overflow is refused
push(5) top() size()	5 1	top doesn't remove
push(7) pop() isEmpty()	7 true

(Confirm: all operations O(1); −1 signals "empty" for pop and top; capacity is fixed at construction.)

How interviewers phrase it

• "Implement a stack using an array, with push, pop, top and isEmpty" (GeeksforGeeks).

Clarifying questions to ask

1. Fixed capacity or growable?
2. What should pop or top return on an empty stack? (−1, an exception, or an optional?)
3. What happens when pushing onto a full stack?

Follow-ups to expect

1. "What does topIndex mean?"
2. "How would you make it growable?"
3. "Why is an array better than a linked list here?"
4. "How can two stacks share one array?"
5. "Complexity?"

Related questions

• Trapping Rainwater Hard
• Largest rectangle in a histogram Hard
• Reverse an array Easy
• Basic Hashing Easy
• Counting Frequencies of Array Elements Easy
• Highest Occurring Element in an Array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in