Frequently Asked Stack Interview Questions

Q: Stack with Function min()


Design a stack that supports getMin() in O(1) time and O(1) extra space

Q: Implement two stacks in an array


Create a data structure twoStacks that represents two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements. Following functions must be supported by twoStacks.

push1(int x) –> pushes x to first stack

push2(int x) –> pushes x to second stack

pop1() –> pops an element from first stack and return the popped element

pop2() –> pops an element from second stack and return the popped element

Implementation of twoStack should be space efficient.

Q: Push and Pop Sequences of Stacks


Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.

Q: Infix to Postfix Conversion using Stack


Given an expression (a+(b-c)/d) convert this expression into postfix expression

Q: The Stock Span Problem


We are given a list of prices of a stock for N number of days. We need to find stock span for each day. Span is defined as number of consecutive days before the given day where the price of stock was less than or equal to price at given day. For example, {100, 60,70,65, 80, 85} span for each day will be {1, 1, 2, 1, 4, 5}.

Q: Next Greater Element


Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Q: Check for balanced parentheses in an expression


Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Q: Celebrity problem


You have a room with n people. A celebrity walks in. Everyone knows the celebrity, the celebrity knows no one. Non-celebrities may/may not know anyone in the room. Give an algorithm to find the celebrity. Discuss the complexity.

Q: Expression Evaluation


Evaluate an expression represented by a String. Expression can contain parentheses, you can assume parentheses are well-matched. For simplicity, you can assume only binary operations allowed are +, -, *, and /.

Q: Implement Queue using Stacks


We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

Q: Design a stack with operations on middle element


How to implement a stack which will support following operations in O(1) time complexity?

1) push() which adds an element to the top of stack.

2) pop() which removes an element from top of stack.

3) findMiddle() which will return middle element of the stack.

4) deleteMiddle() which will delete the middle element.

Push and pop are standard stack operations.