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


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