Day 4 Python 2024

Stacks and Queues in Python

Stacks and queues are fundamental data structures in computer science. They are essential for managing data in specific orders and solving various algorithmic problems. Below is a comprehensive guide on stacks and queues, including their implementation, operations, and applications in Python.

Stacks

What is a Stack?

A stack is a collection of elements that follows the Last-In-First-Out (LIFO) principle. The last element added to the stack is the first one to be removed.

Basic Operations

Push: Add an element to the top of the stack.
Pop: Remove the top element from the stack.
Peek: Retrieve the top element without removing it.
isEmpty: Check if the stack is empty.

Implementing a Stack in Python

Python lists can be used to implement a stack, as they provide methods to append and pop elements.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.is_empty())  # Output: False

Applications of Stacks

Expression evaluation and syntax parsing: Used in compilers and interpreters.
Backtracking: Algorithms that revert to previous states.
Depth-First Search (DFS): In graph traversal.
Undo mechanism in text editors.

Queues

What is a Queue?

A queue is a collection of elements that follows the First-In-First-Out (FIFO) principle. The first element added to the queue is the first one to be removed.

Basic Operations

Enqueue: Add an element to the end of the queue.
Dequeue: Remove the first element from the queue.
Peek: Retrieve the first element without removing it.
isEmpty: Check if the queue is empty.

Implementing a Queue in Python

While Python lists can be used to implement a queue, using collections.deque is more efficient for queue operations.

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Example usage:
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.peek())  # Output: 2
print(queue.is_empty())  # Output: False

Applications of Queues

Order processing systems: Handling tasks in order of arrival.
Breadth-First Search (BFS): In graph traversal.
Print queue management: Managing print jobs in order.
Task scheduling: In operating systems.

Important Concepts and Interview Preparation

Stacks

Reversing Data: Due to LIFO nature, stacks can reverse the order of data.
Recursion: The call stack is an implicit stack used for function calls and recursion.
Balancing Symbols: Used to check balanced parentheses in expressions.

Queues

Producer-Consumer Problem: Queues can manage tasks between producer and consumer processes.
Round-Robin Scheduling: Used in operating systems for task scheduling.
Buffering: Queues are used in buffering data streams.

Practical Examples

Example 1: Balanced Parentheses using Stack

def is_balanced(expression):
    stack = Stack()
    matching_parentheses = {')': '(', '}': '{', ']': '['}

    for char in expression:
        if char in matching_parentheses.values():
            stack.push(char)
        elif char in matching_parentheses.keys():
            if stack.is_empty() or stack.pop() != matching_parentheses[char]:
                return False
    return stack.is_empty()

expression = "{[()]}"
print(is_balanced(expression))  # Output: True

expression = "{[(])}"
print(is_balanced(expression))  # Output: False

Example 2: Level Order Traversal of a Binary Tree using Queue

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def level_order_traversal(root):
    if not root:
        return []

    queue = Queue()
    queue.enqueue(root)
    result = []

    while not queue.is_empty():
        current_node = queue.dequeue()
        result.append(current_node.value)

        if current_node.left:
            queue.enqueue(current_node.left)
        if current_node.right:
            queue.enqueue(current_node.right)

    return result

# Creating a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(level_order_traversal(root))  # Output: [1, 2, 3, 4, 5]

Example 3: Implementing a Min Stack

A min stack supports push, pop, and retrieving the minimum element in constant time.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        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 val == self.min_stack[-1]:
                self.min_stack.pop()
            return val
        return None

    def get_min(self):
        if self.min_stack:
            return self.min_stack[-1]
        return None

# Example usage:
min_stack = MinStack()
min_stack.push(3)
min_stack.push(5)
print(min_stack.get_min())  # Output: 3
min_stack.push(2)
min_stack.push(2)
print(min_stack.get_min())  # Output: 2
min_stack.pop()
print(min_stack.get_min())  # Output: 2
min_stack.pop()
print(min_stack.get_min())  # Output: 3

Key Points for Interviews

Understand the basic operations: Push, pop, peek, and isEmpty for stacks; enqueue, dequeue, peek, and isEmpty for queues.
Know the underlying data structures: Lists for basic implementation and collections.deque for efficient queue operations.
Be familiar with applications: Expression evaluation, backtracking, DFS for stacks; BFS, order processing, and task scheduling for queues.
Practice problems: Solve problems related to balancing symbols, expression evaluation, tree traversal, and other real-world scenarios involving stacks and queues.

By mastering these concepts and practicing relevant problems, you'll be well-prepared for interview questions on stacks and queues.

For Google DSA rounds and assessments, you can expect problems that require a deep understanding of stacks and queues. Below are some common types of problems along with their solutions, explanations, and code implementations in Python.

Problem 1: Valid Parentheses

