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

What is Floyd's Algorithm?

FLOYD’S ALGORITHM Given a weighted connected graph (undirected or directed), the all-pairs shortest paths problem asks to find the distances—i.e., the lengths of the shortest paths— from each vertex to all other vertices.
ALGORITHM Floyd(W[1..n, 1..n])
//Implements Floyd‘s algorithm for the all-pairs shortest-paths problem
//Input: The weight matrix W of a graph with no negative-length cycle
//Output: The distance matrix of the shortest paths‘ lengths
D ←W //is not necessary if W can be overwritten
for k←1 to n do
for i ←1 to n do
for j ←1 to n do
D[i, j ]←min{D[i, j ], D[i, k]+ D[k, j]}
return D
Efficiency of Floyd‘s Algorithm: Time efficiency O(n^3) and Space Efficiency is O(n^2)

Question

Explanation

Write rules for converting infix to postfix.

1. Scan the input string (infix notation) from left to right. One pass is sufficient.
2. If the next symbol scanned is an operand, it may be immediately appended to the postfix string.
3. If the next symbol is an operator,
i. Pop and append to the postfix string every operator on the stack that
a. is above the most recently scanned left parenthesis, and
b. has precedence higher than or is a right-associative operator of equal precedence to that of the new operator symbol.
ii. Push the new operator onto the stack.
4. When a left parenthesis is seen, it must be pushed onto the stack.
5. When a right parenthesis is seen, all operators down to the most recently scanned left parenthesis must be popped and appended to the postfix string. Furthermore, this pair of parentheses must be discarded.
6. When the infix string is completely scanned, the stack may still contain some operators. [Why are there no parentheses on the stack at this point?] All the remaining operators should be popped and appended to the postfix string.

Question

Explanation

Convert the following infix expression to its equivalent postfix expression Showing stack contents for the conversion:
(A+B)*(C^(D-E)+F)-G

current symbol operator stack postfix string
1 ( (
2 A A
3 + ( + A
4 B ( + A B
5 ) A B +
6 * * A B +
7 ( * ( A B +
8 C * ( A B + C
9 ^ * ( ^ A B + C
10 ( * ( ^ ( A B + C
11 D * ( ^ ( A B + C D
12 - * ( ^ ( - A B + C D
13 E * ( ^ ( - A B + C D E
14 ) * ( ^ A B + C D E -
15 + * ( + A B + C D E - ^
16 F * ( + A B + C D E - ^ F
17 ) * A B + C D E - ^ F +
18 - - A B + C D E - ^ F + *
19 G - A B + C D E - ^ F + * G
20 AB + C D E - ^ F + * G -

Question

Explanation

Evaluate the following postfix notation of expression:
20,30,+,50,40,-,*

Using Stack
Step 1: Push 20
Step 2: Push 30
Step 3: Pop 20, Pop 30, Push(20+30=50)
Step 4: Push 50
Step 5: Push 40
Step 6: Pop 40, Pop 50 ,Push(50-40=10)
Step 7: Pop 10,Pop 50 ,Push(50*10=500)
Ans=500