## Google Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

UnionFind.

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

Wouldn't merging the intervals also work here?

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

I believe there are many approaches
1. First build the graph ( like 2d array) of n nodes using edge list
2. Then pick a pair from restricted nodes and recursively check does current node pass through any other node which is restricted, if so, simply remove that edge(s).
Complexity = there can be at most n^2 edges = M size O(m) , You need to pick a pair from k list O(k), and check all possible connections from source to destination of picked pair O(m)
O(nkm^2)

2.
2.1 build hash to set of given k list O(k)
2.2 Rater bulding graph, while building it check the restrictions recursively using 2d matrix,
Complexity = you need to traverse whole matrix to check restrictions O(n^2)
For each pair from edge list O(m) , keeping hash to set of nodes from k list O(1)
O(mn^2)

3. Efficient
Use union find algo, assuming path compression is used.
3.1 union edges from m list one by one if they are not connected, before connecting them see O(m)

a) the parent (s) of pair source does not lies in k list O(logn)
B) child of pair of destinations node not lies in k list O(logn)
If either of its true, then discard

Complexity = O(logn + logn) * O(m)
O(mlogn)

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

To check in k list use Hash to set map

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

isn't it k*m?

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

No, don't check directly to k list (which will be O(k) ) rather build hash to set list; and then check

What is Hash to set List of K?
put a node as key and all node that it connects to as set being value in map
make sure you put in reverse way to
like
1,4
1,5

1 -> (4,5)
4->1
5->1

to check efficiently in k list

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

Complexity of last code is
O(mklogn) in worst case
as it might possible that single node is connected to all nodes in restricted list

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

for approach 2
O(mkn^2)

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

Other option still using disjoint set is for each edge, before adding it, check the sets for each vertex in the edge (say sets x and y) and for each edge in the K list check also the sets of its vertices (say sets w and z), in case (x == z && y == w) || (x == w && y == z) discard the edge. Complexity is O(mk logn)

``````public class RestrictedPaths {

public List<UndirectedGraph.Edge> create(List<UndirectedGraph.Edge> edges, List<UndirectedGraph.Edge> restricted, int n) {

DisjointSet ds = new DisjointSet(n);

List<UndirectedGraph.Edge> result = new ArrayList<>();

for (UndirectedGraph.Edge edge: edges) {

int x = ds.find(edge.getSrc());
int y = ds.find(edge.getDest());

boolean validEdge = true;
for (UndirectedGraph.Edge r: restricted) {
int z = ds.find(r.getSrc());
int w = ds.find(r.getDest());

if ((x == z && y == w) || (x == w && y == z)) {
validEdge = false;
break;
}
}

if (validEdge) {
ds.union(x, y);
}
}

return result;

}

}``````

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.