CareerCup

This is how it looks like in ZoomBA :

num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
   list([0:10]) -> { random(30) }
}
println ( ll )
// naive approach
pairs = join ( [0:num_lists], [0:num_lists] ) :: {
   i = $.0 ; j = $.1
   continue ( i >= j )
   intersection = ll[i] & ll[j]
   size( intersection ) >= 3 // that is the condition ?
}
println ( pairs )

A very complex - and *tries to be smart* approach. Not entirely sure if it is worth it, I would suggest - NO.

num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
   list([0:10]) -> { random(30) }
}
println ( ll )
// smarter approach
d = fold( ll, dict() ) -> {
      for ( inx : [0:size(ll)] ){
         l = ll[inx]
         for ( item : l ){
           if ( item @ $.p ){
              $.p[item] += inx
           } else {
              $.p[item] = set(inx)
           }
         }
      }
      $.p
   }
// find all items that existed in more than one lists
entries = select ( d ) :: {  size( $.o.value ) >= 2  }
println ( entries )
// make pairwise
all_pairs = fold ( entries , dict() ) -> {
    list_indices = $.o.value
    // create pair from values
    pair = comb( list_indices , 2 )
    for ( p : pair ){
      k_p = str(p,',')
      if  ( k_p @ $.p ){
        $.p[k_p] += $.o.key
      } else {
         $.p[k_p] = list( $.o.key )
      }
    }
    $.p
}
println ( all_pairs )
// select all entries with value length more than 2
valid_list_pairs = select ( all_pairs ) :: { size( $.o.value ) > 2 }
println ( valid_list_pairs )

Runtime for this is O(n x m) where `n` is the number of integers in all lists and `m` is the number of unique pairs of lists. Worst case performance is when all lists are exactly the same.

function hash (pair) {
  return pair.join(',')
}
function pair (list) {
  var i = 0
  var j = i + 1
  var pairs = []
  for (; j < list.length; j = ++i + 1) {
    while (j < list.length) {
      pairs.push([list[i], list[j++]])
    }
  }
  return pairs
}
module.exports = function (lists) {
  var i = 0
  var list_ids = []
  for (; i < lists.length; ++i) {
    list_ids[i] = i
  }
  var list_pairs = pair(list_ids)
  var pair_map = {}
  for (i = 0; i < list_pairs.length; ++i) {
    pair_map[hash(list_pairs[i])] = 0
  }
  var elements = {}
  for (i = 0; i < lists.length; ++i) {
    var list = lists[i]
    for (var j = 0; j < list.length; ++j) {
      var element = list[j]
      if (!elements[element]) {
        elements[element] = [i]
      } else {
        var l = elements[element].length
        if (elements[element][l - 1] !== i) {
          elements[element].push(i)
        }
      }
    }
  }
  for (var key in elements) {
    if (({}).hasOwnProperty.call(elements, key)) {
      element = elements[key]
      if (element.length > 1) {
        var pairs = pair(element)
        for (i = 0; i < pairs.length; ++i) {
          var pair_hash = hash(pairs[i])
          pair_map[pair_hash]++
        }
      }
    }
  }
  var solutions = []
  for (key in pair_map) {
    if (({}).hasOwnProperty.call(pair_map, key)) {
      if (pair_map[key] >= 3) {
        solutions.push(key)
      }
    }
  }
  return solutions

}

var solutions = module.exports([
  [1, 2, 3, 4, 5, 6],
  [2, 7, 4, 5],
  [2, 5, 1, 11, 12],
  [11, 13, 15, 12, 4, 7, 2]
])

console.log(JSON.stringify(solutions))

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

int main ()
{
 
   std::vector< std::vector<int> > lists = { {1,2,3,4,5}, {4,5,6,2,3}, {11,10,9,3,5,6,2}, {4,6,7,9}, {2,3,4,5} };
   
   for( auto& list: lists )
   {
       std::sort( std::begin(list),std::end(list) );
   }
   std::vector<int> difference;
   
   std::vector< std::pair<int,int> > result;
   for( size_t i = 0; i < lists.size()-1 ; ++i )
   {
       for( size_t j = i+1; j < lists.size(); ++j )
       {
          std::set_intersection( std::begin(lists[i]), std::end(lists[i]),  std::begin(lists[j]), std::end(lists[j]), std::back_inserter(difference) );         
         
          if(difference.size() > 3)
          {
              result.push_back(std::pair<int,int>(i,j));
          }
          difference.clear();
       }
   }
  
  for (auto& ele: result)
  {
      std::cout << ele.first+1 << " " << ele.second+1 <<"\n";
  }
}

