CareerCup

Please explain what intersection means here. What is the inherent logic to solve the problem?. Giving just the code is not enough.
Could anyone provide a C++ solution to the problem?

This can be done in roughly O(nm) complexity and O(nm) memory where n is the number of elements that are in all lists and m is the number of lists

Create a Set Union to track the Intersections of lists
Use a HashMap to map integers to their set

public static void printIntersections(LinkedList<Integer> lists){
    HashMap<Integer,Integer> setUnionMap = new HashMap<Integer,Integer>();
    HashMap<Integer,Integer> elementMembershipMap = new HashMap<Integer,Integer>();
    
    //attach all the integers together and build the set union list up
    for(LinkedList<Integer> list : lists){
        Iterator<Integer> iterator = list.iterator();
        if(!interator.hasNext()){
            continue;
        }
        Integer name = iterator.next();
        setUnionMap.put(name, null);
        while(iterator.hasNext()){
            Integer element = iterator.next();
            Integer parent = elementMembershipMap.get(element);
            if(parent == null){
                elementMembershipMap.put(element, name);
            }
            else{
                parent = getParent(parent, setUnionMap);
                setUnionMap.put(name, parent);
            }
        }
    }
    
    //invert the set union to construct collections of list names
    HashMap<Integer, Collection<Integer>> groupMembershipMap = new HashMap<Integer, Collection<Integer>>();
    for(Integer setName : setUnionMap.keySet()){
        Integer parent = getParent(setName, setUnionMap);
        if(parent == null){
            ArrayList<Integer> col = new ArrayList<Integer>();
            col.add(setName);
            groupMembershipMap.put(setName, col);
        }
        else{
            Collection<Integer> col = groupMembershipMap.get(parent);
            col.add(setName);
        }
    }

    //output the list names
    for(Collection<Integer> valueSet : groupMembershipMap.getValues()){
        StringBuilder line = new StringBuilder();
        Iterator<Integer> iterator = valueSet.iterator();
        while(iterator.hasNext()){
            if(line.length() > 0){
                line.append(", ");
            }
            line.append(String.parseInt(iterator.next()));
        }
        System.out.println(line.toString());
    }
}

private static Integer getParent(Integer lookUp, HashMap<Integer,Integer> unionMap){
    Integer parentName = unionMap.get(lookUp);
    if(parentName == null){
        return lookUp;
    }
    Integer root = getParent(parentName, unionMap);
    if(root != parentName){
        unionMap.put(lookUp, root);
    }
    return root;
}

O(nm) time complexity and I think O(n) space

public class IntersectFinder
{
	public ArrayList<ArrayList<Integer>> findIntersect(ArrayList<LinkedList<Integr>> allLists) throws InvalidInputException
	{
			if(allLists==null||allLists.size()==0)
			{
					throw new InvalidInputException();
			}
			Map<Integer,ArrayList<Integer>> setsMap=findIntersectingSets(alllists);
			
			//Iterate through the map and store all sets into a single array list
			ArrayList<ArrayList<Integer>> intersectingLists=new ArrayList<ArrayList<Integer>>();
			for(Map.Entry<Integer,ArrayList<Integer>> me:setsMap.entrySet())
			{
				intersectingLists.add(me.getValue());
			}
			return intersectingLists;
			
	}
	private Map<Integer,ArrayList<Integer>> findIntersectingSets(ArrayList<LinkedList<Integer>> lists)
	{
		Map<Integer,ArrayList<Integer>> sets=new HashMap<Integer,ArrayList<Integer>>();
		for(LinkedList<Integer> ls:lists)
			{
				//Navigate to the last entry of the current list
				Integer m=ls.size()-1;
				ArrayList<Integer> set;
				//check if this last alue exists in the map(Is there another list we've already seen that intersects with this one?)
				if(sets.contains(m))
				{
					set=sets.get(m);//If tail value exists in the map, get the corresponding value(Array list of head values from other lists that have the same tail)
					set.add(ls.get(0));
					sets.put(m,set);
				}else{
					set=new ArrayList<Integer>(1);
					set.add(m);
					sets.put(m,set);
				}
			}
			return sets;
	}
}

Can you clarify on the question.
What does intersection of Linked Lists mean? Two or more common elements in the same order?

Seems easy enough just make a Hash Table with the key been the Data and the value been a list of heads that have them.

Then look them up.

