Google Interview Question


Country: United States
Interview Type: Phone Interview




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

'''
Solution:
1) Sort each word's character set and remove dublicate characters => sorted character set of word
2) put into hashtable with sorted character set as key and original word as value
3) iterate over all keys and print words

runtime: O(n*m*lg(m)), whereas m is the max length of the words and n is the number of words
space: O(n*m) 
'''
from collections import defaultdict

def getKey(word):
    return ''.join(sorted(set(word.lower())))

def printUniqueCharacterSetWords(text):
    words = text.split()
    ht = defaultdict(list)
    for word in words:
        ht[getKey(word)].append(word)   
    for v in ht.values():
        print(v)

printUniqueCharacterSetWords(
    "May student students dog studentssess " 
    "god Cat act tab bat flow wolf lambs Amy " 
    "Yam balms looped poodle john alice"
    )

'''
output:
['student', 'students', 'studentssess']
['looped', 'poodle']
['flow', 'wolf']
['dog', 'god']
['May', 'Amy', 'Yam']
['john']
['tab', 'bat']
['lambs', 'balms']
['Cat', 'act']
['alice']
'''

- Chris March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// ZoomBA 
words = ['May', 'student', 'students', 'dog', 'studentssess', 
'god', 'Cat', 'act', 'tab', 'bat', 'flow', 'wolf', 'lambs', 
'Amy', 'Yam', 'balms', 'looped', 'poodle', 'john', 'alice' ]
// now do magic 
m = mset( words ) -> {  k = $.o.toLowerCase() ; str(sset(k.value) ,'') }
fold ( m ) -> { println( $.value ) }

Now the output :

$ zmb tmp.zm 
[student, students, studentssess]
[tab, bat]
[Cat, act]
[john]
[alice]
[lambs, balms]
[May, Amy, Yam]
[looped, poodle]
[dog, god]
[flow, wolf]

- NoOne March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GroupWordsUniqueCharacters {

public static Comparator<String> ascendingStringComparator= new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
};
private String rootWord(String str)
{
Set<Character> sortedCharacters = new TreeSet<>();
for(int i=0;i<str.length();i++)
sortedCharacters.add(str.charAt(i));
StringBuilder buffer= new StringBuilder();
for(Character c:sortedCharacters){
buffer.append(c);
}
return buffer.toString();
}
public Map<String,List<String>> groupWords(String [] words){
Map<String,List<String>> resultMap= new TreeMap<>(); //sorted Map
for(String word:words){
String uniqueString=rootWord(word.toLowerCase());
if(resultMap.containsKey(uniqueString)){
resultMap.get(uniqueString).add(word);
}else{
List<String> similarWords= new ArrayList<>();
similarWords.add(word);
resultMap.put(uniqueString,similarWords);
}
}
return resultMap;
}
public static void main(String args[]){

GroupWordsUniqueCharacters grpWdUniqueChar = new GroupWordsUniqueCharacters();
String [] words={"May", "student", "students", "dog", "studentssess",
"god", "Cat", "act", "tab", "bat", "flow", "wolf", "lambs",
"Amy", "Yam", "balms", "looped", "poodle", "john", "alice" };
Map<String,List<String>> groupWordsMap=grpWdUniqueChar.groupWords(words);
for(Map.Entry<String, List<String>> orderMap:groupWordsMap.entrySet()){
List<String> row=orderMap.getValue();
Collections.sort(row,ascendingStringComparator);
if(row.size()>1){// single word
for(String word:row){
System.out.print(word);
System.out.print(" ");
}
System.out.println("");
}
}
}
}