Problem: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Solution:

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

# Example usage:
s = "()[]{}"
print(is_valid_parentheses(s))  # Output: True

s = "(]"
print(is_valid_parentheses(s))  # Output: False

Problem 2: Min Stack

Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Solution:

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        if self.stack:
            top = self.stack.pop()
            if top == self.min_stack[-1]:
                self.min_stack.pop()

    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

# Example usage:
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min())  # Output: -3
min_stack.pop()
print(min_stack.top())      # Output: 0
print(min_stack.get_min())  # Output: -2

Problem 3: Implement Queue using Stacks

Problem: Implement a queue using two stacks.

Solution:

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        self.stack1.append(x)

    def pop(self):
        self.peek()
        return self.stack2.pop()

    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return not self.stack1 and not self.stack2

# Example usage:
queue = MyQueue()
queue.push(1)
queue.push(2)
print(queue.peek())  # Output: 1
print(queue.pop())   # Output: 1
print(queue.empty()) # Output: False

Problem 4: Daily Temperatures

Problem: Given a list of daily temperatures, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

Solution:

def daily_temperatures(T):
    stack = []
    res = [0] * len(T)
    for i, t in enumerate(T):
        while stack and T[stack[-1]] < t:
            index = stack.pop()
            res[index] = i - index
        stack.append(i)
    return res

# Example usage:
T = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(T))  # Output: [1, 1, 4, 2, 1, 1, 0, 0]

Problem 5: Sliding Window Maximum

Problem: Given an array nums and a sliding window size k, find the maximum value in each sliding window.

Solution:

from collections import deque

def max_sliding_window(nums, k):
    d = deque()
    out = []
    for i, n in enumerate(nums):
        while d and nums[d[-1]] < n:
            d.pop()
        d.append(i)
        if d[0] == i - k:
            d.popleft()
        if i >= k - 1:
            out.append(nums[d[0]])
    return out

# Example usage:
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

Problem 6: Evaluate Reverse Polish Notation

Problem: Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Solution:

def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token not in "+-*/":
            stack.append(int(token))
        else:
            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))  # Truncate towards zero
    return stack[0]

# Example usage:
tokens = ["2", "1", "+", "3", "*"]
print(eval_rpn(tokens))  # Output: 9

Problem 7: Design Circular Queue

Problem: Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Solution:

class MyCircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.head = self.tail = -1
        self.max_size = k

    def enQueue(self, value):
        if self.isFull():
            return False
        if self.isEmpty():
            self.head = 0
        self.tail = (self.tail + 1) % self.max_size
        self.queue[self.tail] = value
        return True

    def deQueue(self):
        if self.isEmpty():
            return False
        if self.head == self.tail:
            self.head = self.tail = -1
        else:
            self.head = (self.head + 1) % self.max_size
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.queue[self.head]

    def Rear(self):
        return -1 if self.isEmpty() else self.queue[self.tail]

    def isEmpty(self):
        return self.head == -1

    def isFull(self):
        return (self.tail + 1) % self.max_size == self.head

# Example usage:
circularQueue = MyCircularQueue(3)
print(circularQueue.enQueue(1))  # Output: True
print(circularQueue.enQueue(2))  # Output: True
print(circularQueue.enQueue(3))  # Output: True
print(circularQueue.enQueue(4))  # Output: False
print(circularQueue.Rear())      # Output: 3
print(circularQueue.isFull())    # Output: True
print(circularQueue.deQueue())   # Output: True
print(circularQueue.enQueue(4))  # Output: True
print(circularQueue.Rear())      # Output: 4

Problem 8: Largest Rectangle in Histogram

Problem: Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Solution:

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# Example usage:
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # Output: 10

Problem 9: Course Schedule

Problem: There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example, if prerequisites[i] = [a, b] this means you must take course b before course a. Determine if you can finish all courses.

Day 4 Python 2024

Overview of Stacks & Queues in Python interview level & problems

Table of contents

Stacks and Queues in Python

Stacks

What is a Stack?

Basic Operations

Implementing a Stack in Python

Applications of Stacks

Queues

What is a Queue?

Basic Operations

Implementing a Queue in Python

Applications of Queues

Important Concepts and Interview Preparation

Stacks

Queues

Practical Examples

Example 1: Balanced Parentheses using Stack

Example 2: Level Order Traversal of a Binary Tree using Queue

Example 3: Implementing a Min Stack

Key Points for Interviews

Problem 1: Valid Parentheses

Problem 2: Min Stack

Problem 3: Implement Queue using Stacks

Problem 4: Daily Temperatures

Problem 5: Sliding Window Maximum

Problem 6: Evaluate Reverse Polish Notation

Problem 7: Design Circular Queue

Problem 8: Largest Rectangle in Histogram

Problem 9: Course Schedule