Practice DSA interview questions

Given weighted edges, count number of distinct shortest paths from source to destination. This problem extends Dijkstra by tracking path counts whenever equal shortest distances are found. It reinforces how dynamic programming can overlay on graph traversal to count optimal routes efficiently.

Prim’s algorithm builds a Minimum Spanning Tree by expanding the smallest weighted edge from the visited set. It maintains a priority queue of candidate edges. This exercise demonstrates greedy strategy and contrast with Kruskal’s union-find approach. Complexity O(E log V).

Kruskal’s algorithm forms an MST by sorting all edges and picking the smallest one that doesn’t form a cycle. It relies on Disjoint Set Union (DSU) to efficiently detect cycles and merge components. This question strengthens knowledge of union-find data structures, path compression, and greedy choice property.

A bipartite graph is one where vertices can be divided into two sets such that no two vertices within the same set share an edge. This property is essential in problems like graph coloring and matching. The problem asks to check if a given graph is bipartite using BFS. By assigning alternate colors (0 and 1) level by level, if a conflict arises where two connected nodes share the same color, the graph is not bipartite. This question is commonly asked to test understanding of BFS traversal and graph coloring principles.

This problem uses Depth First Search (DFS) to verify if a graph is bipartite. It demonstrates recursive coloring, backtracking, and adjacency exploration. If a vertex and its neighbor have the same color, the graph is not bipartite. The DFS approach highlights recursion in undirected graphs and helps practice backtracking logic. This question commonly appears in coding interviews, especially in graph theory rounds.

A bridge in an undirected graph is an edge whose removal increases the number of connected components. Tarjan’s algorithm identifies bridges using DFS and discovery/low arrays. The algorithm assigns timestamps during traversal, updating the low-link value based on back edges. If discovery[u] < low[v] for an edge u–v, it’s a bridge. This is vital for network reliability and connectivity-based questions.

An articulation point is a vertex whose removal increases the number of connected components. This problem identifies all articulation points using Tarjan’s algorithm. During DFS traversal, we maintain discovery and low values for each vertex. A root node is an articulation point if it has two or more children in DFS tree, while for others, if low[v] ≥ disc[u], then u is an articulation point. Understanding this helps design robust networks and critical node detection.

A strongly connected component (SCC) is a subset of nodes where every node is reachable from every other node. Kosaraju’s algorithm finds all SCCs in a directed graph using two DFS passes — first to compute finishing times, then on the reversed graph. It teaches reverse graph traversal, stack usage, and component grouping — essential for dependency and compiler optimization problems.

In a binary matrix where 1 represents open cells and 0 represents blocked cells, find the shortest path from the top-left to the bottom-right cell. BFS efficiently finds the minimal path by exploring neighboring cells level by level. This question teaches grid-based graph modeling and is often asked to test traversal with constraints.

Given a 2D grid of X and O, capture all regions surrounded by X. Any O connected to a border remains uncaptured. The problem uses DFS or BFS to mark border-connected O’s, and then converts all remaining O’s to X. This question tests mastery in flood fill, recursion, and grid graph modeling.

Given a grid where 2 represents rotten oranges and 1 represents fresh ones, find the minimum time for all oranges to rot. Each rotten orange spreads rot to its adjacent fresh oranges every minute. Using multi-source BFS from all initial rotten oranges ensures simultaneous spreading level by level. This question tests BFS from multiple sources and time-tracking in grids.

Given an array of integers `temperatures` representing the daily temperatures, return an array `answer` such that `answer[i]` is the number of days you have to wait after the `i-th` day to get a warmer temperature. If there is no future day for which this is possible, keep `answer[i] == 0` instead. This problem is a perfect use case for a monotonic stack. By maintaining a stack of indices in decreasing order of temperature, we can efficiently find the next warmer day for each day as we iterate through the list from left to right.

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression. RPN, also known as postfix notation, is a mathematical notation in which operators follow their operands. This avoids the need for parentheses. A stack is the natural data structure to solve this: iterate through the tokens, push numbers onto the stack, and when an operator is found, pop the last two numbers, perform the operation, and push the result back.

There are `n` cars going to the same destination along a one-lane road. The destination is `target` miles away. You are given two integer arrays `position` and `speed`, both of length `n`. A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper. A car fleet is a set of cars driving at the same position and speed. The question asks for the number of car fleets that will arrive at the destination. The key is to sort the cars by position and calculate their arrival times.

Given an absolute path for a Unix-style file system, simplify it. This involves resolving `.` (current directory), `..` (parent directory), and `//` (multiple slashes). An absolute path starts with `/`. The simplified path should always start with `/`, and there should be only a single slash between directory names. The last directory name (if it exists) should not end with a trailing `/`. The core idea is to treat the path as a sequence of directory changes, which perfectly maps to a stack.

