Related InterviewSolutions

• 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
• 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
• 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
• 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
• 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
• __________ 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
• 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
• _____________ 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
• 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
• 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