Google Interview Question
SDE1sCountry: India
Interview Type: In-Person
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)
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
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
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) {
result.add(edge);
ds.union(x, y);
}
}
return result;
}
}
UnionFind.
- Sithis April 01, 2019