O(N)

#include <vector>
#include <unordered_map>
#include <stdio.h>

void PrintOverlapping(const std::vector<std::vector<int>>& lol)
{
   struct occuranceEntry
   {
      int lastList = -1, cnt = 0;
   };
   std::unordered_map<int, occuranceEntry> occurances;

   for (int i = 0; i < (int)lol.size(); i++)
   {
      for (int j = 0; j < (int)lol[i].size(); j++)
      {
         occuranceEntry& e = occurances[lol[i][j]];
         if (e.lastList != i)
         {
            e.lastList = i;
            if (++e.cnt == 3)
               printf("%d,", lol[i][j]);
         }
      }
   }
}

int main()
{
   PrintOverlapping({ {1, 9, 2, 4, 3}, 
                      {2, 3, 3, 5, 7}, 
                      {1, 2, 4, 7, 2}, 
                      {4, 5} }); //output = 2,4,
}

Brute Force Approach: For 2 lists of length n1 and n2, finding out overlaps will take O(n1+n2). For n lists, choose 2 lists in n*(n-1)/2 ways . So final Time Complexity = O(n^3)

Here is what I think the Pseudo code can be:

Step 1: Count number of list and name it as as listCount
Step 2: Create an Array called arrayOfLists of HashMap<Integer,Integer> having length as listCount(each index corresponds to list index). the first Integer argument of HashMap tells the list number of overlapping list. The second Integer argument tells count about how many characters of both lists are overlapping.
Step 3: Create a Hashmap<Integer,list<Integer>> called clashMap: the first argument is number, the second is to store all overlapping lists that have this number.
Step 4: Iterate through all numbers of List one by one and put them into clashMap. If clashMap already had it, then check if present list number is already present in its list. If not add the list number in list. And also iterate this list and update arrayOfList:go to index of present list in arrayOfList and if it does not have the overlapping list, add it with count of overlapping characters as 1; otherwise increment that count.

when we have iterated through all the numbers we will have arrayOfLists telling us each list is overlapping with how many characters with which list. So we can then extract how many are overlapping with more then 3 elements.

The complexity will be O(n+k). where n is total number of elements in all list. And k is the number of Lists.

How about this Java code? Comments are welcomed... O(NM)

class Pair {
	int list1;
	int list2;
	
	public Pair(int l1, int l2) {
		this.list1 = l1;
		this.list2 = l2;
	}
	public String toString() {
		return "{"+list1+","+list2+"}";
	}
}

public class Overlapping {
	
	public List<Pair> findOverlapping(int a[][]) {
		
		List<Map<Integer, Integer>> list = new LinkedList<Map<Integer, Integer>>();
		for(int i=0; i < a.length; i++) {
			Map<Integer,Integer> numbers = new HashMap<Integer,Integer>();
			for(int j=0; j < a[i].length; j++) {
				numbers.put(a[i][j], 1);
			}
			list.add(numbers);
		}
		
		List<Pair> pairs = new LinkedList<Pair>();
		for(int i=0; i < a.length; i++) {
			int matches = 0;
			for(int j=i+1; j < a.length; j++) {
				Map<Integer,Integer> counter1 = list.get(i);
				Map<Integer,Integer> counter2 = list.get(j);
				for(Integer ival: counter1.keySet()) {
					if(counter2.get(ival) != null)
						matches++;
				}
				if(matches >= 3) {
					pairs.add(new Pair(i,j));
					break;
				}
			}
		}
		return pairs;
	}

	public static void main(String args[]) {
		/*
		 * {0,1},{1,3},{2,3}
		 */
		int list[][] = new int[][]{
			{ 1, 2, 3, 4, 4, 5, 6},
			{ 2, 7, 4, 5 },
			{ 2, 5, 1, 11, 12 },
			{ 11, 13, 15, 12, 4, 7, 2 }
		};
		Overlapping pi = new Overlapping();
		List<Pair> pairs = pi.findOverlapping(list);
		for(Pair pair: pairs) {
			System.out.print(pair);
		}
	}
}