- Diamond March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GroupWordsUniqueCharacters {

public static Comparator<String> ascendingStringComparator= new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
};
private String rootWord(String str)
{
Set<Character> sortedCharacters = new TreeSet<>();
for(int i=0;i<str.length();i++)
sortedCharacters.add(str.charAt(i));
StringBuilder buffer= new StringBuilder();
for(Character c:sortedCharacters){
buffer.append(c);
}
return buffer.toString();
}
public Map<String,List<String>> groupWords(String [] words){
Map<String,List<String>> resultMap= new TreeMap<>(); //sorted Map
for(String word:words){
String uniqueString=rootWord(word.toLowerCase());
if(resultMap.containsKey(uniqueString)){
resultMap.get(uniqueString).add(word);
}else{
List<String> similarWords= new ArrayList<>();
similarWords.add(word);
resultMap.put(uniqueString,similarWords);
}
}
return resultMap;
}
public static void main(String args[]){

GroupWordsUniqueCharacters grpWdUniqueChar = new GroupWordsUniqueCharacters();
String [] words={"May", "student", "students", "dog", "studentssess",
"god", "Cat", "act", "tab", "bat", "flow", "wolf", "lambs",
"Amy", "Yam", "balms", "looped", "poodle", "john", "alice" };
Map<String,List<String>> groupWordsMap=grpWdUniqueChar.groupWords(words);
for(Map.Entry<String, List<String>> orderMap:groupWordsMap.entrySet()){
List<String> row=orderMap.getValue();
Collections.sort(row,ascendingStringComparator);
if(row.size()>1){// single word
for(String word:row){
System.out.print(word);
System.out.print(" ");
}
System.out.println("");
}
}
}
}

- Diamond March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

assign the prime number to each letter and calculate the multiplication of each word. If multipication is same for two numbers then it means it has the same string. If a word has multiple same letters then don't multiply it again with the same prime number.

- mittalrishabh March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class UniqueCharSet {

public static void main(String[] args) {
Map<Set<Character>, Set<String>> uniqueCharacterMap = new HashMap<>();
for (String arg : args) {
Set<Character> uniqueCharacterSet = new HashSet<>();
for (char c : arg.toLowerCase().toCharArray()) {
uniqueCharacterSet.add(c);
}
if (uniqueCharacterMap.containsKey(uniqueCharacterSet)) {
Set<String> wordSet = uniqueCharacterMap.get(uniqueCharacterSet);
wordSet.add(arg);
}else{
Set<String> wordSet = new HashSet<>();
wordSet.add(arg);
uniqueCharacterMap.put(uniqueCharacterSet, wordSet);
}
}
for(Map.Entry<Set<Character>, Set<String>> entry : uniqueCharacterMap.entrySet()){
System.out.println(entry.getValue());
}
}
}

- OUB March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class UniqueCharSet {

	public static void main(String[] args) {
		Map<Set<Character>, Set<String>> uniqueCharacterMap = new HashMap<>();
		for (String arg : args) {
			Set<Character> uniqueCharacterSet = new HashSet<>();
			for (char c : arg.toLowerCase().toCharArray()) {
				uniqueCharacterSet.add(c);
			}
			if (uniqueCharacterMap.containsKey(uniqueCharacterSet)) {
				Set<String> wordSet = uniqueCharacterMap.get(uniqueCharacterSet);
				wordSet.add(arg);
			}else{
				Set<String> wordSet = new HashSet<>();
				wordSet.add(arg);
				uniqueCharacterMap.put(uniqueCharacterSet, wordSet);
			}
		}
		for(Map.Entry<Set<Character>, Set<String>> entry : uniqueCharacterMap.entrySet()){
			System.out.println(entry.getValue());
		}
	}
}

- OUB March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class UniqueCharSet {

	public static void main(String[] args) {
		Map<Set<Character>, Set<String>> uniqueCharacterMap = new HashMap<>();
		for (String arg : args) {
			Set<Character> uniqueCharacterSet = new HashSet<>();
			for (char c : arg.toLowerCase().toCharArray()) {
				uniqueCharacterSet.add(c);
			}
			if (uniqueCharacterMap.containsKey(uniqueCharacterSet)) {
				Set<String> wordSet = uniqueCharacterMap.get(uniqueCharacterSet);
				wordSet.add(arg);
			}else{
				Set<String> wordSet = new HashSet<>();
				wordSet.add(arg);
				uniqueCharacterMap.put(uniqueCharacterSet, wordSet);
			}
		}
		for(Map.Entry<Set<Character>, Set<String>> entry : uniqueCharacterMap.entrySet()){
			System.out.println(entry.getValue());
		}
	}

}

