Top Algorithms Interview Questions

Mobiprep handbooks are free downloadable placement preparation resources that can help you ace any company placement process. We have curated a list of the 40 most important MCQ questions which are asked in most companies such as Infosys, TCS, Wipro, Accenture, etc. The placement handbooks also have detailed explanations for every question ensuring you revise all the questions with detailed answers and explanations.

Question

Explanation

Write procedure of BFS.

a. Select an unvisited node x, visit it, have it be the root in a BFS tree being formed. Its level is called the current level.
b. From each node z in the current level, in the order in which the level nodes were visited, visit all the unvisited neighbors of z. The newly visited nodes from this level form a new level that becomes the next current level.
c. Repeat step 2 until no more nodes can be visited.
d. If there are still unvisited nodes, repeat from Step 1

Question

Explanation

Write tower of hanoi recursive algorithm for n disks and 3 pegs.
Problem statement: Given a game board with three pegs and a set of disks of different diameter all stacked from smallest to largest on the leftmost peg, move all of the disks to the rightmost peg following these two rules.
First, only one disk may be moved at a time.
Second, a larger diameter disk may never be placed on a smaller disk. Any number of disks can be used.

void Hanoi( int n, string a, string b, string c)
{
if (n == 1) /* base case */
Move( a, b );
else { /* recursion */
Hanoi( n-1, a, c, b );
Move( a, b );
Hanoi( n-1, c, b, a );
}
}

Time Complexity of this algorithm is: O(2^n).

Question

Explanation

Define -Warshall‘s algorithm.

Warshall‘s algorithm is an application of dynamic programming technique, which is used to find the transitive closure of a directed graph.
Transitive closure of a graph:
Given a digraph G(V,E) the transitive closure is a digraph G’(V’,E’) such that
> V’ = V (same set of vertices)
> If (vi, vi+1,…,v k) is a path in G, then (vi, v k) is an edge of E
Generally, The reach-ability matrix is called the transitive closure of a graph.

Question

Explanation

What is greedy technique?

Greedy technique suggests a greedy grab of the best alternative available in the hope that a sequence of locally optimal choices will yield a globally optimal solution to the entire problem.

Examples:

>Kruskal’s Minimum Spanning Tree
>Prim’s Minimum Spanning Tree
>Boruvka’s Minimum Spanning Tree
>Reverse delete algorithm for MST
>Problem Solving for Minimum Spanning Trees (Kruskal’s and Prim’s)
>Dijkastra’s Shortest Path Algorithm