Microsoft Interview Question for Software Engineers


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

- popeye123 July 27, 2018 | Flag Reply
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 = [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)

- adr July 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- robb.krakow July 27, 2018 | Flag
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.

- Hitesh July 26, 2018 | Flag Reply
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.

- adr July 27, 2018 | Flag Reply
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;
		}
		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};
	}
}

- dadakhalandhar August 03, 2018 | Flag Reply
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!

- andres.santana August 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't add comment with code :(

- andres.santana August 12, 2018 | Flag Reply
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<>();
        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);
    }
}

- Anonymous August 12, 2018 | Flag Reply
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<>();
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);
}
}

- Andres Santana August 12, 2018 | Flag Reply
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.

- sudharsansai@g.ucla.edu November 13, 2018 | Flag Reply
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

- cbd November 24, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More