## Google Interview Question

SDE1s**Country:**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

UnionFind.

- Sithis April 01, 2019