## Google Interview Question

**Country:**United States

if the relation is transitive(from aRb and bRc follows aRc) and symetric (from aRb follows bRa), then it's finding the connected component's in a undirected graph and just pick one vertex from each component.

I assume the relation is not to be treated as transitive, so, I don't see much else then a brute force, maximizing the recursion where you exclude directly related elements from the set of potential candidates. Every element has two options: it is in the set or it isn't. Since it's only about finding the size, I assume we can use some dp-techniques, similar like knapsack.

where those interviews phd level?

@ChrisK, i think your idea works and i just elaborate with a 3-step solution as follows:

Step 1. Construct the undirected graph where each vertex is an element from the given set and each edge is a relation from the list.

Step 2. Compute all the connected components of the graph.

Step 3. Count those components of size 1 (i.e. single-vertex components), and this count is actually the answer to the problem.

O(n^2) + exp(k) -

```
public static void main(String[] args) {
int n = 6;
int[][] connected = new int[n][n];
connected[0][3] = 1;
connected[3][0] = 1;
connected[1][2] = 1;
connected[2][1] = 1;
connected[0][2] = 1;
connected[2][0] = 1;
connected[0][4] = 1;
connected[4][0] = 1;
int m = max(connected);
System.out.println(m);
}
// S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}
public static int max(int[][] connected) {
int n = connected.length;
Map<Integer, List<List<Integer>>> map = new HashMap<Integer, List<List<Integer>>>();
int[] dp = new int[n];
dp[0] = 1;
List<List<Integer>> o = new ArrayList<List<Integer>>();
List<Integer> lo = new ArrayList<Integer>();
lo.add(0);
o.add(lo);
map.put(0, o);
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1];
List<List<Integer>> olist = new ArrayList<List<Integer>>();
List<Integer> l = new ArrayList<Integer>();
l.add(i);
olist.add(l);
map.put(i, olist);
for (int j = i - 1; j >= 0; j--) {
List<List<Integer>> connections = map.get(j);
if (null != connections) {
for (List<Integer> nodes : connections) {
boolean canconnect = true;
for (int node : nodes) {
if (connected[i][node] == 1) {
canconnect = false;
break;
}
}
if (canconnect) {
dp[i] = Math.max(dp[i], nodes.size() + 1);
List<List<Integer>> nconn = map.get(i);
List<Integer> list = new ArrayList<Integer>();
for (int k : nodes) {
list.add(k);
}
list.add(i);
nconn.add(list);
}
}
}
}
}
return dp[n - 1];
}
```

this is the independent set problem. though similar to the matching, it is np-hard.

- Anonymous November 13, 2017the relations form the edges between vertices. the problem asks the size of the largest subset of the vertices of a graph with the property that no two are connected by an edge. note that the edges can be of an arbitrary size.