Google Interview Question Software Engineers
Country: United States
var y = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]];
var x = new Map(y);
var foundOutlier;
forLoop: for(var key of x.keys()) {
var index = 0;
for(var index = 0, j = y.length; index < j; index++) {
if(y[index].indexOf(key) < 0) {
foundOutlier = y[index];
break forLoop;
}
}
}
var y = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]];
var x = new Map(y);
var foundOutlier;
forLoop: for(var key of x.keys()) {
var index = 0;
for(var index = 0, j = y.length; index < j; index++) {
if(y[index].indexOf(key) < 0) {
foundOutlier = y[index];
break forLoop;
}
}
}
var y = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]];
var x = new Map(y);
var foundOutlier;
forLoop: for(var key of x.keys()) {
var index = 0;
for(var index = 0, j = y.length; index < j; index++) {
if(y[index].indexOf(key) < 0) {
foundOutlier = y[index];
break forLoop;
}
}
}
public String[] predictItemBasedSimilarity(List<String[]> list){
if(list == null) throw new IllegalArgumentException("List Null");
Map<String, Integer> ItemBasedSimilarityMap = new LinkedHashMap<>();
for(int i =0; i < list.size(); i++){ // evaluate score
String[] words = list.get(i);
if(words!= null)
for(int j =0; j < words.length; j++){
Integer count =
ItemBasedSimilarityMap.getOrDefault(words[j], new Integer(0));
count = count+1;
ItemBasedSimilarityMap.put(words[j],count );
}
}
String[] leastAppeared = null;
int min = Integer.MAX_VALUE;
for(int i =0; i < list.size(); i++) { //rank by score
String[] words = list.get(i);
int sum =0;
if(words!= null){
for (int j = 0; j < words.length; j++) {
Integer count = ItemBasedSimilarityMap.get(words[j]);
sum += count;
}
}
if(min > sum) {
min = sum;
leastAppeared = words;
}
System.out.println(" sum "+ sum + " min "+ min +" i "+ i);
}
return leastAppeared;
}
public static String[] detectOutlier(String [][] list)
{
Map<Integer, String[]> scores = new LinkedHashMap<Integer, String[]>();
for(String [] s : list)
{
int score = 0;
for (String element: s)
{
char c = element.toCharArray()[0];
score+=Character.getNumericValue(c);
}
scores.put(score, s);
}
int max = Collections.max(scores.keySet());
return scores.get(max);
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
public class LeastCommonList {
public static void main(String[] args) {
int n = 3;
// Here aList is an ArrayList of ArrayLists
List<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>(n);
// Create n lists one by one and append to the
// master list (ArrayList of ArrayList)
ArrayList<Integer> a1 = new ArrayList<Integer>();
a1.add(1);
a1.add(2);
aList.add(a1);
ArrayList<Integer> a2 = new ArrayList<Integer>();
a2.add(5);
aList.add(a2);
ArrayList<Integer> a3 = new ArrayList<Integer>();
a3.add(1);
a3.add(2);
a3.add(2);
aList.add(a3);
System.out.println(getUncommon(aList));
}
public static ArrayList<Integer> getUncommon(List<ArrayList<Integer>> list) {
Map<ArrayList<Integer>, AtomicInteger> rank = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
ArrayList<Integer> innerList = list.get(i);
Set<Integer> seen = new HashSet<>();
for (int j = 0; j < innerList.size(); j++) {
Integer aElement = innerList.get(j);
if(seen.contains(aElement)) {
continue;
}else {
seen.add(aElement);
}
int counter = 0;
for (int k = 0; k < list.size(); k++) {
List<Integer> nextList = list.get(k);
if (nextList == innerList) {
continue;
}
for (int l = 0; l < nextList.size(); l++) {
Integer bElement = nextList.get(l);
if (aElement.equals(bElement)) {
counter++;
break;
}
}
}
rank.putIfAbsent(innerList, new AtomicInteger(0));
rank.get(innerList).addAndGet(counter);
}
}
List<ArrayList<Integer>> keylist = new ArrayList<ArrayList<Integer>>(rank.keySet());
Collections.sort(keylist, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> x, ArrayList<Integer> y) {
return rank.get(y).get() - rank.get(x).get();
}
});
System.out.println(rank);
return keylist.get(keylist.size()-1);
}
}
public static String[] detectOutlier(String [][] list)
{
Map<Integer, String[]> scores = new LinkedHashMap<Integer, String[]>();
for(String [] s : list)
{
int score = 0;
for (String element: s)
{
char c = element.toCharArray()[0];
score+=Character.getNumericValue(c);
}
scores.put(score, s);
}
int max = Collections.max(scores.keySet());
return scores.get(max);
}
public static String[] detectOutlier(String [][] list)
{
Map<Integer, String[]> scores = new LinkedHashMap<Integer, String[]>();
for(String [] s : list)
{
int score = 0;
for (String element: s)
{
char c = element.toCharArray()[0];
score+=Character.getNumericValue(c);
}
scores.put(score, s);
}
int max = Collections.max(scores.keySet());
return scores.get(max);
}
from collections import Counter
def disjoint_sets(list_of_sets):
weight = Counter()
for s in list_of_sets:
weight.update(s)
for c in weight.keys():
weight[c] = 1 if weight[c] > 1 else 0
minimum_set_weight = len(weight)*len(list_of_sets)
minimum_set_length = 0
minimum_set = None
for s in list_of_sets:
set_weight = sum(weight[e] for e in s)
if set_weight > minimum_set_weight:
continue
if set_weight == minimum_set_weight and len(s) <= minimum_set_length:
continue
minimum_set_weight = set_weight
minimum_set = s
return minimum_set
Assumption: The array elements are alphabets
M = elements in each set
N = total number of sets
Time complexity = M*N
Space complexity = M*N
def oddManOut(aListOfSets):
score = {}
for letter in "abcdefghijklmnopqrstuvwxyz":
score[letter] = 0
allSets = []
for member in aListOfSets:
allSets.extend(member)
for member in allSets:
score[member] += 1
finalScore = [0]*len(aListOfSets)
for val in score.keys():
for i in range(len(aListOfSets)):
if val in aListOfSets[i]:
finalScore[i] += score[val]
return aListOfSets[finalScore.index(min(finalScore))]
private static HashSet<string> FindUnique(List<HashSet<string>> input)
{
HashSet<string> UniqueSet = input[0];
HashSet<string> AllChars = UniqueSet;
for(int i = 1; i < input.Count; i++)
{
bool isFound = false;
foreach(string s in input[i])
{
if(AllChars.Contains(s))
{
isFound = true;
if(UniqueSet != null && UniqueSet.Contains(s))
{
UniqueSet.Clear();
}
}
else
{
AllChars.Add(s);
}
if(!isFound)
{
UniqueSet = input[i];
}
}
}
return UniqueSet;
}
private static HashSet<string> FindUnique(List<HashSet<string>> input)
{
HashSet<string> UniqueSet = input[0];
HashSet<string> AllChars = UniqueSet;
for(int i = 1; i < input.Count; i++)
{
bool isFound = false;
foreach(string s in input[i])
{
if(AllChars.Contains(s))
{
isFound = true;
if(UniqueSet != null && UniqueSet.Contains(s))
{
UniqueSet.Clear();
}
}
else
{
AllChars.Add(s);
}
if(!isFound)
{
UniqueSet = input[i];
}
}
}
return UniqueSet;
}
Javascript solution
var findSetWithLeastCommon = function(grid)
{
if(grid.length === 0)
{
return grid;
}
let common_set = intersection(grid[0],grid[1]);
let min_intersection_count = common_set.length;
let min_intersection_set = {};
min_intersection_set[min_intersection_count] = grid[1];
for(let i=2;i<grid.length;i++)
{
common_set = intersection(common_set,grid[i]);
if(common_set.length < min_intersection_count)
{
min_intersection_count = common_set.length;
min_intersection_set[min_intersection_count] = grid[i];
}
}
return min_intersection_set[min_intersection_count];
};
function intersection(set1,set2)
{
if(Array.isArray(set1) && Array.isArray(set2))
{
var grid = [set1,set2];
return grid.reduce((a, b) => a.filter(c => b.includes(c)));
}else{
if(set1 != set2)
{
return [];
}else{
return set1;
}
}
}
var grid = [['a','b','c','d'], ['a','b','f'], ['a','b','h','i'], ['a','b','l','m'], ['j','k','l','m','c']];
findSetWithLeastCommon(grid);
s = [('a','x','c','d'),('a','b','f','g'),('a','b','h','i'),('j','f','l','m')]
d = {}
for i,ss in enumerate(s):
o = s[i+1:] #checking each pair of sets only once
for oo in o:
m = len(set(oo) & set(ss)) #distance between sets is an intersection
sm = d.get(ss, 0) #distance is 0 by default
om = d.get(oo, 0)
#print ("ss=%s oo=%s, m=%2d, sm=%2d, om=%2d" % (ss,oo,m,sm,om))
d.update({ss:m+sm}) #increase distance for both sets
d.update({oo:m+om})
#smallest distance is the outlier
print ([dd for dd in sorted(d.items(), key = lambda kv:kv[1])].pop(0))
This question has some ambiguity so I am assume that set is compared against all the unique characters in super set.
The following code returns either a set that has no common element with other sets or a set that has minimum common elements with superset containing all the unique characters of all the sets.
public char[] getMostUniqueSet(char [][] allSets){
int minimum = Integer.MAX_VALUE;
char [] minArray = new char[0];
Map<Character,Integer> charMap = new HashMap<>();
for(char [] setArray: allSets){
for(char c : setArray)
charMap.put(c, charMap.getOrDefault(c, 0) + 1);
}
for(char [] setArray: allSets){
int tempMin = 0;
for(char c : setArray)
if(charMap.get(c) > 1)tempMin++;
if(tempMin == 0){
return setArray;
}else if(tempMin < minimum){
minArray = setArray;
minimum = tempMin;
}
}
return minArray;
}
inp = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]]
count_intersections = []
for each_list in inp:
temp = [i for i in inp if i != each_list]
#print(temp)
_max_ = 0
for each in temp:
count_intersection = len(set(each_list).intersection(set(each)))
if count_intersection > _max_:
_max_ = count_intersection
count_intersections.append(_max_)
result = inp[count_intersections.index(min(count_intersections))]
print(result)
inp = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]]
count_intersections = []
for each_list in inp:
temp = [i for i in inp if i != each_list]
#print(temp)
_max_ = 0
for each in temp:
count_intersection = len(set(each_list).intersection(set(each)))
if count_intersection > _max_:
_max_ = count_intersection
count_intersections.append(_max_)
result = inp[count_intersections.index(min(count_intersections))]
print(result)
inp = [["a","b","c","d"], ["a", "b", "f", "g"], ["a", "b", "h", "i"], ["j", "k", "l", "m"]]
count_intersections = []
for each_list in inp:
temp = [i for i in inp if i != each_list]
#print(temp)
_max_ = 0
for each in temp:
count_intersection = len(set(each_list).intersection(set(each)))
if count_intersection > _max_:
_max_ = count_intersection
count_intersections.append(_max_)
result = inp[count_intersections.index(min(count_intersections))]
print(result)
package T9;
import java.util.ArrayList;
public class T9Class {
private static ArrayList<String> input = new ArrayList<>();
private static ArrayList<ArrayList<String>> inputSet = new ArrayList<>();
private static ArrayList<ArrayList<Integer>> scoreSet = new ArrayList<>();
public static void main(String[] args) {
// TODO Auto-generated method stub
// [a,b,c,d] [a.b.f.g] [a,b,h,i] [j,k,l,m]
// find least in common set
init();
processing();
analyze();
}
private static void processing() {
// check one by one with the similarity
for (int i = 0; i < inputSet.size(); i++) {
ArrayList<Integer> score = new ArrayList<>();
ArrayList<String> getOne = inputSet.get(i);
for (int j = 0; j < inputSet.size(); j++) {
if(i == j) continue;
ArrayList<String> getTwo = inputSet.get(j);
score.add(check(getOne, getTwo));
}
scoreSet.add(score);
}
System.out.println(scoreSet);
}
private static void analyze() {
// find the lowest sum
int findOut = 10000000;
int group = 0;
for(int i = 0; i < scoreSet.size(); i++) {
ArrayList<Integer> getS = scoreSet.get(i);
int sum = 0;
for(int j = 0; j < getS.size(); j++) {
sum= sum + getS.get(j);
}
if(findOut > sum) {
findOut = sum;
group = i;
}
}
System.out.println("find out sum : " + findOut);
System.out.println("final group number (starting from 0) : "+group);
}
private static int check(ArrayList<String> getOne, ArrayList<String> getTwo) {
int retVal = 0;
for (int i = 0; i < getOne.size(); i++) {
String temp = getOne.get(i);
for (int j = 0; j < getTwo.size(); j++) {
if(temp.equalsIgnoreCase(getTwo.get(j))) {
retVal++;
}
}
}
return retVal;
}
private static void init() {
input.add("a");
input.add("b");
input.add("c");
input.add("d");
inputSet.add(input);
input = new ArrayList<String>();
input.add("a");
input.add("b");
input.add("f");
input.add("g");
inputSet.add(input);
input = new ArrayList<String>();
input.add("a");
input.add("b");
input.add("h");
input.add("i");
inputSet.add(input);
input = new ArrayList<String>();
input.add("j");
input.add("k");
input.add("l");
input.add("m");
inputSet.add(input);
System.out.println(inputSet);
}
}
import java.util.ArrayList;
import java.util.Arrays;
public class GoogleSubsetLeastCommon {
public static void compare(ArrayList<ArrayList<String>> data) {
ArrayList<String> temp1;
ArrayList<String> temp2;
int countMaxUncommon = 0;
ArrayList<String> ret = null;
for (int i = 0; i < data.size(); i++) {
if(i != 0) {
for (int j = i-1; j >= 0; j--) {
temp1 = new ArrayList<String>(data.get(i));
temp2 = new ArrayList<String>(data.get(j));
temp1.removeAll(temp2);
if(temp1.size() > countMaxUncommon) {
countMaxUncommon = temp1.size();
ret = data.get(i);
}
}
}
}
System.out.println(ret);
}
public static void main(String[] args) {
ArrayList<ArrayList<String>> data = new ArrayList<>();
data.add(new ArrayList<>(Arrays.asList("a", "b", "c", "d")));
data.add(new ArrayList<>(Arrays.asList("a", "b", "f", "g")));
data.add(new ArrayList<>(Arrays.asList("a", "q", "h", "i")));
data.add(new ArrayList<>(Arrays.asList("j", "k", "l", "m")));
compare(data);
}
}
class UncommonSubsets(object):
def solve(self, inp):
n = len(inp)
# Remove each common char from all sets
for i in range(n):
tmp = set()
for c in inp[i]:
for j in range(n):
if j != i and c in inp[j]:
inp[j].remove(c)
tmp.add(c)
for c in tmp:
inp[i].remove(c)
maxlen = 0
ans = 0
# Get the index of set with largest length i.e most no of uncommon chars
for i in range(n):
if len(inp[i]) > maxlen:
maxlen = len(inp[i])
ans = i
return ans
if __name__ == "__main__":
s = UncommonSubsets()
inp = [{'a', 'b', 'c'}, {'b', 'c', 'd'}, {'c', 'd', 'e'}, {'f', 'g', 'h'}]
print(s.solve(inp))
final Map<String, Integer> counts = new HashMap<>();
final Map<Set<String>, Map<String, Integer>> subCounts = new HashMap<>();
items.forEach(aSet -> {
final Map<String, Integer> aSubCounts = new HashMap<>();
aSet.forEach(item -> {
if (!subCounts.containsKey(item)) aSubCounts.put(item, 0);
aSubCounts.put(item, aSubCounts.get(item) + 1);
if (!counts.containsKey(item)) counts.put(item, aSubCounts.get(item));
else if (counts.containsKey(item) && aSubCounts.get(item) > counts.get(item))
counts.put(item, aSubCounts.get(item));
});
if (counts.isEmpty()) counts.putAll(aSubCounts);
subCounts.put(aSet, aSubCounts);
});
final TreeMap<Integer, Set<String>> score = new TreeMap<>();
items.forEach(aSet -> {
int missing = 0;
for (String item : aSet) missing += counts.get(item) - subCounts.get(aSet).get(item);
score.put(missing, aSet);
});
return score.get(score.lastKey());
}
Disclaimer : I have not coded in a long time. I used python3 so spacing is important!
In the end I probably did not need the numpy.
import numpy as np
narray = np.array([['a','b','c','d'],['a','b','c','g'],['j','c','l','a'],['a','m','h','i'], ['x','z','a','b']])
numarrays = len(narray)
ContainedIn = 0
Total = 0
Cur = 0
CurIndex = -1
for i in range(numarrays):
Total = 0
for j in narray[i]:
ContainedIn = 0
for a in range(numarrays):
if j in narray[a]:
ContainedIn +=1
Total = Total + ContainedIn
if Cur == 0:
Cur = Total
if Cur > Total :
Cur = Total
CurIndex = i
print(narray[CurIndex])
import numpy as np
narray = np.array([['a','b','c','d'],['a','b','c','g'],['j','c','l','a'],['a','m','h','i'], ['x','z','a','b']])
numarrays = len(narray)
#print(numarrays)
ContainedIn = 0
Total = 0
Cur = 0
CurIndex = -1
for i in range(numarrays):
Total = 0
for j in narray[i]:
ContainedIn = 0
for a in range(numarrays):
if j in narray[a]:
ContainedIn +=1
Total = Total + ContainedIn
if Cur == 0:
Cur = Total
if Cur > Total :
Cur = Total
CurIndex = i
#print (Total, narray[i])
#print (j, narray[i], narray[a], ContainedIn)
print(narray[CurIndex])
is it [a,b] common in first three set ?
- Anonymous January 03, 2020