Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

is it [a,b] common in first three set ?

- Anonymous January 03, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is it a,b common in first three set?

- no January 03, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- novice January 06, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- novice January 06, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- novoice January 06, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Ashis Kumar Chanda January 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 17, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure if it would pass the case when we have element counts with [2,2,2,2] and [1,1,1,8] . i wonder which would be the outlier here.

- mrxplek January 28, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

	}

}

- Anonymous January 12, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sreeni January 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nagara January 17, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- JM January 22, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))]

- Sleeba Paul January 27, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous February 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Programmer February 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ammuz February 15, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{ Input [J,K,L,M] =output [J,K,L,M] } Hence [J,K,L,M] is the relevant code of the output.

- Anonymous February 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

[j,k,l,m] =[j,k,l,m] hence [j,k,l,m] is the code of the output [j,k,l,m]

- syeda hansa February 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- MR February 29, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Raminder March 04, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- VK April 23, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- VK April 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- VK April 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- mannerh1 May 07, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- codelover June 26, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

aaaa

- Anonymous June 28, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- savi.honey2 July 07, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Yev August 29, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More