- OUB March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java. Basic idea is that we create a key from each string by using lower case non repeated sorted chars and store each string in a list of similar strings.

public static void main(String[] args) throws Exception {
        String str = "May student students dog studentssess god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice ";
        String[] words = str.split(" ");
        List<List<String>> repeated = getRepeatedStrings(words);

    }

    static List<List<String>> getRepeatedStrings(String[] words) {
        Map<String, List<String>> lookup = new HashMap<>();
        for(String current : words) {
            String key = getKey(current);
            List<String> matches = lookup.computeIfAbsent(key, o-> new ArrayList<String>());
            matches.add(current);
        }

        return lookup.values().stream().filter(list-> list.size() > 1).collect(Collectors.toList());
    }

    static int[] chars = new int[256];

    static String getKey(String s) {
        List<Character> keyChars = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = Character.toLowerCase(s.charAt(i));
            if(chars[(int)c] == 0) {
                keyChars.add(c);
                chars[(int)c]++;
            }
        }

        Collections.sort(keyChars);
        StringBuilder sb = new StringBuilder();
        keyChars.forEach(c-> {
            chars[(int)c]--;
            sb.append(c);
        });
        return sb.toString();
    }

- ak_domi March 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a number for each of the words.
let's say the given array is words[i]. Create a new array of same length as words, lets call it arr. Then for each word i "

for (int j=0; j<words[i].length; j++) 
{
	int x = words[i][j]-'a';
	arr[i] |= 1<<x;
}

Output the repetitions of the numbers.

- yo March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printUniqueCharMatches(List<string> list)
        {
            if (list.Count <= 1)
                return;
            Hashtable refTable = new Hashtable();


            foreach (string str in list)
            {
                string temp = SortAndRemoveDups(str.ToLower());
                if (!(refTable.Contains(temp)))
                {
                    refTable.Add(temp, str);
                }
                else
                {
                    refTable[temp] += " " + str;
                }

            }
            foreach (DictionaryEntry entry in refTable)
            {
                Console.WriteLine(entry.Value);
            }
        }

        public static string SortAndRemoveDups(string str)
        {
            if (str.Length <= 1)
                return str;

                char[] tempCharArray = str.ToArray();
                Array.Sort(tempCharArray);
                
            StringBuilder sb = new StringBuilder();
            Hashtable refTable = new Hashtable();

            foreach (char ch in tempCharArray)
            {
                if (refTable.Contains(ch))
                {
                    continue;
                }
                else
                {
                    refTable.Add(ch, 1);
                    sb.Append(ch);
                }
            }
            return sb.ToString();

            }

- tamvette March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string FindUniqueWords(string inputStr)
{
string[] strList = inputStr.Split(' ');
StringBuilder sb = new StringBuilder();

Dictionary<string, List<string>> strDic = new Dictionary<string, List<string>>();

foreach(var s in strList)
{
var strwithoutdup = RemoveDuplicate(s).ToLower();
if(strDic.ContainsKey(SortString(strwithoutdup)))
{
strDic[SortString(strwithoutdup)].Add(s);
}
else
{
strDic.Add(SortString(strwithoutdup), new List<string> { s });
}
}

foreach (var dic in strDic)
{
if(dic.Value.Count>1)
{
foreach(var s in dic.Value)
{
sb.Append(s);
sb.Append(" ");
sb.Append("\n");
}
}

}

return sb.ToString();

}

private static string SortString(string str)
{
char[] strArr = str.ToCharArray();

Array.Sort(strArr);
return new string(strArr);

}

