Practice DSA interview questions

There are houses, each can be painted one of k colours or not painted yet. Neighbouring painting forms “neighbourhoods”. Return minimum cost to paint so that there are exactly target neighbourhoods. Use DP with three‐dimensional state: house index, previous neighbourhood count, previous colour. Illustrates complex DP with more dimensions and constraints.

Given a circular array, find the maximum sum subarray. Use DP idea: compute standard max subarray, and for circular case: total_sum − min_subarray (with edge check). Demonstrates converting to DP on wrap-around arrays.

Two robots start at (0,0) and (0, n−1) on a grid, each move down one row and either left/right/stay in same column. They collect cherries; both cannot collect same cherry. Maximize total cherries picked. This uses DP with three dimensions: row index, col1, col2; each state depends on next row picks. Highlights DP in grid with two agents.

Given a set of distinct positive integers, find the largest subset such that for any two numbers in the subset, one divides the other. Use DP: sort the array, then dp[i] = size of subset ending at i; transition from j < i if nums[i] % nums[j] == 0. Shows DP on subsets with divisibility constraints.

Given an integer array and target, find maximum number of non-overlapping subarrays whose sum equals target. Use DP: dp[i] = max(dp[i-1], dp[j] + 1) where sum of subarray j+1..i equals target. This uses prefix sum + DP for overlapping sub-problems to maximize count under constraints.

Understanding how graphs are represented is the foundation of graph theory. A graph can be stored using either an adjacency list or adjacency matrix. The adjacency list stores connected nodes for each vertex, using less memory for sparse graphs. The adjacency matrix is a 2D array that records whether an edge exists between every pair of vertices. This question focuses on implementing both representations, analyzing time and space trade-offs, and exploring use-cases such as undirected, directed, and weighted graphs.

Counting edges and vertices helps in verifying graph properties. In undirected graphs, every edge appears twice in adjacency lists, while in directed graphs it appears once. This exercise involves determining vertex count (n) and edge count efficiently from a given adjacency structure. It helps learners validate graph input and ensure correctness before applying complex algorithms like DFS or Dijkstra. The goal is to identify total edges without re-counting duplicates and understand how degree and edge relationships vary between directed and undirected graphs.

Given a graph’s adjacency structure, determine whether it’s directed or undirected. A directed graph contains asymmetric edge pairs, meaning an edge u→v may not imply v→u. By iterating through each node’s adjacency list, one can check if for every connection u→v, there exists a reciprocal edge v→u. This helps in validating inputs before running algorithms that depend on graph type (for example, Topological Sort works only for Directed Acyclic Graphs).

Many graph problems provide input as edge lists rather than adjacency structures. The goal is to convert an edge list of pairs into a proper adjacency list representation. Understanding this conversion reinforces internal graph representation logic used in algorithms. It’s useful in implementing algorithms like BFS, DFS, and Dijkstra which require adjacency-based access. The challenge is ensuring correct handling of directed and undirected graphs while avoiding duplicates.

The degree of a vertex defines how many edges connect to it. In undirected graphs, both endpoints share an edge, while in directed graphs, we differentiate between in-degree and out-degree. Calculating vertex degrees is an essential preprocessing step in several algorithms such as Kahn’s Topological Sort or connectivity checks. The task involves traversing adjacency lists and counting incoming and outgoing edges depending on the graph’s type.

BFS explores nodes level by level starting from a source vertex, using a queue to manage traversal order. It’s widely used in shortest-path problems on unweighted graphs and in checking connectivity. This exercise aims to implement BFS from scratch, visit all vertices in order, and mark visited nodes to prevent cycles. The task teaches graph traversal in breadth fashion and its use in identifying connected components or computing levels of nodes.

DFS explores nodes by going deep along one path before backtracking. Implementing DFS recursively or iteratively helps in understanding tree/graph traversal and cycle detection. The problem focuses on performing DFS from a given start vertex and printing traversal order. It demonstrates stack-based recursion and state tracking through a visited list to prevent infinite loops in cyclic graphs.

Determine the number of connected components in an undirected graph using BFS or DFS. Each component is a maximal set of vertices reachable from one another. This concept is essential in understanding graph connectivity and forms a basis for clustering or identifying isolated subgraphs. Implementing this reinforces repeated traversal logic on unvisited vertices.

Detecting cycles helps in validating graph properties. In undirected graphs, a cycle exists if during DFS traversal a visited vertex is encountered that is not the parent of the current vertex. The exercise aims to implement this logic recursively and confirm whether cycles exist in given graphs.

In directed graphs, cycle detection relies on recursion stack tracking. If during DFS traversal, a vertex is revisited while still in the recursion path, a cycle exists. This problem helps learners understand back-edges and how they represent cycles in directed graphs. It’s a foundation for algorithms like Topological Sort that require acyclic graphs.

