| Stack push/pop/peek | O(1) time whether array-backed or linked-list-backed |
| Circular queue enqueue/dequeue | O(1) time; a naive linear-array queue wastes slots and degrades over time |
| java.util.Stack | Legacy, extends Vector, synchronized on every call — avoid in new code |
| ArrayDeque | Resizable circular array, O(1) amortized at both ends, not thread-safe, no nulls |
| Balanced brackets / monotonic stack scan | O(n) time, O(n) worst-case space, single pass |
| BFS traversal with a queue | O(V+E) time — explores level by level, guarantees shortest path in unweighted graphs |
| PriorityQueue (binary heap) | O(log n) offer/poll, O(1) peek — min-heap by default |
| ArrayBlockingQueue | Bounded, FIFO, blocking put()/take() — backbone of producer-consumer pipelines |
Stacks & Queues Interview Questions & Answers
Q1. What is a stack and what core operations does it support?
A: A stack is a linear data structure that follows Last-In-First-Out (LIFO) ordering — the most recently added element is the first one removed. Its core operations are push (add to the top), pop (remove and return the top), peek/top (read the top without removing it), and isEmpty. All four run in O(1) time in a correct implementation, making stacks ideal for undo history, function call frames, and expression parsing.
Q2. What is a queue and what core operations does it support?
A: A queue is a linear data structure that follows First-In-First-Out (FIFO) ordering — the element that has waited longest is removed first. Its core operations are enqueue (add to the rear), dequeue (remove and return the front), peek/front, and isEmpty. A well-implemented queue (circular array or linked list) supports all of these in O(1) time, and queues underlie BFS, task scheduling, and buffering.
Q3. What does LIFO mean and how does it relate to a stack?
A: LIFO stands for "Last In, First Out" — the item pushed most recently is the first one popped. A physical analogy is a stack of plates: you can only take from the top, and you can only add to the top. Every stack operation preserves this invariant, which is why stacks naturally model nested, reversible processes like bracket matching and recursive call unwinding.
Q4. What does FIFO mean and how does it relate to a queue?
A: FIFO stands for "First In, First Out" — the item that entered earliest is the first one to leave. A physical analogy is a checkout line: the person who arrived first is served first, and new arrivals join at the back. This ordering makes queues the natural fit for fairness-sensitive processing, such as request handling, print spooling, and breadth-first traversal.
Q5. How do you implement a stack using a fixed-size array?
A: Maintain a backing array and a top index initialized to -1. push increments top and writes at that slot (checking for overflow first); pop reads the slot at top and decrements it (checking for underflow first). All operations are O(1), but capacity is fixed unless you add resizing logic similar to ArrayList's growth strategy.
class ArrayStack {
private int[] data;
private int top = -1;
ArrayStack(int capacity) { data = new int[capacity]; }
void push(int value) {
if (top == data.length - 1) throw new RuntimeException("Stack overflow");
data[++top] = value;
}
int pop() {
if (top == -1) throw new RuntimeException("Stack underflow");
return data[top--];
}
int peek() { return data[top]; }
boolean isEmpty() { return top == -1; }
}Q6. How do you implement a stack using a singly linked list?
A: Keep a reference to the head node, which always represents the top of the stack. push creates a new node whose next points to the current head, then reassigns head to the new node — O(1), no shifting. pop reads the head's value and reassigns head to head.next — also O(1). Unlike an array stack, this has no fixed capacity limit (beyond available memory).
class LinkedStack<T> {
private Node<T> top;
private static class Node<T> {
T value; Node<T> next;
Node(T value, Node<T> next) { this.value = value; this.next = next; }
}
void push(T value) { top = new Node<>(value, top); }
T pop() {
if (top == null) throw new RuntimeException("Stack underflow");
T value = top.value;
top = top.next;
return value;
}
T peek() { return top.value; }
boolean isEmpty() { return top == null; }
}Q7. What are the trade-offs between array-based and linked-list-based stack implementations?
A: An array-backed stack has excellent cache locality (contiguous memory) and no per-node allocation overhead, but either has a fixed capacity or needs occasional O(n) resizing. A linked-list-backed stack grows without a predefined limit and never needs a bulk resize, but each node carries pointer overhead and poorer cache locality due to scattered memory. In practice, Java's ArrayDeque (array-backed, resizable) outperforms a linked-list stack for almost all workloads.
Q8. What is stack overflow and stack underflow?
A: Stack overflow occurs when you attempt to push onto a stack that has already reached its maximum capacity — in a fixed-size array implementation this must be checked explicitly, and in the JVM's call stack it happens from excessively deep (often unbounded) recursion, producing a StackOverflowError. Stack underflow occurs when you attempt to pop or peek an empty stack; a correct implementation should throw an exception rather than returning a misleading default value.
Q9. How do you implement a queue using a plain (non-circular) array?
A: Maintain a front index (starting at 0) and a rear index (starting at -1). enqueue increments rear and writes there; dequeue reads the slot at front and increments front. Both are O(1), but front only ever increases, so slots before it become permanently unusable even though logically the queue has shrunk — this is the classic motivation for a circular queue.
class NaiveArrayQueue {
private int[] data;
private int front = 0, rear = -1, size = 0;
NaiveArrayQueue(int capacity) { data = new int[capacity]; }
void enqueue(int value) {
if (rear == data.length - 1) throw new RuntimeException("Queue full");
data[++rear] = value;
size++;
}
int dequeue() {
if (size == 0) throw new RuntimeException("Queue empty");
size--;
return data[front++]; // front only ever advances -- wastes freed slots
}
}Q10. Why does a naive array-based queue waste space, and how is this fixed?
A: Because front only ever moves forward, every dequeued slot at the beginning of the array becomes dead space that can never be reused, even though the array has plenty of "logical" free capacity once elements are removed. Eventually rear hits the physical end of the array and enqueue fails, despite the queue being far from its true intended capacity. The fix is a circular queue, which wraps both front and rear back to index 0 using modulo arithmetic so freed slots are reused.
Q11. How do you implement a circular queue using an array?
A: Track front, rear, and a running size (or reserve one empty slot to distinguish full from empty without a counter). On enqueue, advance rear with (rear + 1) % capacity before writing; on dequeue, read at front then advance it the same way. Wrapping around with modulo lets freed slots at the start of the array be reused, giving true O(1) enqueue/dequeue within a fixed-size buffer.
class CircularQueue {
private int[] data;
private int front = 0, rear = -1, size = 0;
private final int capacity;
CircularQueue(int capacity) {
this.capacity = capacity;
data = new int[capacity];
}
boolean enqueue(int value) {
if (size == capacity) return false;
rear = (rear + 1) % capacity;
data[rear] = value;
size++;
return true;
}
int dequeue() {
if (size == 0) throw new RuntimeException("Queue empty");
int value = data[front];
front = (front + 1) % capacity;
size--;
return value;
}
}Q12. How do you implement a queue using a singly linked list?
A: Keep both a head (front) and tail (rear) reference. enqueue creates a node, links it after the current tail, and updates tail to point to it — O(1), no traversal needed because tail is tracked directly. dequeue reads the head's value and advances head to head.next, resetting tail to null if the list becomes empty — also O(1). This avoids any fixed capacity limit that a plain array queue would impose.
class LinkedQueue<T> {
private static class Node<T> {
T value; Node<T> next;
Node(T value) { this.value = value; }
}
private Node<T> head, tail;
void enqueue(T value) {
Node<T> node = new Node<>(value);
if (tail == null) { head = tail = node; }
else { tail.next = node; tail = node; }
}
T dequeue() {
if (head == null) throw new RuntimeException("Queue empty");
T value = head.value;
head = head.next;
if (head == null) tail = null;
return value;
}
}Q13. What is java.util.Stack and why is it generally discouraged in modern Java code?
A: java.util.Stack is a legacy class dating back to Java 1.0 that extends Vector, inheriting index-based access, synchronized methods on every call, and Vector's growth semantics — none of which a pure stack needs. The synchronization adds locking overhead even in single-threaded code, and extending a random-access list exposes operations (like inserting at an arbitrary index) that violate the stack abstraction. The Java documentation itself recommends Deque, implemented by ArrayDeque, as the modern replacement.
Q14. What is java.util.Deque and how does it relate to the Stack and Queue interfaces?
A: Deque ("deck", double-ended queue) is an interface supporting insertion and removal at both ends in O(1): addFirst/addLast, removeFirst/removeLast, peekFirst/peekLast. Because it supports both ends efficiently, a single Deque implementation can serve as a stack (always operate on the front, via push/pop) or as a FIFO queue (add at the rear, remove from the front, via offer/poll). ArrayDeque and LinkedList both implement Deque, but ArrayDeque is preferred for both stack and queue use in modern code.
Q15. Why is ArrayDeque recommended over Stack and LinkedList for stack/queue usage in Java?
A: ArrayDeque is backed by a resizable circular array, giving it better cache locality and lower per-element memory overhead than LinkedList's node-based storage, and it has no synchronization overhead unlike the legacy Stack class. It provides O(1) amortized insertion and removal at both ends, and the JDK explicitly documents it as likely faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // addFirst
stack.pop(); // removeFirst
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // addLast
queue.poll(); // removeFirstQ16. How does ArrayDeque implement its backing storage internally?
A: ArrayDeque uses a single Object array treated as a circular buffer, with separate head and tail indices tracked modulo the array's length. Adding to the front decrements head (wrapping to the end if needed); adding to the rear writes at tail and increments it. When the array fills up, it is doubled in size and elements are copied into a fresh, unwrapped layout — the same amortized-O(1) growth strategy ArrayList uses for appends.
Q17. Why does ArrayDeque disallow null elements?
A: ArrayDeque uses null internally as a sentinel to represent an empty slot in its circular array, which lets methods like peekFirst() distinguish "empty deque" from "element present" by checking for null rather than maintaining a separate size field for every read. If user code were allowed to store null values, that sentinel would become ambiguous, so the JDK simply forbids it — attempting to add null throws a NullPointerException.
Q18. What is the time complexity of ArrayDeque's addFirst/addLast/pollFirst/pollLast operations?
A: All four are O(1) amortized. Because the backing array is circular, adding or removing at either end only ever touches the head or tail index and the single slot it points to — no shifting of other elements is required, unlike inserting at the front of a plain ArrayList. The occasional O(n) resize when the circular buffer fills up is amortized across many O(1) operations, exactly like ArrayList's amortized append.
Q19. How do you use Deque to implement a stack in Java?
A: Declare a Deque reference (backed by ArrayDeque) and use only its stack-oriented methods: push(value) (an alias for addFirst) and pop() (an alias for removeFirst). Because both operate on the same end, the most recently pushed element is always the first popped — exact LIFO semantics — with O(1) performance and no synchronization overhead.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop()); // 30 -- LIFOQ20. How do you use Deque to implement a FIFO queue in Java?
A: Use offerLast (or the plain offer, which defaults to the tail) to enqueue, and pollFirst (or plain poll) to dequeue. Because insertion happens at the rear and removal happens at the front, the element that has waited longest always leaves first — exact FIFO semantics, in O(1) time per operation.
Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(10);
queue.offerLast(20);
queue.offerLast(30);
System.out.println(queue.pollFirst()); // 10 -- FIFOQ21. What is a monotonic stack and what class of problems does it solve?
A: A monotonic stack maintains its elements in strictly increasing or strictly decreasing order at all times, by popping elements that would violate that order before pushing a new one. It is the standard technique for "next greater/smaller element," histogram-area, and span-style problems, because it lets you answer, for every element, a question about its nearest larger/smaller neighbor in O(n) total time instead of O(n²) brute force.
Q22. How do you solve the Next Greater Element problem using a monotonic stack?
A: Scan left to right while maintaining a stack of indices whose values are in decreasing order. For each new element, pop every stack index whose value is smaller than the current element — the current element is each popped index's "next greater element" — then push the current index. Every element is pushed once and popped at most once, so the total cost is O(n) despite the nested-looking while loop.
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // holds indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}Q23. How do you solve the Next Smaller Element problem using a monotonic stack?
A: The mirror image of Next Greater Element: maintain a stack of indices whose values are increasing, and whenever the current element is smaller than the value at the stack's top index, pop that index and record the current element as its next smaller element. This is also O(n) time, O(n) space, and the two variants are frequently combined to compute both left and right nearest bounds in histogram-style problems.
int[] nextSmaller(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}Q24. How do you find the next greater element in a circular array?
A: Simulate the array as if it were traversed twice (length 2n) by using i % n to index into the actual array, but only push indices during the first pass to avoid double-counting. This lets an element near the end still discover a larger element that appears near the beginning, correctly handling wraparound, while keeping the total work O(n).
int[] nextGreaterCircular(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
while (!stack.isEmpty() && nums[stack.peek()] < nums[idx]) {
result[stack.pop()] = nums[idx];
}
if (i < n) stack.push(idx);
}
return result;
}Q25. How do you solve the Stock Span Problem using a stack?
A: The span of a day is how many consecutive days up to and including today had a price less than or equal to today's price. Maintain a stack of indices with strictly decreasing prices; pop while the top's price is <= today's price, then the span is today - newTopIndex (or today + 1 if the stack empties). This amortizes to O(n) total across all days, because each index is pushed once and popped at most once.
int[] stockSpan(int[] prices) {
int n = prices.length;
int[] span = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // indices, decreasing prices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
}
span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return span;
}Q26. How do you compute Daily Temperatures — for each day, how many days until a warmer one — using a stack?
A: Maintain a stack of indices whose temperatures are non-increasing as you scan left to right. When the current day's temperature is strictly greater than the temperature at the stack's top index, pop that index and set its answer to the distance between the two indices, repeating until the stack top no longer qualifies. This is O(n) time overall because each index is pushed once and popped at most once.
int[] dailyTemperatures(int[] temps) {
int n = temps.length;
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
int idx = stack.pop();
result[idx] = i - idx;
}
stack.push(i);
}
return result;
}Q27. How do you solve Largest Rectangle in Histogram using a stack?
A: Maintain a stack of indices with non-decreasing bar heights. When the current bar is shorter than the bar at the stack's top, pop it and compute the rectangle where that bar's height is the limiting factor — its width spans from the (now-exposed) new stack top plus one, to the current index minus one. A sentinel zero-height bar appended at the end forces all remaining bars to be resolved. This runs in O(n) time since each index is pushed and popped exactly once.
int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0, n = heights.length;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] >= h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}Q28. How can Trapping Rain Water be solved with a stack instead of the two-pointer approach?
A: Maintain a stack of indices with non-increasing bar heights. When a taller bar arrives, pop the top as the "valley floor," and if the stack isn't empty afterward, the trapped width is the distance between the new top and the current index, and the trapped height is min(heights[newTop], heights[current]) - heights[valley]; accumulate this for every pop. This is O(n) time and O(n) space, versus the two-pointer solution's O(n) time and O(1) space — the two-pointer approach is generally preferred, but the stack approach generalizes more naturally to some 2D/skyline variants.
Q29. How do you check if a string of brackets is balanced using a stack?
A: Push every opening bracket onto the stack. On a closing bracket, the string is immediately invalid if the stack is empty (nothing to match) or if the popped opening bracket's type doesn't correspond to the closing bracket seen. After scanning the whole string, it is valid only if the stack ends up empty (no unmatched opens remain). This is O(n) time and O(n) worst-case space.
boolean isBalanced(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char open = stack.pop();
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) return false;
}
}
return stack.isEmpty();
}Q30. How do you determine the minimum number of parentheses to add to make a string valid?
A: Track two counters as you scan: openNeeded (unmatched '(' count) and insertions (closes required so far). On '(', increment openNeeded. On ')', decrement openNeeded if positive (it matches an existing open); otherwise there is no open to match, so increment insertions (you'd need to add a '(' before it). At the end, the answer is insertions + openNeeded (every unmatched open still needs a closing bracket appended). This is O(n) time, O(1) space.
Q31. How do you check if a string is a valid parenthesis sequence when it also contains wildcard '*' characters?
A: Since '*' can act as '(', ')', or empty, track a range [loOpen, hiOpen] of possible counts of unmatched opens instead of a single count. On '(', both bounds increase; on ')', both decrease (clamping loOpen at 0); on '*', loOpen decreases and hiOpen increases (covering all three interpretations). The string is invalid as soon as hiOpen goes negative, and it is valid overall if loOpen reaches 0 by the end. This greedy two-counter approach is O(n) time, O(1) space, avoiding exponential brute-force enumeration of wildcard choices.
Q32. What is the difference between infix, postfix, and prefix notation?
A: Infix notation places the operator between operands (a + b), matching how humans normally write math but requiring precedence rules and parentheses to disambiguate. Postfix (Reverse Polish) notation places the operator after its operands (a b +) and prefix (Polish) notation places it before (+ a b); both eliminate the need for parentheses or precedence rules entirely, which is exactly why postfix/prefix are the forms computers and calculators evaluate directly with a stack.
Q33. How do you convert an infix expression to postfix notation using the Shunting-Yard algorithm?
A: Scan the infix expression left to right. Operands go directly to the output; '(' is pushed onto an operator stack; ')' pops operators to the output until a matching '(' is found and discarded; and any other operator pops higher-or-equal-precedence operators to the output before being pushed itself. After the scan, pop all remaining operators to the output. This runs in O(n) time using a stack to hold pending operators.
String infixToPostfix(String expr) {
StringBuilder output = new StringBuilder();
Deque<Character> ops = new ArrayDeque<>();
Map<Character, Integer> prec = Map.of('+', 1, '-', 1, '*', 2, '/', 2, '^', 3);
for (char c : expr.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
output.append(c);
} else if (c == '(') {
ops.push(c);
} else if (c == ')') {
while (ops.peek() != '(') output.append(ops.pop());
ops.pop();
} else {
while (!ops.isEmpty() && ops.peek() != '(' &&
prec.get(ops.peek()) >= prec.get(c)) {
output.append(ops.pop());
}
ops.push(c);
}
}
while (!ops.isEmpty()) output.append(ops.pop());
return output.toString();
}Q34. How do you convert an infix expression to prefix notation?
A: Reverse the infix expression (swapping every '(' with ')' and vice versa), convert that reversed expression to postfix using the standard Shunting-Yard algorithm, then reverse the resulting postfix string. The double reversal correctly re-orders operators to precede their operands while preserving the original evaluation order, and the whole process remains O(n) time.
Q35. How do you evaluate a postfix expression using a stack?
A: Scan tokens left to right. Push every operand onto the stack. On an operator, pop the two most recent operands (the second-popped is the left operand, the first-popped is the right operand), apply the operator, and push the result back. After processing all tokens, the single remaining stack element is the final answer. This is O(n) time, O(n) space, and requires no precedence rules at evaluation time since postfix already encodes the correct order.
int evalPostfix(String expr) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : expr.split(" ")) {
if (token.matches("-?\\d+")) {
stack.push(Integer.parseInt(token));
} else {
int b = stack.pop(), a = stack.pop();
switch (token) {
case "+": stack.push(a + b); break;
case "-": stack.push(a - b); break;
case "*": stack.push(a * b); break;
case "/": stack.push(a / b); break;
}
}
}
return stack.pop();
}Q36. How do you evaluate a prefix expression using a stack?
A: Scan the tokens from right to left. Push every operand onto the stack. On an operator, pop the two most recently pushed values (the first pop is the left operand, the second pop is the right operand, since we're scanning backward), apply the operator, and push the result. The final remaining value is the answer. Scanning right-to-left (rather than left-to-right, as postfix does) is what makes prefix evaluation work correctly.
int evalPrefix(String expr) {
Deque<Integer> stack = new ArrayDeque<>();
String[] tokens = expr.split(" ");
for (int i = tokens.length - 1; i >= 0; i--) {
String token = tokens[i];
if (token.matches("-?\\d+")) {
stack.push(Integer.parseInt(token));
} else {
int a = stack.pop(), b = stack.pop();
switch (token) {
case "+": stack.push(a + b); break;
case "-": stack.push(a - b); break;
case "*": stack.push(a * b); break;
case "/": stack.push(a / b); break;
}
}
}
return stack.pop();
}Q37. How do you convert a postfix expression directly to infix notation?
A: Scan tokens left to right, pushing operands onto a stack as parenthesized strings. On an operator, pop the two most recent operand strings, wrap them with the operator between them in parentheses ("(" + left + op + right + ")"), and push that combined string back onto the stack. After the scan, the single remaining stack element is the fully parenthesized infix expression, built in O(n) time.
Q38. What is an expression tree and how does it relate to prefix/postfix notation?
A: An expression tree represents an arithmetic expression where every internal node is an operator and every leaf is an operand, with each operator's children being its left and right sub-expressions. A postorder traversal (left, right, node) of this tree produces the postfix form; a preorder traversal (node, left, right) produces the prefix form; and an inorder traversal (with parentheses inserted around subtrees) produces the infix form. Building this tree from postfix is itself a classic stack-based algorithm: push operand nodes, and on an operator, pop two nodes to be its children and push the new subtree.
Q39. How do you implement a basic calculator that evaluates +, -, *, / with correct precedence but no parentheses?
A: Scan the string tracking the previous operator (starting as '+') and the current number being built. Whenever you hit a new operator (or the end of string), push the previous number onto a stack — negated if the previous operator was '-', or combined via multiplication/division with the value already on top of the stack if it was '*' or '/'. Summing everything left on the stack at the end gives the answer, correctly respecting precedence without ever converting to postfix. This is O(n) time, O(n) space.
int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<>();
int num = 0;
char sign = '+';
s = s.replaceAll("\\s+", "") + "+";
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else {
if (sign == '+') stack.push(num);
else if (sign == '-') stack.push(-num);
else if (sign == '*') stack.push(stack.pop() * num);
else if (sign == '/') stack.push(stack.pop() / num);
sign = c;
num = 0;
}
}
int total = 0;
for (int n : stack) total += n;
return total;
}Q40. How do you design a stack that supports getMin() in O(1) time (Min Stack)?
A: Maintain a second, auxiliary stack alongside the main one that tracks, at every depth, the minimum value seen so far. On push, compute min(newValue, currentMin) and push it onto the auxiliary stack; on pop, pop from both stacks in lockstep. getMin() then simply peeks the auxiliary stack's top — O(1) time, O(n) extra space, and pops automatically "restore" the previous minimum since the auxiliary stack mirrors the main one's depth.
class MinStack {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();
void push(int val) {
stack.push(val);
int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
minStack.push(currentMin);
}
void pop() { stack.pop(); minStack.pop(); }
int top() { return stack.peek(); }
int getMin() { return minStack.peek(); }
}Q41. How do you design a stack that supports getMax() in O(1) time?
A: This mirrors the Min Stack design exactly: maintain an auxiliary stack that, at every depth, tracks max(newValue, currentMax) instead of the minimum. Push and pop both stacks together, and getMax() peeks the auxiliary stack. Both approaches share the same O(1) time per operation and O(n) extra space trade-off, and both can be optimized to store only deltas when memory is tight.
Q42. How would you implement a stack that also supports finding the middle element efficiently?
A: Use a doubly linked list as the stack's storage and maintain a separate mid pointer. Track the current size; when pushing makes the size odd, advance mid to mid.prev (toward the new top); when popping makes the size even, advance mid to mid.next. This keeps mid correctly positioned in O(1) per push/pop, avoiding an O(n) scan to the middle on every query.
Q43. How do you implement a queue using two stacks?
A: Use an "in" stack for enqueuing (just push) and an "out" stack for dequeuing. When a dequeue is requested and the "out" stack is empty, pop every element from "in" and push it onto "out," which reverses the order so the oldest element ends up on top; then pop from "out." Enqueue is always O(1); dequeue is O(1) amortized because each element is moved from "in" to "out" exactly once over its lifetime.
class QueueUsingStacks<T> {
private Deque<T> inStack = new ArrayDeque<>();
private Deque<T> outStack = new ArrayDeque<>();
void enqueue(T value) { inStack.push(value); }
T dequeue() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) outStack.push(inStack.pop());
}
return outStack.pop();
}
}Q44. How do you implement a stack using two queues?
A: One approach makes push O(n): enqueue the new element into the secondary queue, then drain the primary queue into the secondary queue behind it, and finally swap the two queue references so the primary queue always has the most recent element at its front (making pop O(1)). This trades push's cost for pop's, the opposite of the two-stacks-as-queue approach, illustrating how the same conversion problem can shift cost to either operation.
class StackUsingQueues<T> {
private Queue<T> q1 = new LinkedList<>();
private Queue<T> q2 = new LinkedList<>();
void push(T value) {
q2.offer(value);
while (!q1.isEmpty()) q2.offer(q1.poll());
Queue<T> temp = q1; q1 = q2; q2 = temp;
}
T pop() { return q1.poll(); }
}Q45. How do you implement a queue using a single stack and recursion?
A: Enqueue simply pushes onto the one stack — O(1). Dequeue is done recursively: pop the top element, and if the stack becomes empty, that popped value is the answer; otherwise, recursively dequeue from the now-smaller stack first, then push the originally popped value back on top. This restores stack order using the call stack itself as the second storage area, achieving the two-stack effect with only one explicit stack, at the cost of O(n) time and O(n) recursive call-stack space per dequeue.
Q46. How do you design a circular deque (double-ended queue) with a fixed capacity?
A: Use a fixed-size array with both a front and rear index, both moving with modulo arithmetic like a circular queue, but supporting insertion/removal at either end. insertFront decrements front modulo capacity before writing; insertLast increments rear modulo capacity after writing; the mirror operations remove from either end. A separate size counter (or reserving one empty slot) distinguishes a full deque from an empty one, since both states can otherwise leave front == rear.
Q47. What is a priority queue and how does java.util.PriorityQueue implement it?
A: A priority queue is an abstract data type where each dequeue operation returns the element with the highest priority (by default, the smallest, in Java) rather than the oldest one — it is not FIFO. java.util.PriorityQueue implements this with a binary min-heap stored in a resizable array, where the parent at index i is always <= its children at 2i+1 and 2i+2, guaranteeing the smallest element is always at index 0.
Q48. What is the time complexity of insertion and extraction in a binary-heap-based priority queue?
A: Insertion (offer) is O(log n): the new element is placed at the end of the array and "sifted up" by swapping with its parent while it violates the heap property. Extraction of the minimum (poll) is also O(log n): the root is removed, the last element is moved to the root, and it is "sifted down" to restore the heap property. Peeking the minimum is O(1) since it's always at the root.
Q49. How do you create a max-heap using java.util.PriorityQueue, which is a min-heap by default?
A: Supply a comparator that reverses the natural order, either Collections.reverseOrder() for Comparable elements or a custom lambda like (a, b) -> b - a. The heap's internal structure is unchanged — it still maintains a "smallest at the root" invariant — but "smallest" is now redefined by the reversed comparator to mean "largest by natural order," so poll() returns the maximum element.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(9);
System.out.println(maxHeap.poll()); // 9Q50. How do you use a custom Comparator with PriorityQueue to order complex objects?
A: Pass a Comparator to the constructor that defines the ordering by whichever field matters — for example, ordering int[] pairs by their second element. The heap then uses that comparator for every sift-up and sift-down comparison instead of natural ordering, letting you prioritize arbitrary objects (tasks by deadline, events by timestamp, graph edges by weight) without wrapping them in a Comparable type.
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{1, 5});
pq.offer(new int[]{2, 3});
System.out.println(pq.poll()[0]); // 2 -- its second field (3) is the smallestQ51. How does BFS (breadth-first search) use a queue, and why?
A: BFS explores a graph or tree level by level: it enqueues the start node, then repeatedly dequeues a node, processes it, and enqueues all of its unvisited neighbors. A queue's FIFO order guarantees that all nodes at distance k from the start are dequeued (and their neighbors at distance k+1 enqueued) before any node at distance k+1 is processed — this level-by-level guarantee is exactly what gives BFS its shortest-path property in unweighted graphs, and it would break if a stack (DFS-style) were used instead.
void bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}Q52. How do you perform a level-order traversal of a binary tree using a queue?
A: Enqueue the root, then repeatedly process one full "level" at a time: capture the queue's current size before the inner loop (this is exactly the number of nodes at the current level), dequeue that many nodes, record their values, and enqueue their children. Starting a fresh inner loop for each captured size cleanly separates levels without needing to track depth explicitly.
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}Q53. How do you find the shortest path between two nodes in an unweighted graph using BFS?
A: Run standard BFS from the source while recording, for every newly discovered node, the node it was reached from (its "parent" in the BFS tree) and its distance (parent's distance + 1). Because BFS discovers nodes strictly in order of increasing distance, the first time the target node is dequeued, its recorded distance is guaranteed minimal; walking the parent pointers backward from the target reconstructs the actual shortest path. This is O(V+E) time.
Q54. How do you detect a cycle in an undirected graph using BFS?
A: Run BFS while tracking, for each node, the parent node it was reached from. If BFS ever encounters a neighbor that is already visited and is not that node's parent, a cycle exists — you've reached an already-discovered node through a second, different path. This runs in O(V+E) time and correctly ignores the "trivial" edge back to the immediate parent, which is not a cycle in an undirected graph.
Q55. What is the fundamental difference between BFS's queue usage and DFS's stack usage?
A: Both algorithms maintain a frontier of nodes to visit next, but a queue (FIFO) makes BFS expand the frontier breadth-first — visiting all neighbors of the current level before going deeper — while a stack (LIFO), or equivalently recursion's implicit call stack, makes DFS plunge as deep as possible along one path before backtracking. This single data-structure swap changes the entire exploration order and is why BFS finds shortest paths in unweighted graphs while DFS does not.
Q56. How do you implement DFS iteratively using an explicit stack instead of recursion?
A: Push the start node onto a stack. Repeatedly pop a node; if it hasn't been visited, mark it visited, process it, and push all of its neighbors (visited or not — the check happens on pop, not on push, in this simple variant). This mimics the order recursive DFS would visit nodes in (though not always the identical order, since sibling order depends on push order), while avoiding the JVM call-stack depth limit that deep recursive DFS can hit on large graphs.
void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.contains(node)) continue;
visited.add(node);
for (int neighbor : graph.get(node)) {
stack.push(neighbor);
}
}
}Q57. How do you design an LRU (Least Recently Used) cache?
A: The classic design combines a HashMap (for O(1) key lookup) with a doubly linked list (for O(1) reordering) that keeps entries ordered from most- to least-recently used. On get, look up the node via the map and move it to the front of the list; on put when at capacity, evict the node at the back of the list (the least recently used) and remove it from the map too. In Java, LinkedHashMap with access-order enabled provides this behavior out of the box, avoiding a hand-rolled doubly linked list.
class LRUCache {
private final int capacity;
private final LinkedHashMap<Integer, Integer> map;
LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > LRUCache.this.capacity;
}
};
}
int get(int key) { return map.getOrDefault(key, -1); }
void put(int key, int value) { map.put(key, value); }
}Q58. Why is a doubly linked list combined with a HashMap the classic way to implement LRU cache in O(1)?
A: The HashMap gives O(1) lookup of any entry by key, but a plain HashMap has no notion of usage order. A doubly linked list gives O(1) removal and re-insertion of a node at either end given a direct node reference (no traversal needed), which a singly linked list cannot do at the tail. Together, the map stores key-to-node references for O(1) access, and the list maintains recency order for O(1) "move to front" and "evict from back" — neither structure alone can deliver both capabilities in O(1).
Q59. How do you design an LFU (Least Frequently Used) cache?
A: Maintain a HashMap from key to (value, frequency), a HashMap from frequency count to a doubly linked list (or LinkedHashSet) of keys currently at that frequency (preserving recency within a frequency for tie-breaking), and a pointer to the current minimum frequency. On access, move the key from its old frequency bucket to the next one up, updating the minimum-frequency pointer if its old bucket becomes empty; on eviction, remove the least-recently-used key from the minimum-frequency bucket. This achieves O(1) get and put, at the cost of considerably more bookkeeping than LRU.
Q60. How does LinkedHashMap's access-order mode simplify LRU cache implementation in Java?
A: Constructing a LinkedHashMap with the three-argument constructor and accessOrder = true makes every get and put automatically move the affected entry to the end of its internal iteration order, exactly mirroring "most recently used goes to the front" without any manual linked-list surgery. Overriding removeEldestEntry to return true once size() > capacity makes the map self-evict the least-recently-used entry (the head of iteration order) on every insertion that exceeds capacity, giving a complete LRU cache in a handful of lines.
Q61. What is a BlockingQueue and how does it support the producer-consumer pattern?
A: A BlockingQueue is a thread-safe queue that adds blocking semantics: a consumer calling take() on an empty queue simply waits until an item is available instead of throwing or returning null, and a producer calling put() on a full bounded queue waits until space frees up. This built-in coordination eliminates the need for manual wait/notify boilerplate, making it the standard building block for producer-consumer pipelines where producer and consumer threads run at different, varying speeds.
Q62. What is the difference between ArrayBlockingQueue and LinkedBlockingQueue?
A: ArrayBlockingQueue is backed by a fixed-size circular array, always bounded, using a single lock for both put and take operations (so producers and consumers can briefly contend for the same lock). LinkedBlockingQueue is backed by linked nodes, optionally unbounded (or bounded if a capacity is given), and uses two separate locks internally — one for the head, one for the tail — allowing a put and a take to proceed concurrently without contending for the same lock, generally giving it higher throughput under contention at the cost of per-node allocation overhead.
Q63. How do put() and take() behave differently from offer() and poll() on a BlockingQueue?
A: put() and take() block indefinitely — a producer calling put() on a full queue waits until space is available, and a consumer calling take() on an empty queue waits until an item arrives. offer() and poll() (no-argument versions) instead return immediately — offer() returns false if there's no space, poll() returns null if there's nothing to take — and both also have timed overloads (offer(item, timeout, unit)) that block only up to a bound before giving up.
Q64. How do you implement a simple producer-consumer example using BlockingQueue?
A: Share a single BlockingQueue instance between one or more producer threads and one or more consumer threads. Producers call put() to add work items, blocking automatically if the queue is at capacity, applying natural backpressure; consumers call take() in a loop, blocking automatically when there's nothing to process. No explicit locks, conditions, or manual signaling are needed — the queue itself handles all synchronization internally.
class ProducerConsumerDemo {
private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
void produce() throws InterruptedException {
for (int i = 0; i < 100; i++) {
queue.put(i); // blocks when the queue is full
}
}
void consume() throws InterruptedException {
while (true) {
int value = queue.take(); // blocks when the queue is empty
process(value);
}
}
void process(int value) { /* work */ }
}Q65. What is a SynchronousQueue and when would you use one?
A: A SynchronousQueue has zero internal capacity — every put() must wait for a matching take() to occur (and vice versa), effectively handing an item directly from one thread to another with no buffering in between. It's used when you want a direct rendezvous/handoff rather than a buffer, such as in Executors.newCachedThreadPool()'s internal work queue, where tasks should either find an idle thread immediately or trigger creation of a new one, rather than queuing up.
Q66. What is a PriorityBlockingQueue and how does it differ from a regular PriorityQueue?
A: PriorityBlockingQueue is an unbounded, thread-safe blocking queue that orders elements by priority (like PriorityQueue) rather than insertion order, using an internal lock to guard the heap. Because it's unbounded, put() never blocks on a full-queue condition (there is none), but take() still blocks when the queue is empty — making it useful for multi-threaded task schedulers where the highest-priority pending task should always be processed next.
Q67. What is a DelayQueue and what problem does it solve?
A: A DelayQueue holds elements that implement Delayed, each specifying how long it must remain in the queue before becoming eligible for retrieval; take() blocks until the head element's delay has expired. This is the natural fit for scheduling tasks to run at a future time — retry-with-backoff logic, cache-entry expiration, or delayed job execution — without a caller having to manually poll and check timestamps.
Q68. How do you find the maximum in every sliding window of size k using a deque?
A: Maintain a deque of indices whose corresponding values are in decreasing order. For each new index, first evict indices from the front that have fallen outside the current window; then evict indices from the back whose values are smaller than the current value (they can never be the max again); finally add the current index to the back. The window's maximum is always the value at the front. This is O(n) total, since each index enters and leaves the deque at most once.
int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>(); // indices, decreasing values
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
deque.offerLast(i);
if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}Q69. How do you reverse a queue using recursion?
A: Dequeue the front element and hold it in a local variable; if the queue is now empty, enqueue that element back and return (base case). Otherwise, recursively reverse the remaining (smaller) queue first, and only after that recursive call returns, enqueue the held element. Because the held element is added back after the recursive reversal completes, it ends up at the back — effectively reversing the whole queue using the call stack as auxiliary storage, in O(n) time and O(n) recursion depth.
Q70. How do you reverse only the first k elements of a queue while leaving the rest in order?
A: Dequeue the first k elements into an auxiliary stack (a stack naturally reverses order), then dequeue and re-enqueue those k values from the stack back into the queue (now in reversed order at the back), and finally rotate the remaining n-k original elements from the front to the back so the whole queue's relative structure — reversed first k, followed by the original rest, in original queue position — is preserved. This runs in O(n) time using O(k) auxiliary space.
void reverseFirstK(Queue<Integer> queue, int k) {
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < k; i++) stack.push(queue.poll());
while (!stack.isEmpty()) queue.offer(stack.pop());
int rest = queue.size() - k;
for (int i = 0; i < rest; i++) queue.offer(queue.poll());
}Q71. How do you check whether a queue's elements can be rearranged into another target queue's order using only an auxiliary stack?
A: Repeatedly compare the front of the input queue to the front of the target queue: if they match, dequeue both; otherwise, if the auxiliary stack's top matches the target's front, pop and consume it; otherwise push the input queue's front onto the stack. If at any point neither the queue's front nor the stack's top can supply the target's next expected value, the rearrangement is impossible. This models real constraints like railway carriage re-shuffling using a single siding (the stack).
Q72. How do you interleave the first and second halves of a queue with an even number of elements?
A: Push the first half's elements onto an auxiliary stack (reversing them), then pop the stack while alternately taking from the stack (originally first-half elements) and from the queue's current front (now the second half), re-enqueuing each in alternating order. This produces the classic "interleave" pattern (1,2,3,4,5,6 → 1,4,2,5,3,6) in O(n) time using O(n/2) extra space for the stack.
Q73. How do you generate the first n binary representations (as strings) using a queue?
A: Seed a queue with the string "1" (the first binary number). Repeat n times: dequeue the front string, record it as the next answer, then enqueue that string with "0" appended and again with "1" appended (the two children in the implicit binary-number tree). Because the queue is FIFO, this naturally produces binary strings in increasing numeric order without any sorting, in O(n) time overall.
List<String> generateBinary(int n) {
List<String> result = new ArrayList<>();
Queue<String> queue = new LinkedList<>();
queue.offer("1");
for (int i = 0; i < n; i++) {
String front = queue.poll();
result.add(front);
queue.offer(front + "0");
queue.offer(front + "1");
}
return result;
}Q74. How do you implement a "hit counter" that reports the number of hits in the last 5 minutes?
A: Maintain a queue of timestamps, one per recorded hit. On each new hit, enqueue its timestamp; then, before answering a count query (or before each new hit), dequeue from the front any timestamps older than 300 seconds relative to the current time, since a FIFO queue keeps timestamps in increasing order and the oldest ones always expire first. The count is simply the queue's remaining size, giving amortized O(1) work per hit despite the expiry cleanup.
Q75. How do you compute a moving average from a stream of numbers using a deque?
A: Maintain a deque holding at most windowSize recent values along with a running sum. On each new value, add it to the back and to the running sum; if the deque now exceeds the window size, remove the front value and subtract it from the running sum. The moving average is always sum / deque.size(), computed in O(1) per new value rather than re-summing the whole window each time.
class MovingAverage {
private final Deque<Integer> window = new ArrayDeque<>();
private final int size;
private double sum = 0;
MovingAverage(int size) { this.size = size; }
double next(int val) {
if (window.size() == size) sum -= window.pollFirst();
window.offerLast(val);
sum += val;
return sum / window.size();
}
}Q76. How does a queue-based cooldown counter help solve task-scheduling problems with a required gap between identical tasks?
A: Track how many time slots remain before each task type becomes eligible again using a small queue or map of "task type, next-eligible-time" pairs, incrementing a global clock one slot at a time. At each slot, check whether the currently due task has completed its cooldown (based on when it was last scheduled), and if not, either idle or schedule a different eligible task. This greedy, queue-driven simulation naturally enforces the minimum gap without needing to pre-compute an entire schedule combinatorially.
Q77. How do you remove duplicate letters from a string, keeping the lexicographically smallest possible result, using a stack?
A: Precompute the last occurrence index of every character. Scan left to right, skipping characters already placed on the stack; for a new character, pop the stack while its top is greater than the current character and that top character still occurs again later in the string (so removing it now is safe). Push the current character and mark it as placed. This greedily keeps the result as small as possible while guaranteeing every distinct character still appears once, in O(n) time.
String removeDuplicateLetters(String s) {
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++) lastIndex[s.charAt(i) - 'a'] = i;
boolean[] onStack = new boolean[26];
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (onStack[c - 'a']) continue;
while (!stack.isEmpty() && stack.peek() > c && lastIndex[stack.peek() - 'a'] > i) {
onStack[stack.pop() - 'a'] = false;
}
stack.push(c);
onStack[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
for (char c : stack) sb.append(c);
return sb.reverse().toString();
}Q78. How do you decode a nested run-length-encoded string like "3[a2[c]]" using a stack?
A: Keep two stacks — one for pending repeat counts and one for the string built so far before each '['. On a digit, accumulate the current number; on '[', push the current count and the current partial string, then reset both; on ']', pop the count and the outer partial string, append the just-finished inner string repeated that many times to the outer string, and make that the new "current" string; on any other character, append it to the current string. The final current string is the fully decoded result, computed in O(n × maxRepeat) time.
String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> stringStack = new ArrayDeque<>();
StringBuilder current = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '[') {
countStack.push(num);
stringStack.push(current);
current = new StringBuilder();
num = 0;
} else if (c == ']') {
StringBuilder decoded = stringStack.pop();
int repeat = countStack.pop();
for (int i = 0; i < repeat; i++) decoded.append(current);
current = decoded;
} else {
current.append(c);
}
}
return current.toString();
}Q79. How do you solve the Asteroid Collision problem using a stack?
A: Process asteroids left to right, maintaining a stack of surviving right-moving asteroids. A new left-moving asteroid can only collide with a right-moving one already on the stack top; while it's larger, pop (destroy) the stack top, and if they're exactly equal, pop and also cancel the new asteroid. Only push the current asteroid if it survives all such collisions. This models the physical rule that collisions only happen between a right-moving asteroid behind a left-moving one, in O(n) amortized time.
int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<>();
for (int a : asteroids) {
boolean alive = true;
while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
if (stack.peek() < -a) { stack.pop(); continue; }
else if (stack.peek() == -a) { stack.pop(); }
alive = false;
}
if (alive) stack.push(a);
}
int[] result = new int[stack.size()];
for (int i = result.length - 1; i >= 0; i--) result[i] = stack.pop();
return result;
}Q80. How do you simplify a Unix-style file path (e.g., "/a/./b/../../c/") using a stack?
A: Split the path on '/'. Ignore empty segments and "." (current directory, no effect); on ".." (parent directory), pop the stack if it isn't empty (go up one level); on any real directory name, push it. The stack, read from bottom to top, is the simplified absolute path, joined with '/'. This correctly handles arbitrary combinations of nesting and backtracking in a single O(n) pass.
String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue;
if (part.equals("..")) {
if (!stack.isEmpty()) stack.pop();
} else {
stack.push(part);
}
}
StringBuilder sb = new StringBuilder();
for (String dir : stack) sb.insert(0, "/" + dir); // prepend to restore order
return sb.length() == 0 ? "/" : sb.toString();
}Q81. What is stack permutation validation, and how would you check if one sequence could result from pushing another sequence onto a stack and popping in a different order?
A: Given an input push order and a proposed output (pop) order, simulate it with an actual stack: push elements from the input one at a time, and after each push, pop from the stack (comparing to the next expected output value) as many times as possible while it matches. If, after processing all input, the stack is empty, the output order is achievable; otherwise it isn't. This runs in O(n) time and directly validates feasibility without generating all permutations.
Q82. What is the "Stack of Plates" (SetOfStacks) design problem, and how would you implement it?
A: The problem asks you to simulate a single logical stack that is internally composed of multiple fixed-capacity sub-stacks, automatically creating a new sub-stack when the current one is full, and supporting a popAt(index) operation that pops from a specific sub-stack rather than only the last one. Implement it with a list of stacks; push checks if the last sub-stack is full and creates a new one if so; a plain pop operates on the last sub-stack, removing it from the list if it becomes empty (unless you choose to leave gaps, a design trade-off interviewers often probe).
Q83. What is the "Celebrity problem" and how can a stack help solve it?
A: Given a "knows" relation among n people, a celebrity is someone everyone else knows but who knows no one else; the task is to find them (if one exists) faster than checking all pairs. A stack-based approach pushes all candidates, then repeatedly pops two candidates and eliminates one based on a single "does A know B" query — the loser of each pairwise elimination can never be the celebrity — leaving one final candidate to verify in a full pass. This achieves O(n) queries overall instead of the O(n²) brute-force check of every pair.
Q84. How do you sort a stack using only stack operations (push, pop, peek, isEmpty) and one auxiliary stack?
A: Repeatedly pop from the input stack; for each popped value, pop elements off a second "sorted" stack back onto the input stack as long as they're greater than the popped value, then push the value onto the sorted stack. After the input stack empties, the sorted stack holds all values in order (largest on top). This is O(n²) time in the worst case, since each element may be moved back and forth multiple times, but uses no data structure besides two stacks.
Deque<Integer> sortStack(Deque<Integer> input) {
Deque<Integer> sorted = new ArrayDeque<>();
while (!input.isEmpty()) {
int temp = input.pop();
while (!sorted.isEmpty() && sorted.peek() > temp) {
input.push(sorted.pop());
}
sorted.push(temp);
}
return sorted; // top of 'sorted' holds the largest element
}Q85. How do you find the maximum nesting depth of valid parentheses in a string?
A: You don't need an actual stack's contents, only its size at every point: maintain a counter that increments on every '(' and decrements on every ')', tracking the maximum value the counter ever reaches. That maximum is the deepest nesting level, computed in O(n) time and O(1) space, since a real stack's depth at any moment equals exactly this running counter.
Q86. How do you validate whether a given push sequence and pop sequence are consistent with a single stack (Validate Stack Sequences)?
A: Simulate an actual stack: iterate the push sequence, pushing each value, and after every push, check whether the stack's top matches the next value expected in the pop sequence — if so, pop it and advance the pop-sequence pointer, repeating while matches continue. If, after all pushes are exhausted, the stack has been fully drained by matching pops, the sequences are consistent. This is O(n) time since every element is pushed once and popped at most once.
boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<>();
int j = 0;
for (int value : pushed) {
stack.push(value);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}Q87. Why is recursion described as using an "implicit stack," and how does this relate to StackOverflowError?
A: Every recursive call pushes a new stack frame onto the JVM's call stack, holding that call's local variables, parameters, and return address; returning from the call pops that frame off. This is functionally identical to an explicit push/pop stack, just managed automatically by the runtime. Because the call stack has a fixed maximum size (configurable via -Xss), recursion that goes too deep — often from a missing or incorrect base case — exhausts that space and throws StackOverflowError, the same failure mode as overflowing a hand-rolled fixed-size array stack.
Q88. How would you convert a recursive algorithm into an iterative one using an explicit stack?
A: Replace each recursive call with pushing the "next state to process" (whatever arguments that call would have received) onto an explicit stack, and replace the top-level recursive kickoff with a loop that pops a state, processes it, and pushes any further states that a recursive call would have made. Where the recursive version had multiple recursive calls per invocation (like tree traversal's left and right children), push both, in the order that reproduces the desired visiting order once popped in LIFO fashion. This removes the JVM call-stack depth limit at the cost of managing the stack yourself.
Q89. What is the time and space complexity difference between recursion and using an explicit stack for the same traversal?
A: Time complexity is typically identical between the two — both visit the same nodes the same number of times, so both are, for example, O(n) for a tree traversal. The difference is in space characteristics: recursion's implicit stack is bounded by the JVM's configured thread stack size and can overflow on deep inputs regardless of available heap memory, while an explicit stack lives on the heap, is limited only by available memory (typically far larger), and can be resized dynamically like any collection.
Q90. How would you implement an undo/redo feature using two stacks?
A: Maintain an "undo" stack and a "redo" stack. Every new action pushes onto the undo stack and clears the redo stack (a new action invalidates any previously undone redo history). "Undo" pops the most recent action off the undo stack, reverses its effect, and pushes it onto the redo stack; "redo" pops from the redo stack, re-applies the action, and pushes it back onto the undo stack. This gives O(1) undo and redo per step, matching how most editors implement command history.
Q91. How do you check balanced brackets in a string that also contains other characters (letters, digits, punctuation) that should be ignored?
A: Use the same stack-based algorithm as plain bracket validation, but simply skip over (do nothing for) any character that is not one of the six bracket characters — only push on an opening bracket and only pop/compare on a closing bracket. This keeps the algorithm O(n) time, O(n) space, and is exactly the approach needed for validating balanced brackets embedded in real source code or markup.
Q92. How do you compute the "score" of a fully balanced parentheses string, where "()" scores 1 and "AB" concatenated scores A+B, and "(A)" scores 2*A?
A: Maintain a stack of partial scores, seeded with a 0 at the bottom to accumulate the top-level total. On '(', push a fresh 0 (a new nested scope starting empty). On ')', pop the just-closed scope's score: if it was 0 (an empty "()"), its contribution is 1; otherwise its contribution is double that inner score (the "(A)" rule); add that contribution to the new top of the stack (the enclosing scope). The stack's final single remaining value is the total score. This is O(n) time, O(n) space.
int scoreOfParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(0);
} else {
int inner = stack.pop();
int score = (inner == 0) ? 1 : 2 * inner;
stack.push(stack.pop() + score);
}
}
return stack.pop();
}Q93. How does browser back/forward navigation relate to stack usage?
A: Visiting a new page pushes the current page onto a "back" stack; clicking "back" pops that stack, pushing the page you're leaving onto a "forward" stack so it can be returned to; clicking "forward" pops the forward stack, pushing the current page back onto the back stack. Navigating to a brand-new page (not via back/forward) typically clears the forward stack, since that history branch is no longer reachable — the same invalidation rule used in undo/redo designs.
Q94. Why would a print job spooler naturally be modeled with a queue rather than a stack?
A: Print jobs should be printed in the order they were submitted — the first document sent should generally print first, which is exactly FIFO ordering. A stack would print the most recently submitted document first (LIFO), meaning an earlier job could be starved indefinitely if new jobs keep arriving, which is unfair and not how users expect a print queue to behave. This is why operating systems literally call it a "print queue."
Q95. How is a queue used in operating system CPU scheduling, such as round-robin scheduling?
A: Round-robin scheduling maintains a queue of ready processes; the scheduler dequeues the process at the front, lets it run for one fixed time quantum, and if it hasn't finished, re-enqueues it at the back before dequeuing the next process. This FIFO cycling guarantees every process gets a fair, bounded share of CPU time in turn, and the queue's ordering directly determines scheduling fairness — a stack would repeatedly favor the most recently added process instead.
Q96. Since Deque supports both stack and queue operations, what determines whether a given usage is "really" a stack or a queue?
A: It's determined entirely by which end you insert at versus which end you remove from, not by the underlying class. Using push/pop (both operate on the front) gives LIFO stack behavior; using offer/poll (insert at the back, remove from the front) gives FIFO queue behavior. The same ArrayDeque instance's internal circular-array mechanics support both access patterns equally well — the abstraction you get is a matter of which method names you choose to call.
Q97. Why must ArrayDeque never be used from multiple threads without external synchronization, and what would you use instead?
A: ArrayDeque performs no internal locking or volatile-field coordination, so concurrent modification from multiple threads (even two threads only reading and writing at opposite ends) can corrupt its internal head/tail indices or backing array, producing lost updates or exceptions with no warning. For a thread-safe stack or queue, use ConcurrentLinkedDeque (non-blocking, lock-free via CAS) or a BlockingQueue implementation like ArrayBlockingQueue or LinkedBlockingQueue when you also need blocking put/take semantics.
Q98. What is ConcurrentLinkedQueue and how does it achieve thread safety without locking?
A: ConcurrentLinkedQueue is an unbounded, non-blocking, thread-safe FIFO queue built on a linked-node structure where enqueue and dequeue use compare-and-swap (CAS) operations on the head and tail references instead of synchronized blocks or explicit locks. This lets multiple threads enqueue and dequeue concurrently with high throughput and no thread ever blocking waiting for a lock, at the cost of methods like size() being O(n) (it must traverse the list) rather than O(1).
Q99. How do you check whether a binary tree is a "complete" binary tree using BFS?
A: Run a level-order BFS, but enqueue every child slot including nulls (rather than skipping them). If a null is dequeued, remember that a gap has been seen; if any non-null node is dequeued after that point, the tree is not complete, because a complete binary tree can only have gaps at the very end of its last level. If BFS finishes without a non-null node appearing after a gap, the tree is complete. This runs in O(n) time.
boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean seenNull = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
seenNull = true;
} else {
if (seenNull) return false; // non-null node found after a gap
queue.offer(node.left);
queue.offer(node.right);
}
}
return true;
}Q100. How do you implement a zigzag (alternating direction) level-order traversal of a binary tree using a deque?
A: Perform standard level-order traversal with a queue to discover each level's nodes, but collect each level's values into a small Deque instead of a plain list: on left-to-right levels, append new values to the back; on right-to-left levels, append new values to the front. Toggling this insertion side after every level produces the zigzag order without needing to reverse a completed list afterward, still in O(n) total time.
List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
Deque<Integer> level = new ArrayDeque<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) level.offerLast(node.val);
else level.offerFirst(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(new ArrayList<>(level));
leftToRight = !leftToRight;
}
return result;
}Q101. What is the time complexity of java.util.Stack's operations, and how does its Vector-based implementation affect performance under concurrency?
A: push, pop, and peek are all O(1) on java.util.Stack, same as any correct stack, but because it extends the legacy Vector class, every one of these methods is synchronized. In single-threaded code this adds needless lock acquisition/release overhead on every call; in multi-threaded code it does provide thread safety for individual operations, but composite operations (like "check isEmpty then pop") are still not atomic as a whole, so callers must still coordinate externally for correctness — meaning the synchronization mostly adds cost without eliminating the need for higher-level thread coordination.
Q102. How do you evaluate an arithmetic expression with nested parentheses and +, -, *, / using two stacks (operators and operands), without first converting to postfix?
A: Maintain an operand stack and an operator stack. Push numbers onto the operand stack as they're read; on '(', push it onto the operator stack; on ')', repeatedly apply the top operator to the top two operands until the matching '(' is popped and discarded; on any other operator, first apply any pending operators of equal or higher precedence (so *// resolve before a pending +/-), then push the new operator. After the scan, apply any remaining operators; the operand stack's last value is the answer. This evaluates directly in one pass, O(n) time, without materializing a postfix string.
int evaluate(String s) {
Deque<Integer> operands = new ArrayDeque<>();
Deque<Character> operators = new ArrayDeque<>();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
operands.push(num);
continue;
} else if (c == '(') {
operators.push(c);
} else if (c == ')') {
while (operators.peek() != '(') applyTop(operands, operators);
operators.pop();
} else if ("+-*/".indexOf(c) >= 0) {
while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
applyTop(operands, operators);
}
operators.push(c);
}
i++;
}
while (!operators.isEmpty()) applyTop(operands, operators);
return operands.pop();
}
// applyTop() pops one operator and two operands, applies the operator, and
// pushes the result; precedence() maps '+','-' to 1 and '*','/' to 2.Q103. How would you detect a "132 pattern" (i indices i<j<k with nums[i]<nums[k]<nums[j]) using a stack?
A: Scan from right to left while maintaining a monotonic stack of candidate "3" values (the middle, largest element of the pattern) and a running third value representing the best candidate for the smallest "1" position discovered by popping. Whenever the current value is smaller than third, a valid 132 pattern has been found; otherwise, pop all stack values smaller than the current value into third (they become candidates for the "1" role) before pushing the current value as a new "3" candidate. This runs in O(n) time despite tracking three roles simultaneously.
Q104. What is the difference between Queue.poll() and Queue.remove() when the queue is empty?
A: Both remove and return the head of the queue when elements are present, but they differ on an empty queue: poll() returns null to signal "nothing there," while remove() throws a NoSuchElementException. This mirrors the List convention where a "safe" query-style method returns a sentinel and a "strict" method throws, and the same pattern applies to peek() (returns null) versus element() (throws).
Q105. What is the difference between Queue.peek() and Queue.element()?
A: Both return (without removing) the head of the queue, but peek() returns null if the queue is empty, while element() throws a NoSuchElementException in that case. Choosing between them is a style decision about whether an empty queue is an expected, recoverable condition (use peek and check for null) or a programming error worth failing loudly on (use element).
Q106. Why does java.util.Queue not provide a direct index-based get(), unlike List?
A: The Queue interface deliberately models only ends-based access (front and, for Deque, also back) because that's the entire contract a FIFO/LIFO abstraction needs — allowing arbitrary index access would encourage code that bypasses the ordering discipline the data structure exists to enforce, and several Queue implementations (like LinkedList used as a queue) would make such access O(n) anyway. If you need indexed access, you likely want a List, not a Queue, and mixing the two abstractions in one usage is usually a sign the wrong data structure was chosen.
Q107. How do you implement a circular buffer (ring buffer), and how does it relate to a circular queue?
A: A circular buffer is a fixed-size array where a write pointer and read pointer both wrap around to index 0 via modulo arithmetic once they reach the end, letting the buffer be reused indefinitely without shifting data. This is exactly the mechanism a circular queue uses internally (front/rear wrapping via % capacity); the terms are often used interchangeably, though "circular buffer" is more common in streaming/IO contexts (audio buffers, network packet buffers) and "circular queue" more common in algorithmic/interview contexts.
Q108. How do you prevent producer starvation or consumer starvation when multiple threads share a bounded BlockingQueue?
A: A plain ArrayBlockingQueue/LinkedBlockingQueue already avoids indefinite starvation for basic put/take because waiting threads are released in a reasonably fair manner by the underlying lock's condition queues, but true FIFO fairness across waiting threads can be requested explicitly by passing fair = true to ArrayBlockingQueue's constructor, which uses a fair ReentrantLock at some throughput cost. Beyond that, ensuring consumers keep pace with producers (or applying backpressure/timeouts on offer) is an application-level concern the queue itself cannot fully solve.
Q109. How do you implement an iterative inorder traversal of a binary tree using an explicit stack?
A: Maintain a stack and a "current" pointer starting at the root. Repeatedly push the current node and move to its left child until there is no left child (this walks all the way down the left spine); then pop a node, record its value, and move "current" to that popped node's right child, repeating the whole process. This exactly mirrors what recursive inorder traversal's implicit call stack would do, in O(n) time and O(h) explicit stack space (h = tree height) instead of relying on the JVM's call stack.
List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}Q110. What common real-world scenarios call for a stack versus a queue, and how do you decide which to reach for?
A: Reach for a stack whenever the most recent thing matters most and must be undone or resolved first — function call frames, undo/redo, expression parsing, backtracking search, browser back history. Reach for a queue whenever fairness and arrival order matter — task scheduling, print spooling, BFS, message/event buffering, rate limiting over a time window. The deciding question is simply: "when I need to remove one item, should it be the one that arrived most recently (stack) or the one that has waited longest (queue)?"
Q111. Why is a monotonic-stack algorithm that contains a nested while loop still O(n) overall, rather than O(n²)?
A: Although the inner while loop can run multiple times per outer iteration, every element is pushed onto the stack exactly once across the entire algorithm and can therefore be popped at most once as well. Summing the total number of pop operations across all iterations is bounded by n (the total number of pushes), so the combined cost of every inner-loop execution, added up over the whole run, is O(n) — this is the standard amortized-analysis argument (sometimes called the "aggregate method") used to justify calling next-greater-element-style algorithms linear despite their nested-looking structure.
Q112. If you had to pick one Java class for general-purpose stack and queue needs in new code, which would it be, and why?
A: ArrayDeque, used either as a stack (via push/pop) or a FIFO queue (via offer/poll), covers both roles with O(1) amortized operations at either end, better cache locality than a linked structure, and no synchronization overhead. Reach for LinkedList only if you specifically need it to also behave as a List; reach for a BlockingQueue implementation only when you need cross-thread coordination; and avoid java.util.Stack entirely in new code, since ArrayDeque supersedes it in every respect the JDK documentation itself calls out.
Post a Comment
Add