Given an array of sets, find the least common set. The least common set is also an outlier set, that has least in common with other sets. There are different ways to find the least common set. One ways is to use union-find to make all elements in a disjoint set. From the disjoint set, you can find a subset with the more elements than others. Then you scan each input set and count how many elements in the popular subset. The one with the smallest counts is the least common set.
There is another simple way. You use a map to store all counts for each elements. The key is element, the value is the count. You reset the map’s value, if the count is larger than 1, reset the count to 1. If the count is 1, reset to 0. Then you scan each input set to sum up the counts in the map. The set with the smallest counts is the least common set.
Google Interview Question :
Given an array of sets find the one that does not belong:
example: [[a,b,c,d], [a,b,f,g], [a,b,h,i], [j,k,l,m]]
output: [j,k,l,m]
We can see above that the first three sets have a subset [a,b,c] and the last one does not. Note: There may be a case where the outlier set does have elements contained in the input group. In this case we have the find the set that has the least in common with the other sets.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import java.util.*; public class FindLeastCommonSet3<T> { //Time O(m x n), Space O(mxn) public static Character[] disjoint_sets(Character[][] input){ Map<Character,Integer> mapCount = new HashMap<>(); int n = 0; //max length for (Character[] oneList: input) { n = Math.max(n, oneList.length); for (Character x: oneList) mapCount.put(x, mapCount.getOrDefault(x, 0)+1); } System.out.println(mapCount); for (Character ch: mapCount.keySet()) { int t = mapCount.get(ch); if (t > 1) mapCount. put(ch, 1); else mapCount.put(ch, 0); } int minCount = mapCount.size()*input.length; //max value Character[] res = new Character[n]; for (Character[] oneList : input) { int setCount = 0; for(Character ch: oneList) setCount += mapCount.get(ch); if (setCount > minCount) continue; if (setCount == minCount) continue; minCount = setCount; //find smaller one res = oneList; } return res; } public static void main(String[] args){ Character[][] input = {{'a','b','c','d'}, {'a','b','f','g'}, {'a','b','h','i'}, {'j','k','l','m'}}; Character[] b = disjoint_sets(input); System.out.println("Find least common set: " + Arrays.toString(b)); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//Time O(m x n), Space O(mxn) function disjointSets(input){ var mapCount = new Map(); var n = 0; //max length for (let oneList of input) { n = Math.max(n, oneList.length); for (let x of oneList) { if (mapCount.get(x) == null) mapCount.set(x, new Array()) let count = mapCount.get(x); mapCount.set(x, count+1); } } for (let ch of mapCount.keys()) { let t = mapCount.get(ch); if (t > 1) mapCount.set(ch, 1); else mapCount.set(ch, 0); } var minCount = mapCount.size*input.length; //max value var res = new Array(n); for (let oneList of input) { let setCount = 0; for(let ch of oneList) setCount += mapCount.get(ch); if (setCount > minCount) continue; if (setCount == minCount) continue; minCount = setCount; //find smaller one res = oneList; } return res; } var input = [['a','b','c','d'], ['a','b','f','g'], ['a','b','h','i'], ['j','k','l','m']]; var b = disjointSets(input); console.log(b); |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
from collections import Counter #Time O(mxn), Space O(mxn) def disjoint_sets(list_of_sets): map_count = Counter() for x in list_of_sets: map_count.update(x) print(map_count) for ch in map_count.keys(): map_count[ch] = 1 if map_count[ch] > 1 else 0 min_count = len(map_count)*len(list_of_sets) res = None for x in list_of_sets: set_count = sum(map_count[e] for e in x) if set_count > min_count: continue if set_count == min_count: continue min_count = set_count res = x return res input = [['a','b','c','d'], ['a','b','f','g'], ['a','b','h','i'], ['j','k','l','m']] min_set = disjoint_sets(input) print(min_set) |
Output:
Find least common set: [j, k, l, m]
O Notation:
Time complexity: O(m*n*),
m is number of input sets, n is average number elements in each set
Space complexity: O(m*n))
Download FindLeastCommonSet.java
Download FindLeastCommonSet.js
Download FindLeastCommonSet.py
Minimum Spanning Tree with union find (GitHub)
