Google Interview Question
Country: United States
Interview Type: Phone Interview
// 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]
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("");
}
}
}
}
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("");
}
}
}
}
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());
}
}
}
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());
}
}
}
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());
}
}
}
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();
}
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();
}
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());
}
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);
}
}
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;
}
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;
}
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);
}
}
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);
}
}
- Chris March 15, 2017