## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

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)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

But it is not given that A is source ie. it has no incoming edges and B is destination ie. it has no outgoing edges.

Comment hidden because of low score. Click to expand.
1
of 3 vote

Finding shortest path will not help. We need to remove all possible paths.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Consider a triangle ABC with all three edges AB,BC and AC. Removing edge AB still leaves the points A and B connected via AC and BC. You have to remove two edges in this case.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think that this is a Edmonds-Karp based solution, but i dont know how to implement it :(

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find all possible paths
2. Go through the path set, find the smallest sub edge set in common

2 Could be done by ranking the edges and use dynamic planning to figure out the minimal edge set that covers all paths.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The quesiton asked us to find an Articulation Edge (Bridge) in disguise and DFS can be used to find such and Edge Complexity O(V+E).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do DFS to get all the paths from node1 to node2. Build set of edges for each path. Now this is the famous set cover problem - find the minimum edges covering all paths and remove them.

This is classified DP problem

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Finding shortest path will not help. We need to remove all possible paths.

Comment hidden because of low score. Click to expand.
0

You gotta be kidding me...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

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.