private static string RemoveDuplicate(string str)
{
char[] strArr = str.ToCharArray();
HashSet<char> charStr = new HashSet<char>();

foreach(var s in str)
{
if (!charStr.Contains(s))
charStr.Add(s);
}

return new string(charStr.ToArray());
}

- suvirg March 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Solution :

public static List<List<String>> groupAnagrams(String[] words) {
    List<List<String>> result = new ArrayList<List<String>>();

    Pair[] pairs = new Pair[words.length];
    for (int i=0; i<words.length; i++) {
      pairs[i] = new Pair(words[i]);
    }

    Arrays.sort(pairs);

    List<String> cur = new ArrayList<String>();
    cur.add(pairs[0].a);
    result.add(cur);
    for (int i=1; i<pairs.length; i++) {
      if (pairs[i].b.equals(pairs[i-1].b)) {
        cur.add(pairs[i].a);
      } else {
        cur = new ArrayList<String>();
        cur.add(pairs[i].a);
        result.add(cur);
      }
    }

    return result;
  }

  public static class Pair implements Comparable<Pair>{
    String a;
    String b;

    public Pair(String str) {
      a = str;
      StringBuffer sb = new StringBuffer();
      char[] strArr = str.toLowerCase().toCharArray();
      Arrays.sort(strArr);
      str = new String(strArr);
      sb.append(str.charAt(0));
      for (int i=1; i<str.length(); i++) {
        char cur = str.charAt(i);
        if (cur == str.charAt(i-1)) {
          continue;
        } else {
          sb.append(cur);
        }
      }
      b = sb.toString();
    }

    public int compareTo(Pair p) {
      return this.b.compareTo(p.b);
    }
  }

- challapallirahul March 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){
    Map<Double, List<String>> map = group(Arrays.asList(new String[]{"May", "student", "students", "dog", "studentssess", "god", "Cat", "act", 
                                                                     "tab", "bat", "flow", "wolf", "lambs", "Amy", "Yam", "balms", "looped", "poodle", "john", "alice" }));
    for(List<String> strs: map.values()){
    	System.out.println(strs);
    }
    
  }
  
  
  public static Map<Double, List<String>> group(List<String> words){
  	Map<Double, List<String>> map = new HashMap<Double, List<String>>();
    
    for(String str: words){
    	double hash = hash(str);
      	List<String> list = map.get(hash);
      	if(list == null)
          list = new ArrayList<String>();
      	list.add(str);
      	map.put(hash, list);
    }
    return map;
  }
  
  public static double hash(String str){
  	String s = str.toLowerCase();
    char[] carr = s.toCharArray();
    int n = carr.length;
    double hash = 0.0;
    double K = 29.51;
    
    int[] arr = new int[26];
    for(int i = 0; i < n; i++){
      if(arr[carr[i]-'a'] == 0){
      	hash += K*carr[i];
        arr[carr[i]-'a'] = 1;
      }	
    }
    return hash;
  }

- sudip.innovates October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private List<Set<String>> uniqueCharSet(List<String> list) {
        HashMap<Set<Character>, Set<String>> map = new HashMap<>();

        for (String word : list) {
            Set<Character> set = new HashSet<>();
            for (char c : word.toCharArray()) {
                set.add(c);
            }

            if (map.get(set) != null) {
                Set<String> tmpset = map.get(set);
                tmpset.add(word);
                map.put(set, tmpset);
            } else {
                Set<String> tmpset = new HashSet<>();
                tmpset.add(word);
                map.put(set, tmpset);
            }
        }

        List<Set<String>> res = new ArrayList<>();
        Set<Set<Character>> keySet = map.keySet();
        for (Set<Character> k : keySet) {
            Set<String> s = map.get(k);
            res.add(map.get(k));
        }

        return res;
    }

- Hugh May 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

