## Microsoft Interview Question for Software Engineers

• 2

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

My first thought is to construct a directed graph and use BFS.
Start 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = *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)``````

Comment hidden because of low score. Click to expand.
0

Would you mind explaining the code and your thought process just so I can understand it better?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am thinking more in the lines of red black trees. Make a graph, with an edge for every pair in K. 1->black, it's neighbors red and their neighbors black. Like that.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

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) {
}

for (int[] query:queries) {
if(set0.contains(query)){
set0.remove(query);
}else if(set0.contains(query)){
set0.remove(query);
}else{
throw new Exception("Data inconsitent");
}
}
return new HashSet[]{set0,set1};
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't add a comment that contains code with my solution. This sucks!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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<>();

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
} else {
// there's at least one element in common, add to subsetTwo
}
} else {
// this number can be in any subset
}
});
return Arrays.asList(subsetOne, subsetTwo);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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<>();

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
} else {
// there's at least one element in common, add to subsetTwo
}
} else {
// this number can be in any subset
}
});
return Arrays.asList(subsetOne, subsetTwo);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simple bipartite checking question. The queries represent the edges and finally try to check if the resultant graph is a bipartite graph.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a bipartite graph. Apply DFS , keep the depth during DFS. Place odd depth vertices in one set, even depth vertices in the second set

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.