## Microsoft Interview Question

Software Engineers**Country:**United States

**Interview Type:**Phone Interview

Assuming the set of rules is complete and non-contradictary, i.e after applying the rules every element can be in exactly one of the two partitions:

```
def part(n, k):
rel = [0]*n
for a,b in k:
if rel[a-1] == rel[b-1]:
rel[a-1] = 1
rel[b-1] = -1
else:
if rel[b-1]==0:
a,b = b,a
rel[a-1] = -rel[b-1]
r1 = []
r2 = []
for i in xrange(n):
r = r1 if rel[i] == 1 else r2
r += [i+1]
return (r1,r2)
```

@robb.krakow Sure. This has some similarities with union-find. Use an array to store for N elements which of the two partitions they belong to with 0 meaning unmarked/undecided. When you see a rule (a,b) you look up a,b in the array. If both of them are unmarked, i.e. rel[a] == rel[b] (we assume a != b and they cannot be already marked as belonging to the same partition as the rules are non-contradictary), we mark them as belonging to the opposite partitions. Otherwise identify which of a,b is marked and mark the other one as belonging to the opposite partition.

A generic where numbers can be any array.

```
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
public class SetPartitionBasedOnQuery {
public static void main(String[] args) {
int N = 4;
List<int[]> queries = new ArrayList<>();
int[] numbers = new int[N];
for(int i=0;i<N;i++){
numbers[i] = i+1;
}
queries.add(new int[]{1,2});
queries.add(new int[]{1,3});
queries.add(new int[]{2,4});
try {
HashSet<Integer>[] result = partition(numbers, queries);
for (HashSet<Integer> hashSet : result) {
Iterator<Integer> iter = hashSet.iterator();
System.out.println();
while(iter.hasNext()){
System.out.print(iter.next());
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static HashSet<Integer>[] partition(int[] numbers,List<int[]> queries) throws Exception{
HashSet<Integer> set0 = new HashSet<>();
HashSet<Integer> set1 = new HashSet<>();
for (int i:numbers) {
set0.add(i);
}
for (int[] query:queries) {
if(set0.contains(query[0])){
set0.remove(query[1]);
set1.add(query[1]);
}else if(set0.contains(query[1])){
set0.remove(query[0]);
set1.add(query[0]);
}else{
throw new Exception("Data inconsitent");
}
}
return new HashSet[]{set0,set1};
}
}
```

Java solution

import java.util.*;

import java.util.stream.IntStream;

```
/**
* @author Andres Santana (andres.santana@gmail.com)
*/
public class ConstraintSatisfaction {
public static void main(String[] args) {
int n = 6;
List<List<Integer>> k = new ArrayList<>();
k.add(Arrays.asList(2, 1));
k.add(Arrays.asList(3, 4));
k.add(Arrays.asList(4, 6));
k.add(Arrays.asList(1, 3));
ConstraintSatisfaction constraintSatisfaction = new ConstraintSatisfaction();
List<Set<Integer>> result = constraintSatisfaction.disjointSubsets(n, k);
System.out.println(result);
}
public List<Set<Integer>> disjointSubsets(int n, List<List<Integer>> queries) {
Map<Integer, List<Integer>> map = new HashMap<>();
queries.forEach(query -> {
// TODO: assuming queries have only two members - can use iteration for general case
int memberOne = query.get(0);
int memberTwo = query.get(1);
map.computeIfAbsent(memberOne, k -> new ArrayList<>()).add(memberTwo);
map.computeIfAbsent(memberTwo, k -> new ArrayList<>()).add(memberOne);
});
Set<Integer> subsetOne = new HashSet<>();
Set<Integer> subsetTwo = new HashSet<>();
IntStream.range(1, n + 1).forEach(number -> {
List<Integer> blackList = map.get(number);
if (blackList != null) {
long intersectionSize = blackList.stream().filter(subsetOne::contains).count();
if (intersectionSize == 0) {
// there's no elements in common, so can add to subsetOne
subsetOne.add(number);
} else {
// there's at least one element in common, add to subsetTwo
subsetTwo.add(number);
}
} else {
// this number can be in any subset
subsetOne.add(number);
}
});
return Arrays.asList(subsetOne, subsetTwo);
}
}
```

import java.util.*;

import java.util.stream.IntStream;

/**

* @author Andres Santana (andres.santana@gmail.com)

*/

public class ConstraintSatisfaction {

public static void main(String[] args) {

int n = 6;

List<List<Integer>> k = new ArrayList<>();

k.add(Arrays.asList(2, 1));

k.add(Arrays.asList(3, 4));

k.add(Arrays.asList(4, 6));

k.add(Arrays.asList(1, 3));

ConstraintSatisfaction constraintSatisfaction = new ConstraintSatisfaction();

List<Set<Integer>> result = constraintSatisfaction.disjointSubsets(n, k);

System.out.println(result);

}

public List<Set<Integer>> disjointSubsets(int n, List<List<Integer>> queries) {

Map<Integer, List<Integer>> map = new HashMap<>();

queries.forEach(query -> {

// TODO: assuming queries have only two members - can use iteration for general case

int memberOne = query.get(0);

int memberTwo = query.get(1);

map.computeIfAbsent(memberOne, k -> new ArrayList<>()).add(memberTwo);

map.computeIfAbsent(memberTwo, k -> new ArrayList<>()).add(memberOne);

});

Set<Integer> subsetOne = new HashSet<>();

Set<Integer> subsetTwo = new HashSet<>();

IntStream.range(1, n + 1).forEach(number -> {

List<Integer> blackList = map.get(number);

if (blackList != null) {

long intersectionSize = blackList.stream().filter(subsetOne::contains).count();

if (intersectionSize == 0) {

// there's no elements in common, so can add to subsetOne

subsetOne.add(number);

} else {

// there's at least one element in common, add to subsetTwo

subsetTwo.add(number);

}

} else {

// this number can be in any subset

subsetOne.add(number);

}

});

return Arrays.asList(subsetOne, subsetTwo);

}

}

My first thought is to construct a directed graph and use BFS.

- popeye123 July 27, 2018Start with first node and put it in Hashset1.

for i= 1 to N.

1. If node 1 exists in any of the hashsets

then all child nodes(only 1 level) of first node go into other hashset. I know this is not a proper pseudo code. I am half-asleep