InterviewSolution

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.	How many constraints does flow have?(a) one(b) three(c) two(d) fourI have been asked this question by my school teacher while I was bunking the class.This key question is from Flow Networks in portion Flow Networks of Data Structures & Algorithms II
Answer» Right choice is (C) TWO Easy EXPLANATION - A flow is a mapping which follows two constraints- CONSERVATION of flows and CAPACITY constraints.

2.	What is the running time of Dinic’s blocking flow algorithm?(a) O(V^2E)(b) O(VE^2)(c) O(V^3)(d) O(E max \|f\|)The question was asked in a national level competition.The query is from Flow Networks in division Flow Networks of Data Structures & Algorithms II
Answer» The correct option is (a) O(V^2E) For EXPLANATION: The RUNNING time of Dinic’s blocking flow algorithm is O(V^2E). The running of Ford-Fulkerson algorithm is O(E max \|F\|).

3.	Who is the formulator of Maximum flow problem?(a) Lester R. Ford and Delbert R. Fulkerson(b) T.E. Harris and F.S. Ross(c) Y.A. Dinitz(d) KruskalThis question was addressed to me during an interview.My question is from Flow Networks topic in chapter Flow Networks of Data Structures & Algorithms II
Answer» The CORRECT choice is (b) T.E. HARRIS and F.S. Ross Easy explanation - The first ever people to FORMULATE Maximum flow problem were T.E. Harris and F.S. Ross. Lester R. Ford and Delbert R. Fulkerson FORMULATED Ford- Fulkerson algorithm.

4.	What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?(a) O(\|E\|)(b) O(\|E\|\|V\|)(c) O(\|E\|^2\|V\|)(d) O(\|E\| log \|V\|)I have been asked this question in unit test.My doubt stems from Flow Networks in division Flow Networks of Data Structures & Algorithms II
Answer» Right OPTION is (c) O(\|E\|^2\|V\|) The best I can explain: Each augmenting step takes O(\|E\|) using an unweighted shortest PATH algorithm YIELDING a O(\|E\|2\|V\|) bound on the running time.

5.	Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.(a) true(b) falseThis question was posed to me in a national level competition.Query is from Flow Networks topic in section Flow Networks of Data Structures & Algorithms II
Answer» Correct option is (a) true For EXPLANATION: Dinic’s ALGORITHM includes CONSTRUCTION of LEVEL graphs and resLidual graphs and finding of augmenting paths along with blocking flow and is FASTER than the Ford-Fulkerson algorithm.

6.	In what time can an augmented path be found?(a) O(\|E\| log \|V\|)(b) O(\|E\|)(c) O(\|E\|^2)(d) O(\|E\|^2 log \|V\|)The question was posed to me during an interview.The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II
Answer» Right choice is (B) O(\|E\|) The EXPLANATION is: An augmenting PATH can be found in O(\|E\|) mathematically by an unweighted shortest path ALGORITHM.

7.	A simple acyclic path between source and sink which pass through only positive weighted edges is called?(a) augmenting path(b) critical path(c) residual path(d) maximum pathThis question was posed to me during an online exam.Question is from Flow Networks in section Flow Networks of Data Structures & Algorithms II
Answer» Right OPTION is (a) augmenting path Explanation: Augmenting path between source and sink is a simple path WITHOUT CYCLES. Path consisting of zero SLACK edges is called CRITICAL path.

8.	Find the maximum flow from the following graph.(a) 22(b) 17(c) 15(d) 20This question was addressed to me during an interview.This interesting question is from Flow Networks topic in portion Flow Networks of Data Structures & Algorithms II
Answer» Correct OPTION is (c) 15 For EXPLANATION: INITIALLY, zero flow is COMPUTED. Then, COMPUTING flow= 7+1+5+2=15. Hence, maximum flow=15.

9.	Under what condition can a vertex combine and distribute flow in any manner?(a) It may violate edge capacities(b) It should maintain flow conservation(c) The vertex should be a source vertex(d) The vertex should be a sink vertexThe question was asked in class test.I'd like to ask this question from Flow Networks topic in portion Flow Networks of Data Structures & Algorithms II
Answer» The correct CHOICE is (b) It should MAINTAIN flow conservation The best I can explain: A VERTEX can combine and DISTRIBUTE flow in any manner but it should not violate edge capacities and it should maintain flow conservation.

10.	The first step in the naïve greedy algorithm is?(a) analysing the zero flow(b) calculating the maximum flow using trial and error(c) adding flows with higher values(d) reversing flow if requiredThe question was asked during an online exam.I need to ask this question from Flow Networks in division Flow Networks of Data Structures & Algorithms II
Answer» The CORRECT answer is (a) ANALYSING the zero FLOW Easy explanation - The first step in the naïve greedy ALGORITHM is to start with the zero flow followed by adding edges with higher values.

11.	Does Ford- Fulkerson algorithm use the idea of?(a) Naïve greedy algorithm approach(b) Residual graphs(c) Minimum cut(d) Minimum spanning treeThis question was addressed to me in a job interview.The query is from Flow Networks topic in chapter Flow Networks of Data Structures & Algorithms II
Answer» Right ANSWER is (b) Residual GRAPHS Easy explanation - Ford-Fulkerson algorithm USES the idea of residual graphs which is an extension of naïve GREEDY approach allowing undo operations.

12.	Which algorithm is used to solve a maximum flow problem?(a) Prim’s algorithm(b) Kruskal’s algorithm(c) Dijkstra’s algorithm(d) Ford-Fulkerson algorithmThe question was posed to me by my college director while I was bunking the class.I'm obligated to ask this question of Flow Networks topic in section Flow Networks of Data Structures & Algorithms II
Answer» RIGHT CHOICE is (d) Ford-Fulkerson algorithm Easy explanation - Ford-fulkerson algorithm is USED to compute the MAXIMUM feasible flow between a SOURCE and a sink in a network.

13.	What is the source?(a) Vertex with no incoming edges(b) Vertex with no leaving edges(c) Centre vertex(d) Vertex with the least weightI got this question in class test.This interesting question is from Flow Networks topic in section Flow Networks of Data Structures & Algorithms II
Answer» RIGHT option is (a) Vertex with no incoming edges The BEST I can explain: Vertex with no incoming edges is CALLED as a SOURCE. Vertex with no leaving edges is called as a SINK.

14.	A network can have only one source and one sink.(a) False(b) TrueI got this question in examination.Asked question is from Flow Networks topic in chapter Flow Networks of Data Structures & Algorithms II
Answer» Right ANSWER is (b) True Easy explanation - A NETWORK can have only one source and one sink INORDER to find the feasible FLOW in a WEIGHTED connected graph.

15.	What does Maximum flow problem involve?(a) finding a flow between source and sink that is maximum(b) finding a flow between source and sink that is minimum(c) finding the shortest path between source and sink(d) computing a minimum spanning treeI got this question by my school principal while I was bunking the class.My doubt stems from Flow Networks topic in section Flow Networks of Data Structures & Algorithms II
Answer» Correct OPTION is (a) finding a flow between SOURCE and sink that is maximum Easy explanation - The maximum flow PROBLEM INVOLVES finding a feasible flow between a source and a sink in a network that is maximum and not MINIMUM.