CareerCup

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

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)

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.

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

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

Can't add comment with code :(

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

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.

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

public static Dictionary<int, int> GenerateSet()
 {
}

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