Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.

From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?(a) 5(b) 4(c) 3(d) 2I had been asked this question in homework.My enquiry is from Matching in section Matching of Data Structures & Algorithms II

Answer» CORRECT OPTION is (a) 5

Best explanation: One of the solutions of the matching problem is given by a-w,b-v,c-x,d-y,e-z. Hence the answer is 5.
Discussion
2.

Who was the first person to solve the maximum matching problem?(a) Jack Edmonds(b) Hopcroft(c) Karp(d) Claude BergeI had been asked this question in class test.This interesting question is from Matching topic in section Matching of Data Structures & Algorithms II

Answer»

The correct ANSWER is (a) JACK Edmonds

The BEST explanation: Jack Edmonds was the first person to solve the maximum MATCHING PROBLEM in 1965.
Discussion
3.

What is the efficiency of algorithm designed by Hopcroft and Karp?(a) O(n+m)(b) O(n(n+m)(c) O(√n(n+m))(d) O(n+2)I had been asked this question in final exam.My question is taken from Matching in division Matching of Data Structures & Algorithms II

Answer»

Right choice is (C) O(√n(n+m))

To explain: The EFFICIENCY of ALGORITHM designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).
Discussion
4.

What is the total number of iterations used in a maximum- matching algorithm?(a) [n/2](b) [n/3](c) [n/2]+n(d) [n/2]+1The question was posed to me in class test.This interesting question is from Matching in section Matching of Data Structures & Algorithms II

Answer»

The correct ANSWER is (d) [n/2]+1