import org.apache.commons.lang.StringUtils;
public class UniqueCharSet {

public static void main(String[] args) {

// input string
String str = "May student students dog studentssess god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice";

// input string converted to lower case
str = str.toLowerCase();

// split the input string into string array
String[] s1 = StringUtils.split(str);

// sort the array of string words
String[] strArray = new String[s1.length];
for (int i = 0; i < s1.length; i++) {
strArray[i] = sort(s1[i]);
}

// store sorted array of strings with it;s word count
Map<String, Integer> hashMap = new HashMap<String, Integer>();
int tmp = 0;
String subStr = null;
boolean flag = false;
for (int x = 0; x < strArray.length; x++) {
if (subStr != null) {
if (strArray[x].contains(subStr)) {
flag = true;
}
}
if (!hashMap.containsKey(strArray[x]) || flag) {
subStr = strArray[x];
if (flag) {
hashMap.put(strArray[x], ++tmp);
flag = false;
} else {
tmp = 0;
hashMap.put(strArray[x], ++tmp);
}

} else {
hashMap.put(strArray[x], ++tmp);
}
}

// iterate through hash map and check is any word is having count greater than 1 print it;s unique charcter set from input
Iterator<Entry<String, Integer>> iter = hashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String, Integer> pair = iter.next();
String temp = pair.getKey();
int val = pair.getValue();
if (val > 1) {
for (int x = 0; x < s1.length; x++) {
if (sort(s1[x]).equals(temp)) {
System.out.print(s1[x]);
System.out.print("\t");
}
}
System.out.println();
}

}

}

/**
* sort the input string alphabetically
* @param input input string
* @return sorting string
*/
public static String sort(String input) {
String original = input;
int j = 0;
char temp = 0;
char[] chars = original.toCharArray();
for (int i = 0; i < chars.length; i++) {
for (j = 0; j < chars.length; j++) {
if (chars[j] > chars[i]) {
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
}
return String.valueOf(chars);
}
}

- Anonymous March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

import org.apache.commons.lang.StringUtils;

public class UniqueCharSet {

public static void main(String[] args) {

// input string
String str = "May student students dog studentssess god Cat act tab bat flow wolf lambs Amy Yam balms looped poodle john alice";

// input string converted to lower case
str = str.toLowerCase();

// split the input string into string array
String[] s1 = StringUtils.split(str);

// sort the array of string words
String[] strArray = new String[s1.length];
for (int i = 0; i < s1.length; i++) {
strArray[i] = sort(s1[i]);
}

// store sorted array of strings with it;s word count
Map<String, Integer> hashMap = new HashMap<String, Integer>();
int tmp = 0;
String subStr = null;
boolean flag = false;
for (int x = 0; x < strArray.length; x++) {
if (subStr != null) {
if (strArray[x].contains(subStr)) {
flag = true;
}
}
if (!hashMap.containsKey(strArray[x]) || flag) {
subStr = strArray[x];
if (flag) {
hashMap.put(strArray[x], ++tmp);
flag = false;
} else {
tmp = 0;
hashMap.put(strArray[x], ++tmp);
}

} else {
hashMap.put(strArray[x], ++tmp);
}
}

// iterate through hash map and check is any word is having count greater than 1 print it;s unique charcter set from input
Iterator<Entry<String, Integer>> iter = hashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<String, Integer> pair = iter.next();
String temp = pair.getKey();
int val = pair.getValue();
if (val > 1) {
for (int x = 0; x < s1.length; x++) {
if (sort(s1[x]).equals(temp)) {
System.out.print(s1[x]);
System.out.print("\t");
}
}
System.out.println();
}

}

}

/**
* sort the input string alphabetically
* @param input input string
* @return sorting string
*/
public static String sort(String input) {
String original = input;
int j = 0;
char temp = 0;
char[] chars = original.toCharArray();
for (int i = 0; i < chars.length; i++) {
for (j = 0; j < chars.length; j++) {
if (chars[j] > chars[i]) {
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
}
return String.valueOf(chars);
}
}

- lparka123 March 15, 2017 | 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