Graph traversal interview questions

Rotten oranges problem goes like: In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing ...
Read More

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, ...
Read More

Tarjan Algorithm is a very useful algorithm in finding strongly connected components in a directed graph. What is a strongly connected component? What is Strongly Connected Component? A directed graph ...
Read More

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b ...
Read More

Today, we will discuss an approach that can be used to solve quite a few problems with matrices. Problem structure is quite similar, you have a matrix, where cells represent ...
Read More

Cycle in undirected graph using disjoint set In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to ...
Read More

Disjoint set data structure A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, ⋯ , 𝑆𝑛 } of disjoint dynamic sets. Subsets ...
Read More

Lowest common ancestor(LCA) using RMQ We already have discussed lowest common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find the lowest common ancestor ...
Read More

Breadth First traversal In the last post, we discussed depth first traversal of a graph. Today, we will discuss another way to traverse a graph, which is breadth first traversal ...
Read More

Given a direct graph, detect bridges in the graph. An edge is called as bridge edge if and only if on removal of that edge will increases number of components ...
Read More