InterviewSolution
Saved Bookmarks
InterviewSolution
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. |
What is the minimum cut of the following network?(a) ({1,3},{4,3},{4,5})(b) ({1,2},{2,3},{4,5})(c) ({1,0},{4,3},{4,2})(d) ({1,2},{3,2},{4,5})This question was posed to me in an interview for job.My question comes from Minimum Cut topic in chapter Minimum Cut of Data Structures & Algorithms II |
|
Answer» CORRECT OPTION is (a) ({1,3},{4,3},{4,5}) The best explanation: The minimum cut of the given GRAPH network is FOUND to be ({1,3},{4,3},{4,5}) and its CAPACITY is 23. |
|
| 2. |
Which one of the following is not an application of max-flow min-cut algorithm?(a) network reliability(b) closest pair(c) network connectivity(d) bipartite matchingThe question was posed to me during an interview.I want to ask this question from Minimum Cut in section Minimum Cut of Data Structures & Algorithms II |
|
Answer» CORRECT answer is (b) CLOSEST pair Easy EXPLANATION - Network reliability, connectivity and BIPARTITE matching are all applications of min-cut algorithm whereas closest pair is a different kind of PROBLEM. |
|
| 3. |
What is the running time of implementing a min-cut algorithm using bidirected edges in a graph?(a) O(N)(b) O(N log N)(c) O(N^4)(d) O(N^2)The question was posed to me in an internship interview.Asked question is from Minimum Cut in section Minimum Cut of Data Structures & Algorithms II |
|
Answer» The correct OPTION is (c) O(N^4) |
|
| 4. |
The running time of implementing naïve solution to min-cut problem is?(a) O(N)(b) O(N log N)(c) O(log N)(d) O(N^2)This question was posed to me during an internship interview.My doubt stems from Minimum Cut in division Minimum Cut of Data Structures & Algorithms II |
|
Answer» The correct CHOICE is (d) O(N^2) |
|
| 5. |
In how many ways can a Gomory-Hu tree be implemented?(a) 1(b) 2(c) 3(d) 4I got this question during an online interview.My question comes from Minimum Cut in chapter Minimum Cut of Data Structures & Algorithms II |
|
Answer» Right CHOICE is (B) 2 |
|
| 6. |
__________ is a data structure used to collect a system of cuts for solving min-cut problem.(a) Gomory-Hu tree(b) Gomory-Hu graph(c) Dancing tree(d) AA treeI got this question in a national level competition.My question is taken from Minimum Cut in portion Minimum Cut of Data Structures & Algorithms II |
|
Answer» CORRECT OPTION is (a) Gomory-Hu TREE Explanation: Gomory-Hu tree is a WEIGHTED tree that CONTAINS the minimum cuts for all pairs in a graph. It is constructed in |V|-1 max-flow computations. |
|
| 7. |
The weight of the cut is not equal to the maximum flow in a network.(a) true(b) falseThis question was addressed to me at a job interview.This is a very interesting question from Minimum Cut topic in chapter Minimum Cut of Data Structures & Algorithms II |
|
Answer» Right choice is (B) false |
|
| 8. |
_____________ is a family of combinatorial optimization problems in which a graph is partitioned into two or more parts with constraints.(a) numerical problems(b) graph partition(c) network problems(d) combinatorial problemsThe question was asked in semester exam.Enquiry is from Minimum Cut in division Minimum Cut of Data Structures & Algorithms II |
|
Answer» The correct option is (b) graph PARTITION |
|
| 9. |
What is the running time of Karger’s algorithm to find the minimum cut in a graph?(a) O(E)(b) O(|V|^2)(c) O(V)(d) O(|E|)The question was asked in exam.I'm obligated to ask this question of Minimum Cut in chapter Minimum Cut of Data Structures & Algorithms II |
|
Answer» CORRECT answer is (B) O(|V|^2) Easy explanation - The RUNNING time of Karger’s ALGORITHM to find the minimum cut is mathematically found to be O(|V|^2). |
|
| 10. |
What is the minimum number of cuts that a graph with ‘n’ vertices can have?(a) n+1(b) n(n-1)(c) n(n+1)/2(d) n(n-1)/2This question was addressed to me in final exam.This interesting question is from Minimum Cut topic in portion Minimum Cut of Data Structures & Algorithms II |
|
Answer» The CORRECT option is (C) n(n+1)/2 |
|
| 11. |
______________ separates a particular pair of vertices in a graph.(a) line(b) arc(c) cut(d) flowI have been asked this question in my homework.Origin of the question is Minimum Cut topic in division Minimum Cut of Data Structures & Algorithms II |
|
Answer» Right ANSWER is (c) CUT |
|
| 12. |
What does the given figure depict?(a) min cut problem(b) max cut problem(c) maximum flow problem(d) flow graphThe question was posed to me in an international level competition.My doubt is from Minimum Cut in portion Minimum Cut of Data Structures & Algorithms II |
|
Answer» Correct choice is (a) min cut PROBLEM |
|
| 13. |
Minimum cut algorithm comes along with the maximum flow problem.(a) true(b) falseThis question was posed to me during an interview.My doubt stems from Minimum Cut in chapter Minimum Cut of Data Structures & Algorithms II |
|
Answer» The correct ANSWER is (a) true |
|
| 14. |
___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge.(a) Minimum cut(b) Maximum flow(c) Maximum cut(d) Graph cutI got this question in a job interview.My enquiry is from Minimum Cut topic in section Minimum Cut of Data Structures & Algorithms II |
|
Answer» Right choice is (a) MINIMUM cut |
|
| 15. |
Which algorithm is used to solve a minimum cut algorithm?(a) Gale-Shapley algorithm(b) Ford-Fulkerson algorithm(c) Stoer-Wagner algorithm(d) Prim’s algorithmThe question was posed to me in exam.I would like to ask this question from Minimum Cut in section Minimum Cut of Data Structures & Algorithms II |
|
Answer» Correct ANSWER is (C) Stoer-Wagner algorithm |
|