Interview Question
Country: United States
is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
Seems like a Flow Network question.
- EulGam05 December 09, 2013Define the following Flow Network: N=(G,s,t,c)
G will be the original graph with the following modifications:
1. Turn each undirected edge into two edges in opposite directions.
2. Split each vertex v into two vertices v_i and v_o. All the incoming edges to v will be incoming to v_i and all the outgoing edges from v will be outgoing from v_o. Add a directed edge from v_i to v_o.
3. Remove incoming edges to s_i and outgoing edges from t_o.
s will be s_i and t will t_o where s and t are the original source and target vertices.
The capacities function - c will be equal to 1 on all edges except (s_i,s_o) and (t_i,t_o) where it will be equal to infinity.
Now, the Maximum Flow value in N will be equal to the maximum number of disjoint paths between s and t. Why? First it should be noted that because the capacities are all integers the maximum flow will be an integer flow as well. Second, the split vertices with a unit capacity edge between them will ensure that there is at most one saturated incoming edge for each vertex which would result in the paths being disjoint.
Overall run-time complexity: O(n^3) where n is the number of vertices in the original graph (Relabel-To-Front algorithm).