To explain: The total number of iterations cannot EXCEED [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.
Discussion
5.

The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?(a) Maximum- mass matching(b) Maximum bipartite matching(c) Maximum weight matching(d) Maximum node matchingThe question was asked in an online interview.This is a very interesting question from Matching in portion Matching of Data Structures & Algorithms II

Answer»

Right OPTION is (c) MAXIMUM weight matching

Best EXPLANATION: The PROBLEM is called as maximum weight matching which is similar to a bipartite matching. It is also called as assignment problem.
Discussion
6.

Which is the correct technique for finding a maximum matching in a graph?(a) DFS traversal(b) BFS traversal(c) Shortest path traversal(d) Heap order traversalThe question was posed to me in homework.My question is from Matching in division Matching of Data Structures & Algorithms II

Answer»

Right ANSWER is (b) BFS traversal

The best EXPLANATION: The CORRECT technique for FINDING a MAXIMUM matching in a bipartite graph is by using a Breadth First Search(BFS).
Discussion
7.

Which one of the following is an application for matching?(a) Proposal of marriage(b) Pairing boys and girls for a dance(c) Arranging elements in a set(d) Finding the shortest traversal pathThis question was posed to me in my homework.The origin of the question is Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

Correct choice is (b) Pairing boys and girls for a dance

Best EXPLANATION: Pairing boys and girls for a dance is a traditional example for MATCHING. Proposal of MARRIAGE is an application of STABLE marriage problem.
Discussion
8.

A matching M is maximal if and only if there exists no augmenting path with respect to M.(a) True(b) FalseThe question was posed to me in unit test.This question is from Matching in portion Matching of Data Structures & Algorithms II

Answer» RIGHT option is (a) True

The explanation is: ACCORDING to the theorem discovered by the French MATHEMATICIAN CLAUDE Berge, it means that the CURRENT matching is maximal if there is no augmenting path.
Discussion
9.

In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?(a) Bipartite matching(b) Cardinality matching(c) Augmenting(d) Weight matchingThis question was addressed to me in a national level competition.I need to ask this question from Matching topic in portion Matching of Data Structures & Algorithms II

Answer»

The correct choice is (c) Augmenting

For EXPLANATION: A SIMPLE PATH from a FREE VERTEX in V to a free vertex in U whose edges alternate between edges not in M and edges in M is called a augmenting path.
Discussion
10.

What is the length of an augmenting path?(a) Even(b) Odd(c) Depends on graph(d) 1This question was addressed to me during an interview for a job.I want to ask this question from Matching in section Matching of Data Structures & Algorithms II

Answer» CORRECT CHOICE is (b) Odd

Easiest explanation - The length of an augmenting PATH in a BIPARTITE graph is ALWAYS said to be always odd.
Discussion
11.

A matching that matches all the vertices of a graph is called?(a) Perfect matching(b) Cardinality matching(c) Good matching(d) Simplex matchingThe question was posed to me in an interview for job.This intriguing question comes from Matching topic in division Matching of Data Structures & Algorithms II

Answer»

The correct choice is (a) Perfect matching

The EXPLANATION is: A matching that matches all the VERTICES of a GRAPH is called perfect matching.
Discussion
12.

What is the simplest method to prove that a graph is bipartite?(a) It has a cycle of an odd length(b) It does not have cycles(c) It does not have a cycle of an odd length(d) Both odd and even cycles are formedThe question was posed to me during an internship interview.My question comes from Matching in section Matching of Data Structures & Algorithms II

Answer» RIGHT option is (c) It does not have a cycle of an odd length

The BEST I can explain: It is not DIFFICULT to PROVE that a graph is bipartite if and only if it does not have a cycle of an odd length.
Discussion
13.

How many colours are used in a bipartite graph?(a) 1(b) 2(c) 3(d) 4I had been asked this question in semester exam.This question is from Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

The correct CHOICE is (B) 2

The best I can explain: A bipartite graph is SAID to be two-colourable so that every edge has its VERTICES coloured in different colours.
Discussion
14.

Maximum matching is also called as maximum cardinality matching.(a) True(b) FalseThe question was posed to me in quiz.My doubt stems from Matching in chapter Matching of Data Structures & Algorithms II

Answer»

Right choice is (a) True

Best EXPLANATION: Maximum MATCHING is ALSO CALLED as maximum cardinality matching (i.e.) matching with the largest number of edges.
Discussion
15.

_____________ is a matching with the largest number of edges.(a) Maximum bipartite matching(b) Non-bipartite matching(c) Stable marriage(d) SimplexThis question was posed to me by my college director while I was bunking the class.This intriguing question originated from Matching topic in portion Matching of Data Structures & Algorithms II

Answer» RIGHT ANSWER is (a) MAXIMUM bipartite matching

The best EXPLANATION: Maximum bipartite matching matches TWO elements with a property that no two edges share a vertex.
Discussion
16.

What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(log N)The question was asked during an interview for a job.This key question is from Matching in portion Matching of Data Structures & Algorithms II

Answer»

Right OPTION is (c) O(N^2)

Easiest explanation - The TIME efficiency of Gale-Shapley algorithm is MATHEMATICALLY FOUND to be O(N^2) where N denotes stable MARRIAGE problem.
Discussion
17.

Which of the following problems is related to stable marriage problem?(a) Choice of school by students(b) N-queen problem(c) Arranging data in a database(d) Knapsack problemThis question was posed to me in a job interview.Query is from Matching in section Matching of Data Structures & Algorithms II

Answer»

The correct option is (a) CHOICE of school by students

To explain: Choice of school by students is the most related example in the GIVEN set of OPTIONS since both school and students will have a preference LIST.
Discussion
18.

What is the prime task of the stable marriage problem?(a) To provide man optimal solution(b) To provide woman optimal solution(c) To determine stability of marriage(d) To use backtracking approachI had been asked this question in a job interview.Question is taken from Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

Right choice is (c) To DETERMINE stability of marriage

Easy EXPLANATION - The prime task of stable marriage PROBLEM is to determine stability of marriage (i.e) FINDING a man and a woman who PREFER each other to others.
Discussion
19.

Can stable marriage cannot be solved using branch and bound algorithm.(a) True(b) FalseThe question was asked in an internship interview.This question is from Matching topic in section Matching of Data Structures & Algorithms II

Answer»

Correct answer is (b) False

The best explanation: Stable marriage PROBLEM can be solved using BRANCH and bound approach because branch and bound follows BACKTRACKING SCHEME with a LIMITATION factor.
Discussion
20.

Who formulated a straight forward backtracking scheme for stable marriage problem?(a) McVitie and Wilson(b) Gale(c) Ford and Fulkerson(d) DinitzThe question was posed to me in an interview.This question is from Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

Correct answer is (a) McVitie and Wilson

The best explanation: McVitie and Wilson formulated a much faster straight forward backtracking scheme for STABLE MARRIAGE problem. FORD and Fulkerson formulated MAXIMUM FLOW problem.
Discussion
21.

Consider the following ranking matrix. Assume that M1 and W1 are married and M2 and W3 are married. Now, whom will M3 approach first?(a) W1(b) W2(c) W3(d) All threeThe question was asked in an interview for internship.I want to ask this question from Matching in portion Matching of Data Structures & Algorithms II

Answer»

The correct option is (c) W3

To explain: M3 will approach W3 FIRST. SINCE W3 is married and since her preference list has her current mate before M3, she rejects his proposal.
Discussion
22.

Consider the following ranking matrix. Assume that M1 and W2 are married. Now, M2 approaches W2. Which of the following happens?(a) W2 replaces M1 with M2(b) W2 rejects M2(c) W2 accepts both M1 and M2(d) W2 rejects both M1 and M2I got this question by my college director while I was bunking the class.I need to ask this question from Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

Right answer is (a) W2 REPLACES M1 with M2

For explanation: W2 is married to M1. But the preference of W2 has M2 before M1. HENCE, W2 replaces M1 with M2.
Discussion
23.

In case of stability, how many symmetric possibilities of trouble can occur?(a) 1(b) 2(c) 4(d) 3I had been asked this question in an online interview.The origin of the question is Matching in division Matching of Data Structures & Algorithms II

Answer»

The CORRECT answer is (b) 2

Best explanation: Possibilities- There might be a woman pw, PREFERRED to W by m, who herself prefers m to be her husband and the same applies to man as WELL.
Discussion
24.

What happens when a free man approaches a married woman?(a) She simply rejects him(b) She simply replaces her mate with him(c) She goes through her preference list and accordingly, she replaces her current mate with him(d) She accepts his proposalThe question was asked in an international level competition.Query is from Matching topic in division Matching of Data Structures & Algorithms II

Answer»

The CORRECT answer is (c) She goes through her PREFERENCE list and accordingly, she REPLACES her current mate with him

Explanation: If the preference of the MAN is greater, she replaces her current mate with him, LEAVING her current mate free.
Discussion
25.

How many 2*2 matrices are used in this problem?(a) 1(b) 2(c) 3(d) 4This question was addressed to me by my college director while I was bunking the class.I would like to ask this question from Matching topic in portion Matching of Data Structures & Algorithms II

Answer»

Right CHOICE is (b) 2

For explanation: TWO 2*2 matrices are used. One for men REPRESENTING corresponding woman and ranking and the other for women.
Discussion
26.

If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.(a) True(b) FalseThe question was posed to me in an interview for job.My question is based upon Matching topic in division Matching of Data Structures & Algorithms II

Answer» RIGHT CHOICE is (a) True

Best explanation: If there are N COUPLES such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable.
Discussion
27.

When a free man proposes to an available woman, which of the following happens?(a) She will think and decide(b) She will reject(c) She will replace her current mate(d) She will acceptThis question was addressed to me in an international level competition.My question is based upon Matching in division Matching of Data Structures & Algorithms II

Answer»

The CORRECT answer is (d) She will accept

The EXPLANATION is: When a man proposes to an AVAILABLE woman, she will accept his proposal irrespective of his position on his preference list.
Discussion
28.

An optimal solution satisfying men’s preferences is said to be?(a) Man optimal(b) Woman optimal(c) Pair optimal(d) Best optimalThe question was asked during an interview for a job.Query is from Matching topic in chapter Matching of Data Structures & Algorithms II

Answer»

Right option is (a) Man optimal

The BEST EXPLANATION: An optimal solution satisfying men’s preferences are SAID to be man optimal. An optimal solution satisfying woman’s preferences are said to be woman optimal.
Discussion
29.

Which of the following algorithms does Stable marriage problem uses?(a) Gale-Shapley algorithm(b) Dijkstra’s algorithm(c) Ford-Fulkerson algorithm(d) Prim’s algorithmThis question was addressed to me in homework.My question is based upon Matching topic in section Matching of Data Structures & Algorithms II

Answer»

Right answer is (a) Gale-Shapley algorithm

Best explanation: Stable marriage problem USES Gale-Shapley algorithm. Maximum flow problem uses Ford-Fulkerson algorithm. Prim’s algorithm INVOLVES MINIMUM SPANNING tree.
Discussion
30.

Stable marriage problem is an example of?(a) Branch and bound algorithm(b) Backtracking algorithm(c) Greedy algorithm(d) Divide and conquer algorithmThe question was asked during a job interview.My question comes from Matching in section Matching of Data Structures & Algorithms II

Answer»

The correct OPTION is (B) Backtracking ALGORITHM

To EXPLAIN: Stable marriage problem is an EXAMPLE for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution.
Discussion