Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Can someone clarify this question. We can directly disconnect two nodes by removing the edge connecting them. I know this is not the answer please elaborate this question.
int bfs(int graph[][V],int src,int dest,int parent[])
{
int visited[V];
int i=0;
for(i=0;i<V;i++)
visited[i]=0;
push(src);
parent[src]=-1;
visited[src]=1;
int temp = pop();
while(temp!=-1)
{
for(i=0;i<V;i++)
{
if(visited[i]==0 && graph[temp][i]>0)
{
visited[i]=1;
push(i);
parent[i]=temp;
}
}
temp=pop();
}
return visited[dest];
}
void dfs(int graph[][V],int src,int visited[])
{
visited[src]=1;
int i=0;
for(i=0;i<V;i++)
{
if(visited[i]==0 && graph[src][i]>0)
dfs(graph,i,visited);
}
}
int getmin(int graph[][V],int src,int dest)
{
int res[V][V];
int i=0,j=0;
for(j=0;j<V;j++)
{
for(i=0;i<V;i++)
res[i][j] = graph[i][j];
}
int parent[V];
int flow=1000;
int mincap=0;
while(bfs(res,src,dest,parent))
{
flow = 1000;
int v = dest;
while(v!=src)
{
int u = parent[v];
if(flow>res[u][v])
flow = res[u][v];
v=u;
}
v = dest;
while(v!=src)
{
int u = parent[v];
res[u][v] = res[u][v]-flow;
res[v][u] = res[v][u]+flow;
v = u;
}
mincap = mincap + flow;
}
int visited[V];
for(i=0;i<V;i++)
visited[i]=0;
dfs(res,src,visited);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
if(visited[i]==1 && visited[j]==0 && graph[i][j]>0)
printf("%d---->%d\t",i,j);
}
}
printf("\n");
return mincap;
}
Direction is to find all possible paths, and remove most common edges.
If space is not a problem, solution should maintain each edge's occurrence count, and reference to paths on which it occurs.
Algorithm should remove edge with highest occurrence count, then discard paths, on which it was occurring.
Repeat the same process, until all paths are discarded.
If the graph is directed-
1) Add a dummy source to the first node with capacity infinity.
2) Add a dummy sink to the second node with capacity infinity.
3) Give all other nodes capacity 1.
4) Apply ford-fulkerson algorithm, max-flow value will give the minimum number of edges to disconnect the two nodes.Because max-flow is equal to min-cut.
If the graph is undirected.
1) Reduce it to the directed graph.
2) Apply the same procedure as stated above.
I think we can transfer the question as to search for the shortest path between A and B with treating all edge weights equal to 1, then we can solve the question with Dijkstra's algorithm.
Can be solved by taking the max flow where A is the source and B the desination. The min number of edges to remove would be the flow. (max flow, min cut)
- Anonymous April 20, 2014