Stacks: Cracking the Coding Interview

Question

Accepted Answer

Stacks: Cracking the Coding Interview

Stacks are one of the fundamental data structures in computer science, and they are often used to solve problems that require managing data in a Last-In-First-Out (LIFO) order. Whether it’s dealing with the function call stack in recursion, parsing expressions, or performing undo operations in software, stacks have a wide range of applications in real-world programming.

In coding interviews, stacks are commonly tested for their ability to manage sequences of data and efficiently solve problems that require sequential access. Understanding how stacks work, and how to apply them effectively, is essential for acing technical interviews.

In this article, we’ll explore the core concept of stacks, delve into practical applications, and look at common interview problems that use stacks.

What is a Stack?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning that the most recently added element is the first one to be removed. You can think of it like a stack of plates where you can only add or remove the plate from the top.

A stack supports two primary operations:

Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.

Other important operations often associated with stacks include:

Peek (or Top): View the element at the top of the stack without removing it.
IsEmpty: Check whether the stack is empty.
Size: Get the number of elements currently in the stack.

Stack Operations Example

Let’s implement a basic stack in Python:

class Stack:
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return "Stack is empty"
    
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "Stack is empty"
    
    def is_empty(self):
        return len(self.stack) == 0
    
    def size(self):
        return len(self.stack)

Example usage:

s = Stack()
s.push(10)
s.push(20)
s.push(30)

print(s.pop())  #  Output: 30
print(s.peek())  #  Output: 20
print(s.is_empty())  #  Output: False
print(s.size())  #  Output: 2

Applications of Stacks

Stacks are used in many practical scenarios and often appear in coding interviews. Some common uses include:

Function Call Stack: When a function is called, its context (local variables, return address) is saved onto the stack. When the function finishes, the context is popped off the stack, and the program returns to the previous function call.
Expression Evaluation and Parsing: Stacks are frequently used to evaluate arithmetic expressions, especially those involving parentheses or operators with different precedence levels.
Undo/Redo Operations: In text editors and graphics programs, stacks are used to manage the state for undo and redo actions.
Depth-First Search (DFS): DFS in graph traversal is typically implemented using a stack to keep track of nodes to visit.

Understanding these applications and knowing how to apply stacks efficiently is key to solving interview problems involving this data structure.

Common Interview Problems Involving Stacks

Let’s dive into some common problems that involve stacks, along with their solutions.

Problem 1: Balanced Parentheses

Problem: Given a string containing only parentheses ((), {}, []), determine if the input string is valid. An input string is valid if:

Open brackets must be closed by the same type of bracket.
Open brackets must be closed in the correct order.

Example:

Input: "()" → Output: True
Input: "()[]{}" → Output: True
Input: "(]" → Output: False

Solution:

We can use a stack to solve this problem. For each character:

If it’s an opening bracket ((, {, or [), we push it onto the stack.
If it’s a closing bracket (), }, or ]), we check if the top of the stack contains the corresponding opening bracket. If it does, we pop the stack; if not, the string is invalid.

def is_valid(s):
    stack = []
    #  Define a mapping of closing to opening parentheses
    parentheses_map = {")": "(", "}": "{", "]": "["}
    
    for char in s:
        if char in parentheses_map:  #  If it's a closing bracket
            top_element = stack.pop() if stack else '#'
            if parentheses_map[char] != top_element:
                return False
        else:  #  If it's an opening bracket
            stack.append(char)
    
    return not stack  #  Stack should be empty if all brackets were matched

Explanation:

Time complexity: O(n), where n is the length of the string, because we process each character once.
Space complexity: O(n) for the stack, in the worst case when the string consists only of opening parentheses.

Problem 2: Next Greater Element

Problem: Given an array of integers, for each element in the array, find the next greater element that comes after it in the array. If no such element exists, output -1.

Example:

Input: [4, 5, 2, 10] → Output: [5, 10, 10, -1]

Solution:

We can use a stack to keep track of the elements for which we haven’t yet found the next greater element. As we iterate over the array:

For each element, we check the stack to see if it’s smaller than the current element. If so, we pop the stack and update the result for those elements.
We push the current element onto the stack.

def next_greater_element(nums):
    stack = []
    result = [-1] * len(nums)
    
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

Explanation:

Time complexity: O(n), where n is the number of elements in the array. Each element is pushed and popped from the stack at most once.
Space complexity: O(n) for the stack and the result array.

Problem 3: Evaluate Reverse Polish Notation (RPN)

Problem: Evaluate an expression given in Reverse Polish Notation (RPN). Valid operators are +, -, *, and /.

Example:

Input: ["2", "1", "+", "3", "*"] → Output: 9
Input: ["4", "13", "5", "/", "+"] → Output: 6

Solution:

We can use a stack to evaluate the expression. For each token:

If it’s a number, push it onto the stack.
If it’s an operator, pop the two top numbers, apply the operator, and push the result back onto the stack.

def eval_rpn(tokens):
    stack = []
    
    for token in tokens:
        if token in ["+", "-", "*", "/"]:
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            elif token == "/":
                stack.append(int(a / b))  #  Use integer division for truncation
        else:
            stack.append(int(token))
    
    return stack.pop()

Explanation:

Time complexity: O(n), where n is the number of tokens, since we process each token exactly once.
Space complexity: O(n), as we store the intermediate results in the stack.

Problem 4: Min Stack

Problem: Design a stack that supports the following operations:

push(x): Push element x onto the stack.
pop(): Removes the element on the top of the stack.
top(): Get the top element.
get_min(): Retrieve the minimum element in the stack.

Solution:

We can use two stacks: one for the regular stack and another for tracking the minimum values.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val):
        self.stack.append(val)
        #  If min_stack is empty or the current value is smaller than the current minimum, push it onto min_stack
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self):
        if self.stack:
            val = self.stack.pop()
            #  If the popped value is the same as the current minimum, pop from min_stack as well
            if val == self.min_stack[-1]:
                self.min_stack.pop()
            return val
    
    def top(self):
        return self.stack[-1] if self.stack else None
    
    def get_min(self):
        return self.min_stack[-1] if self.min_stack else None

Explanation:

Time complexity: O(1) for all operations—push, pop, top, and get_min.
Space complexity: O(n) for the two stacks.

Conclusion

Stacks are one of the most important data structures to master for coding interviews. They help solve a wide variety of problems, from checking balanced parentheses to evaluating expressions and performing graph traversals. By understanding how to implement a stack and applying it to problems, you can significantly enhance your problem-solving skills.

When preparing for coding interviews, make sure to practice problems involving stacks, understand their applications, and optimize your solutions to handle edge cases. Mastery of this data structure will give you an edge in technical interviews and prepare you for real-world programming challenges.

Stacks: Cracking the Coding Interview