public List<Tuple<int, int>> GetIntersections(List<LinkedList<int>> lists)
{
	List<Tuple<int, int>> result = List<Tuple<int, int>>();
	var combinations = new 	HashSet<string>();
	var map = new Dictionary<int, List<int>>();

	foreach(LinkedList<int> ll in lits)
	{
		Node<int> current = ll.Head;
		while(current != null)
		{
			if(map.ContainsKey(current.Data))
			{
				map[current.Data].Add(ll.Head.Data)
			}
			else
			{
				map.Add(current.Data, new List<int> { ll.Head.Data };
			}
		}
	}
	
	foreach(LinkedList<int> ll in lits)
	{
		Node<int> current = ll.Head;
		while(current != null)
		{
			foreach(var head in map[current.Data])
			{
				if(head != ll.Head.Data)
				{
					// Find combination and reverse combination exist 
					// so they are are unique
					string hash = head + "," + ll.Head.Data;
					string reverseHash =  ll.Head.Data + "," + head;

					if(!combinations.Contains(hash) &&
					   !combinations.Contains(reverseHash)
					{ 
						combinations.Add(hash);
						result.Add(new Tuple<int, int>(ll.Head.Data, head);
					}
				}
			}
		}
	}

	return result;
}

If we are allowed to assume that the numbers are not bigger than K (for example 1000 or something like that) then we can use union-find data structure instead of hash maps. UF allows us to union and find intersection in amortized O(1). As a result what we need is to check union in two nested loops for first elements in each LinkedList. UF requires O(K) memory. Time complexity is bound above by double loop to go through all elements in lists once -> O(N * M).

import java.util.*;

/**
 * Created by Igor_Sokolov on 6/16/2015.
 */
public class CareerCup_5991240778645504 {
    private static final int K = 1000;

    private static class UF {
        int[] parent;
        int[] rank;

        public UF(int size) {
            this.parent = new int[size];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }

            this.rank = new int[size];
            Arrays.fill(rank, 1);
        }

        public void union(int i, int j) {
            int pi = find(i);
            int pj = find(j);

            if (rank[pi] == rank[pj]) {
                parent[pi] = pj;
                rank[pj]++;
            } else if (rank[pi] > rank[pj]) {
                parent[pj] = pi;
            } else {
                parent[pi] = pj;
            }
        }

        public int find(int j) {
            int p = j;
            while (parent[p] != p) {
                p = parent[p];
            }

            while (parent[j] != p) {
                int x = parent[j];
                parent[j] = p;
                j = x;
            }

            return p;
        }
    }
    public static void main(String[] args) {
        LinkedList<Integer>[] lists = prepareData();

        List<List<Integer>> result = findIntersections(lists);

        printResult(result);
    }

    private static void printResult(List<List<Integer>> result) {
        for (List<Integer> list: result) {
            StringBuilder sb = new StringBuilder();
            for (int i: list) {
                sb.append(i).append(' ');
            }
            System.out.println(sb);
        }
    }

    private static LinkedList<Integer>[] prepareData() {
        LinkedList<Integer>[] lists = new LinkedList[5];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new LinkedList<>();
        }

        lists[0].addAll(Arrays.asList(1, 2, 3, 4, 5));
        lists[1].addAll(Arrays.asList(6, 7, 8, 4, 5));
        lists[2].addAll(Arrays.asList(8, 9, 10, 11, 12));
        lists[3].addAll(Arrays.asList(13, 14, 15, 12));
        lists[4].addAll(Arrays.asList(16, 17, 18 ));
        return lists;
    }

    private static List<List<Integer>> findIntersections(LinkedList<Integer>[] input) {
        UF uf = new UF(K);
        final int N = input.length;

        for (int i = 0; i < N; i++) {
            int head = input[i].getFirst();
            for (int v : input[i]) {
                uf.union(head, v);
            }
        }

        boolean[] visited = new boolean[N];
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                int x = input[i].getFirst();

                List<Integer> list = new ArrayList<>();
                list.add(x);

                for (int j = i + 1; j < N; j++) {
                    int y = input[j].getFirst();
                    if (uf.find(x) == uf.find(y)) {
                        visited[j] = true;
                        list.add(y);
                    }
                }

                result.add(list);
            }
        }

        return result;
    }
}

Actually do we need to print just the starting node of the 5 linked lists or something else and what does that intersection mean in that question and why the hell we care about intersection if they are given as separate lists.ACTUALLY WHAT IS THE MEANING OF THIS LAME QUESTION.

Algorithm:

1) Go through first list till the end node. Store this end node in the hash.
2) Now if any lists among remaining m-1 lists has same end node then that list is intersecting with this list. Otherwise keep on saving the end nodes only.

Time Complexity: O(nm)
Space Complexity: O(m) Since only last node on m lists is stored in hash.

We can further reduce the time complexity to O(m) if we keep track of last node in our linked list implementation.

why is 6 8 not in the answer ?

Put all list elements in hashtable 
Linked list data as key and value as head of each linked list. 
Traverse hashtable for a list which is having two or more than two elements.
Print elements of list.
for eg.
HashTable will look like..
Key(node data)  Value(headnode)
1---1
2---1
3---1
4---1-->6
5---1--->6
6---6
7---6
8---6--->8
9---8
10--8
11--8
12--8-->13
13--13
14---13
15---13
16---16
17---16
18---16
ANS: 1 6 
	  6 8
          8 13