Amazon Interview Question for Developer Program Engineers

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

I think making a n-ary tree should work. Start by any node and Do BFS. If you encounter any node that already in the tree except its parent, that means that node is not critical.

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

@Varun, can you help me understand how do you construct n-ary tree out of this.

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

Doesn't work with the following graph:
.A
./\
BC
.\/
.D
./\
EF
.\/
.G

Starting at A, you're going to encounter D twice, yet it's a critical node.

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

I think we can remove each node from the graph(one at a time) and check if the graph is still connected(doing BFS or DFS) and then add the node back to the graph.
I am sure there must be a more optimal solution for this.

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

Remove each node from the graph(one at a time) and then check if the graph is still connected(By doing BFS or DFS) and add the node back to the graph.
I am sure there exists a more optimal solution to this.

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

Remove each node from the graph(one vertex at a time) and then check if the graph is still connected(By doing DFS or BFS) and then add the node back to the graph.
I am sure there exists a more optimal solution to this.

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

manish i think the question is not clear.Each one interpreting the question in similar way. can you explain me in person :)

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

We can use BFS with path length property, if any node has length 3 from source than source and this node are critical nodes.
Incase of A-C-B & A-D-E-B, A-D-E will be critical path.

private int[] bfs(char s){
boolean[] visited = new boolean;
int[] count = new int;
Queue<Character> q = new LinkedList<Character>();
q.offer(s);
visited[s - 'A'] = true;
count[s -'A'] = 1;
while(! q.isEmpty()){
char tmp = q.poll();
for(char x : getAdjacentVertices(tmp)){
int indics = x - 'A';
if(! visited[indics]){
q.offer(x);
visited[x - 'A'] = true;
count[indics] = count[ tmp - 'A'] + 1;
} else{
count[indics] = count[ tmp - 'A'] + 1;
}
}
}
return count;
}
public List<Character> findCriticalNodes(){
int[] count =  bfs(source);
for(int x = 0 ; x < 26; x++){
if(count[x] == 3){
nodes.add((char) (x  + 'A'));
}
}
if(! nodes.isEmpty()){
}
return nodes;
}

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

Time Complexity O(V(V+E)) here, V is # of vertex and E is # edges

For a given vertex V,

- Maintain list of its immediate neighbor (i.e. pathlength 1). Call it as SINGLE_HOP
- Maintain list of immediate neighbors of SINGLE_HOP list, call it as ANSWER.
- ANSWER is the superset of our what our final answer will be.
- Now run BFS on V as root, remove all elements from ANSWER which can be reached using BFS with pathlength more than 2.
- If BFS finds a path with pathlength > 1 for an element in SINGLE_HOP, then remove all its immediate neighbors from ANSWER. store/append ANSWER => FINAL_ANSWER
- Repeat above with each edge.

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

I am interpreting this question as finding all critical paths, each defined by a pair of critical nodes.

For single-source critical path from source n:
- Do BFS where the limit of the search is of distance 2
- Track nodes of distance 1 from n
- When searching nodes of distance 2 from n, if it does not also exist at distance 1 from n (tracked in previous step), then add it to result set
- Result set now contains all nodes that form a critical path with n

For all sources critical paths:
- Easy solution is to just repeat the single-source solution for all nodes.

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

typedef pair<int, int> Node;

vector<int> *G; bool *onStack, *judge, *visited; int V;

void dfs(int u, int p, int d)
{
visited[u] = true; onStack[u] = true; if (d != 2) judge[u] = false;

++d;

for (int v : G[u])
{
if (v != p && !onStack[v]) dfs(v, u, d);
}

onStack[u] = false;
}

vector<Node> findCriticalNodes(vector<int> G[], int V)
{
::G = G; ::V = V;

onStack = new bool[V]; judge = new bool[V]; visited = new bool[V];

vector<Node> ans;

for (int u = 0; u < V - 1; ++u)
{
memset(onStack, false, V); memset(judge, true, V); memset(visited, false, V);

dfs(u, -1, 0);

for (int v = 0; v < V; ++v)
{
if (visited[v] && judge[v]) ans.push_back(Node(u, v));
}
}

return move(ans);
}

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

1) run all nodes shortest path algorithm
2) all the nodes whose paths size is greater than 2 are not ciritical
3) now find logest path between nodes by negating all the edge weights
4) if longest paths are greater than 2 then we can eliminate pairs form 2

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

Articulation Points in a Graph

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.