Topological sorting of a Directed Acyclic Graph (DAG) orders its vertices such that for every directed edge u → v, u appears before v. This problem uses **Kahn’s Algorithm** (BFS based) that repeatedly removes nodes with zero in-degree and updates neighbors’ in-degrees. It’s crucial for scheduling tasks and resolving dependency chains in systems like build-order or course prerequisites, as it ensures all dependencies are met before a node is processed.

Another approach for topological sorting uses **depth-first traversal**. The order is determined by pushing nodes onto a stack *after* all their dependent nodes (neighbors) have been visited. Reversing this stack then gives a valid topological order. This technique strengthens the understanding of post-order DFS and dependency resolution, particularly in identifying the logical ordering of tasks where no cycle exists.

Given $n$ courses and a list of prerequisites, the goal is to determine if it is **possible to finish all courses**. This is solved by modeling the courses as a directed graph where an edge $A \to B$ means course $A$ is a prerequisite for course $B$. The problem reduces to **detecting a cycle** in this dependency graph using Kahn's topological sort. If the topological order contains all $n$ courses, no cycle exists, and all courses can be finished.

The core challenge is to **find the alphabetical order** of characters in an unknown language, given a list of words sorted lexicographically by that language's rules. This is a classic **topological sorting application**. Edges are established between letters based on the first differing character in adjacent words (e.g., if 'wrt' comes before 'wrf', then $t \to f$). Topological sort then reveals the correct character precedence order.

In a directed graph, a node is considered **safe** if every path starting from it eventually leads to a terminal node (a node with no outgoing edges). The goal is to identify all such safe nodes. The key insight is that safe nodes are those **not part of any cycle**. This problem is solved efficiently by creating a **reverse graph** and applying Kahn's algorithm, as all nodes whose reversed paths lead to the initial set of terminal nodes are safe.

Given a set of jobs and their dependency relationships (prerequisites), find the **minimum time required to finish all jobs**, where each job takes a single unit of time. This is a shortest path problem in a DAG, where the path length represents the minimum time. It's solved by iterating through the topologically sorted nodes and updating the time to complete a job based on the max completion time of its prerequisites.

Given the number of courses and the list of prerequisites, return **one valid order** in which the courses can be taken to finish all of them. Unlike Course Schedule I, this requires constructing the actual topological sort order. The problem is directly solved using Kahn’s algorithm. If a cycle is detected (the final order size is less than the total number of courses), an empty list is returned, otherwise the computed order is returned.

Given $N$ courses and prerequisites, find the **minimum number of semesters** required to finish all courses, where in one semester you can take any number of courses as long as all prerequisites are met. This models a level-order traversal on the DAG. By using Kahn's algorithm, we count the layers/levels of the BFS. Each level represents one semester where all available courses can be taken in parallel.

The problem of detecting a cycle in an undirected graph can also be solved using **Breadth-First Search (BFS)**. Similar to DFS, BFS maintains a `visited` array and keeps track of the **parent** of each node. If BFS encounters a neighbor that has already been visited and is **not** the current node's direct parent, a cycle is present. This BFS-based approach offers an iterative alternative to the recursive DFS method for cycle detection.

This problem asks to find the shortest path in an undirected graph where each edge has a unit weight. The optimal approach uses Breadth First Search (BFS) because every edge cost is equal, ensuring level order traversal represents distance from the source. BFS guarantees minimal distance discovery as it explores neighbors level-wise. The task is to compute shortest distance from a source node to all vertices efficiently in O(V + E).

Dijkstra’s algorithm finds the shortest path from a single source to all other nodes in a weighted graph with non-negative edges. It uses a priority queue to always expand the node with the smallest current distance. The algorithm progressively relaxes edges, updating distances until all nodes are finalized. Understanding Dijkstra’s is crucial for network routing, GPS, and optimization tasks. Complexity O(E log V).

Bellman-Ford computes shortest paths from a single source even if negative edges exist. It repeatedly relaxes all edges V−1 times. If after V−1 iterations any edge can still be relaxed, a negative cycle exists. This problem tests understanding of edge relaxation, negative weight handling, and cycle detection. Complexity O(V × E).

Floyd-Warshall computes shortest paths between all pairs of vertices. It’s a dynamic programming algorithm updating distance[i][j] through every intermediate k. It elegantly demonstrates multi-stage relaxation in O(V³) time, making it ideal for dense graphs or fixed small V. Learners explore how adding an intermediate node may improve path lengths and handle negative edges without cycles.

Finding shortest paths in a DAG can be done faster using topological order. Because edges only go forward, relaxing them in topo order ensures each vertex gets minimal distance. This problem teaches applying topological sorting to weighted DAGs for linear-time path computations. Complexity O(V + E).

Given flights between cities with costs, find cheapest price from source to destination with ≤ K stops. This combines shortest-path logic with level-wise BFS or Bellman-Ford bounded by K iterations. It demonstrates constrained relaxation and practical airline network optimization.