Microsoft Interview Question
Software EngineersCountry: 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);
}
}
public static Dictionary<int, int> GenerateSet()
{
int[,] set = { { 1, 2 }, { 1, 3 }, { 1, 1 }, { 2, 4 },{ 1, 5 },{ 4, 9 },{ 5, 4 },{ 2, 8 } };
Dictionary<int, int> map = new Dictionary<int, int>();
for(int i = 0; i < set.GetLength(0); i++)
{
if (!map.ContainsKey(set[i, 0]) && !map.ContainsKey(set[i, 1]) && set[i, 0] != set[i, 1])
{
map.Add(set[i, 0], set[i, 1]);
map.Add(set[i, 1], set[i, 0]);
}
else if (map.ContainsKey(set[i, 0]) && map[set[i, 0]] < set[i, 1])
{
map[set[i, 0]] = set[i, 1];
}
if (!map.ContainsKey(set[i, 0]))
{
map.Add(set[i, 0], set[i, 1]);
}
if (!map.ContainsKey(set[i, 1]))
{
map.Add(set[i, 1], 0);
}
}
Dictionary<int, int> result = new Dictionary<int, int>();
foreach (KeyValuePair<int, int> key in map)
{
if (key.Value != 0)
{
result.Add(key.Key, key.Value);
}
}
return result;
}
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