You are given a string `s` consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on `s` until we no longer can. Return the final string after all such duplicate removals have been made. This problem can be elegantly solved using a stack. As we iterate through the string, we can use the stack to build our resulting string. If the current character is the same as the character on top of the stack, it means we found an adjacent duplicate.

We are given an array `asteroids` of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). All asteroids move at the same speed. Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet. This stack-based simulation problem requires carefully handling the interactions between asteroids moving in opposite directions.

Given an encoded string, return its decoded string. The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. `k` is guaranteed to be a positive integer. You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. This problem is best solved with one or two stacks to manage the nested structure of the string and the repeating counts.

Given an array of integers `heights` representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. This is a classic hard problem that can be solved efficiently using a monotonic stack. The key idea is to find, for each bar, the nearest smaller bar to its left and its right. These boundaries define the width of the largest rectangle that can be formed with that bar as the smallest bar. The stack helps track potential candidates for these boundaries in a single pass.

Given a string `s` representing a valid expression, implement a basic calculator to evaluate it and return the result of the evaluation. The expression string may contain open `(` and closing `)` parentheses, the plus `+` or minus sign `-`, non-negative integers, and empty spaces. You may assume that the given expression is always valid. This problem requires handling operator precedence, which is naturally introduced by parentheses. A stack is ideal for this, allowing us to 'pause' an evaluation, compute a sub-expression within parentheses, and then resume.

Given a string `s` representing an expression, implement a basic calculator to evaluate it and return the result. The expression string contains only non-negative integers, `+`, `-`, `*`, `/` operators, and empty spaces. The integer division should truncate toward zero. This problem introduces operator precedence (`*` and `/` must be evaluated before `+` and `-`). A common approach is to use a stack to store operands. We can process the string, and whenever we encounter a `*` or `/`, we immediately perform the operation with the last number on the stack.

Given a string `num` representing a non-negative integer and an integer `k`, return the smallest possible integer after removing `k` digits from `num`. The key insight for this problem is to use a monotonic stack. To make the resulting number as small as possible, we want to ensure the digits on the left are smaller than the digits on the right. We can iterate through the number, and if a digit is smaller than the previous one (at the top of the stack), we 'remove' the larger previous digit by popping it and decrementing `k`.

Given an array of `n` integers `nums`, a 132 pattern is a subsequence of three integers `nums[i]`, `nums[j]`, and `nums[k]` such that `i < j < k` and `nums[i] < nums[k] < nums[j]`. Return `true` if there is a 132 pattern in `nums`, otherwise, return `false`. This problem can be solved efficiently by iterating from right to left, using a stack to maintain potential `nums[j]` candidates and a variable to track the maximum possible `nums[k]` (which we call `s3`). The stack helps us find the largest `nums[j]` for a given `nums[k]`.

Given a balanced parentheses string `s`, return the score of the string. The score of a balanced parentheses string is based on the following rules: `()` has score 1. `AB` has score `A + B`, where `A` and `B` are balanced parentheses strings. `(A)` has score `2 * A`, where `A` is a balanced parentheses string. This problem can be solved by tracking the 'depth' of the parentheses. A stack-based approach simulates this by keeping track of the scores at each level of nesting.

Design an algorithm that collects daily price quotes for some stock and returns the **span** of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price. For example, if the prices of the last 7 days are `[100, 80, 60, 70, 60, 75, 85]`, then the spans are `[1, 1, 1, 2, 1, 4, 6]`. A monotonic (decreasing) stack is perfect for this.

Given two integer arrays `pushed` and `popped`, return `true` if this could have been the result of a sequence of push and pop operations on an initially empty stack, or `false` otherwise. The `pushed` array contains distinct values. This problem asks us to simulate the process. We can use an actual stack to perform the push operations and greedily check if the top of our stack matches the next element we need to pop. If we can successfully pop all elements in the `popped` order, the sequence is valid.

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return an array containing the maximum of each window. This hard problem requires an efficient way to find the maximum in a dynamic window. The optimal solution uses a **monotonic deque (double-ended queue)** to store indices of potential maximums.

You are given an `m x n` grid where each cell can have one of three values: `0` representing an empty cell, `1` representing a fresh orange, or `2` representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return `-1`. This is a classic **Breadth-First Search (BFS)** problem, which is implemented using a queue.

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. It is also called 'Ring Buffer'. One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue.

Design your implementation of the circular double-ended queue (deque). Your implementation should support `insertFront`, `insertLast`, `deleteFront`, `deleteLast`, `getFront`, `getRear`, `isEmpty`, and `isFull`. A circular deque is a generalization of a circular queue that allows insertion and deletion at both ends. This structure is highly flexible and can be used to implement both stacks (using one end) and queues (using opposite ends). It's often implemented with a fixed-size array and two pointers.