Question 1

Valid Parentheses (every bracket closes with the same type in the right order) for s = "(]" and s = "((". Which check is complete?

Accepted Answer

Match each closer to the stack top and return True only if the stack is empty at the end Both conditions matter: "(]" mismatches and "((" leaves items on the stack. Counting types accepts "([)]". Skipping the final empty check accepts "((". The mirror check rejects valid strings like "()()".

Question 2

Min Stack (a stack that also returns its current minimum) with O(1) getMin. What do you store?

Accepted Answer

Each entry as (value, min so far) Storing the min so far with each entry restores the previous min on pop. A single global min is lost when that min is popped. A sorted list makes push O(n). A heap gives O(log n) push and cannot delete the popped value efficiently.

Question 3

Daily Temperatures (for each day, how many days until a warmer one), n up to 10^5. What does the monotonic stack hold and what is the time?

Accepted Answer

Indices with decreasing temperatures, O(n) Indices of days still waiting for a warmer day form a decreasing stack, and each is pushed and popped once. Values alone lose the distance, and there is no log factor. An increasing stack answers the previous smaller element, not the next warmer one. Scanning all later days is the brute force.

Question 4

Evaluate Reverse Polish Notation ["4","13","5","/","+"] where division truncates toward zero. In Python, which division is right for negative operands?

Accepted Answer

int(a / b) int(a / b) truncates toward zero, matching the spec, for operands in the given range. a // b floors, so -7 // 2 is -4 instead of -3. round rounds to nearest. floor is the same as //. Also pop b before a.

Question 5

Queue using two stacks (in and out). When do you move items to out?

Accepted Answer

Only when out is empty, then move all of in Moving only when out is empty keeps FIFO order and makes each item move once, so operations are amortized O(1). Moving on every pop is O(n) per pop and breaks order if out is not empty. Moving on push reverses order each time. A size threshold mixes orders.

Question 6

Decode String such as "3[a2[c]]" to "accaccacc". Approach?

Accepted Answer

Stack of (previous string, repeat count). On a digit build the number (it can be multiple digits). On [ push and reset. On ] pop and set cur = prev + count * cur. Pitfall: reading only one digit.

Question 7

Largest Rectangle in Histogram (largest rectangle area under the bars) with a monotonic increasing stack of indices. When you pop index i at current index r, what is the width?

Accepted Answer

r - stack[-1] - 1 after popping, or r if the stack is empty Bar i extends from just after the new top to just before r. r - i misses the left extension. r - i + 1 includes r, which is shorter. i - stack[-1] measures only the left side.

Question 8

Largest Rectangle in Histogram (largest rectangle area under the bars) with a monotonic stack. Why append a 0 height at the end?

Accepted Answer

It forces every remaining bar to be popped and measured Bars still on the stack at the end are never measured without a final flush. Heights are non negative. You still need the empty stack case for width. The stack stays increasing.

Question 9

Next Greater Element II (next larger value for each element) on a circular array of n. How do you handle wraparound?

Accepted Answer

Iterate i from 0 to 2n - 1 using i % n, pushing only in the first pass A second pass resolves elements whose greater value is before them, and only n results are kept. Returning 2n answers is the wrong size. Two independent runs lose the pending stack. Sorting loses positions.

Question 10

A monotonic stack loop has a while pop inside a for loop. Why is it O(n) and not O(n^2)?

Accepted Answer

Each index is pushed once and popped at most once Total pops cannot exceed total pushes, so the while body runs at most n times overall. A single iteration can pop many. The stack can hold n items. Input need not be sorted.

Stack and monotonic stack interview questions

More coding topics

Practise these on your commute