Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
1. Create a HashMap<Integer, List<String>> that will hold every String from your array of strings using as Key the sum of each char Integer value.
2. Iterate over your list and insert each string using as key a transformation function that will calculate the sum of every char on that string, thus strings with same chars will have exact same sum. Append the Strings with same sum into the List of Strings for that particular sum.
3. for your String as input, just get it's sum value using the same transformation function, once you have the sum use it as key to print the resulting List<String> of the HashMap, that will print all Strings with same chars.
- O(n * n) to build list, O(1) to print String list
- O(n) space
Almost.
Let's define ascii values:
A= 65
B = 66
C = 67
D = 68
E = 69
... etc.
If we have two strings "BE" and "DC", they both sum to the same value, but they have different characters.
I think instead of transforming based on the sum of characters, when you iterate over the list, the hash code should be the hashcode produced when the particular string is lexicographically ordered.
so if you have the following strings:
"BAC", "CAB"
we would first find the lexicographically sorted version of the string , (for both this is "ABC") and in the hash location for "ABC", we would add both of them
def anagramQuestion(list1, input):
dict1 = {}
for x in range(0,len(list1)):
key = ''.join(sorted(list1[x]))
if key in dict1:
dict1[key].append(list1[x])
else:
dict1[key] = [list1[x]]
result = []
for x in dict1:
inputsorted = ''.join(sorted(input))
if x == inputsorted:
dict1[x].remove(input)
result.append(dict1[x])
return result
package com.careercup;
public class FuzzyStringSearch
{
public static void main(String[] args)
{
String input[] = new String[]{"cat","lion","act","dog"};
String toSearch = "tac";
searchWord(toSearch,input);
}
private static void searchWord(String toSearch, String[] input)
{
for (int i = 0; i < input.length; i++)
{
if (input[i].length() == toSearch.length())
{
if(fuzzySearch(input[i],toSearch))
{
System.out.println(input[i]);
}
}
}
}
private static boolean fuzzySearch(String string, String toSearch)
{
boolean result = false;
char text[] = toSearch.toCharArray();
for (int i = 0; i < text.length; i++)
{
for (int j = 0; j < string.length(); j++)
{
if(text[i] == string.charAt(j))
result = true;
}
}
return result;
}
}
import java.util.*;
import java.util.regex.Pattern;
public class AllMatchedletters {
ArrayList<String> al=new ArrayList<String>();
ArrayList <String>matches=new ArrayList<String>();
public void insertChar()
{
al.add("cat");
al.add("tac");
al.add("tas");
al.add("act");
al.add("bct");
al.add("bat");
}
public void matchAll(String str)
{
Pattern p=Pattern.compile(str);
for(String s:al)
{
if(p.matcher(s).matches())
{
matches.add(s);
}
}
System.out.println(matches);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
AllMatchedletters match=new AllMatchedletters();
match.insertChar();
String str="[cat]+";
match.matchAll(str);
}
}
This problem can be solved by sorting the words and then compairing it with given word. This is basically a problem of finding anagrams from list of words.
<pre>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class AnagramFinder {
public static void main(String[] args) {
List<String> listOfWords = new ArrayList<String>();
listOfWords.add("utid");
listOfWords.add("ttid");
listOfWords.add("diut");
listOfWords.add("utdi");
findAnagramInList(listOfWords,"tdiu");
}
private static void findAnagramInList(List<String> listOfWords,
String string) {
char[] stringArray= string.toCharArray();
Arrays.sort(stringArray);
for(String s :listOfWords){
char [] arr = s.toCharArray();
Arrays.sort(arr);
if(String.valueOf(arr).equals(String.valueOf(stringArray))){
System.out.println("Angram found :" +s);
}
}
}
}
</pre>
Its basically a anagram finding problem. The given solution will have time complexity as O(n) sa you are going through the whole list, sorting the words would be O(nlogn) and compairing is a constant work we are doing. So final complexity would be O(n)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class AnagramFinder {
public static void main(String[] args) {
List<String> listOfWords = new ArrayList<String>();
listOfWords.add("utid");
listOfWords.add("ttid");
listOfWords.add("diut");
listOfWords.add("utdi");
findAnagramInList(listOfWords,"tdiu");
}
private static void findAnagramInList(List<String> listOfWords,
String string) {
char[] stringArray= string.toCharArray();
Arrays.sort(stringArray);
for(String s :listOfWords){
char [] arr = s.toCharArray();
Arrays.sort(arr);
if(String.valueOf(arr).equals(String.valueOf(stringArray))){
System.out.println("Angram found :" +s);
}
}
}
}
A different approach
- each string could be identified by an array of integers of length 26 (size depended on the set of characters, here we considered only a-z). The integer array is populated by setting the number of occurrence of characters in the input string. For example "cat" will be represented as {1,1,1,0,0,0,0,....0}. In this way we form a unique integer array for strings with same number of characters.
- create a map of integer array versus string list
package com.cnu.ds.programs;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class SetOfAnagrams {
public List<String> anagrams(String str,List<String> list) {
List<String> anagrams = new LinkedList<>();
for (String string : list) {
if (anagrams(string, str)) {
anagrams.add(string);
}
}
return anagrams;
}
public boolean anagrams(String s1, String s2) {
if (s1 != null && s2 != null) {
if (s1.length() == s2.length()) {
int[] noOfAlphabetsInS1 = new int[26];
for (int i = 0; i < s1.length(); i++) {
noOfAlphabetsInS1[s1.charAt(i) - 97]++;
noOfAlphabetsInS1[s2.charAt(i) - 97]--;
}
for (int i = 0; i < noOfAlphabetsInS1.length; i++) {
if (noOfAlphabetsInS1[i] != 0) {
return false;
}
}
return true;
}
}
return false;
}
public static void main(String[] args) {
String[] strings = { "abc", "cab", "dac", "bed", "few", "deb", "acd" };
System.out.println(String.format("List of Anagrams of %s : %s","cad",anagrams.anagrams("cad", Arrays.asList(strings))));
}
}
import java.util.Arrays;
public class FindNumOfWordsFromList {
static String[] array = {"act","tca","asd","cat"};
public static void main(String[] args){
searchwords("act");
}
private static void searchwords(String string) {
for(String word:array){
if(!word.equals(string) && word.length()==string.length()){
char[] stringCh =string.toCharArray();
char[] wordCh =word.toCharArray();
Arrays.sort(stringCh);
Arrays.sort(wordCh);
if(Arrays.equals(stringCh, wordCh)){
System.out.println(word);
}
}
}
}
}
import java.util.Arrays;
public class FindNumOfWordsFromList {
static String[] array = {"act","tca","asd","cat"};
public static void main(String[] args){
searchwords("act");
}
private static void searchwords(String string) {
for(String word:array){
if(!word.equals(string) && word.length()==string.length()){
char[] stringCh =string.toCharArray();
char[] wordCh =word.toCharArray();
Arrays.sort(stringCh);
Arrays.sort(wordCh);
if(Arrays.equals(stringCh, wordCh)){
System.out.println(word);
}
}
}
}
}
public static void main(String[] args) {
String[] arr={"abc","cab","fdg","sbc","bac","bsc"};
String inputKey="cba";
System.out.println(getAllPaatern(arr,inputKey));
}
static List<String> getAllPaatern(String[] inputArray, String searchKey){
List<String> wordList= new ArrayList<String>();
for(int i=0;i <inputArray.length;i++){
if(getSortedString(inputArray[i].toLowerCase()).equals(getSortedString(searchKey.toLowerCase()))){
wordList.add(inputArray[i]);
}
}
return wordList;
}
static String getSortedString(String str){
char [] c = str.toCharArray();
Arrays.sort(c);
return new String(c);
}
1. Iterate over the 1000 words.
Create a multivalue hashmap, put the sorted form of that word as key and actual order as value. So all 'act', 'tca', 'cat' will come under key 'act'.
2. Sort the string to compare i.e. sort 'tca' -> 'act'.
3. Use 'act' as key to find all the values from hashmap.
code :
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
public class Anagrams {
public static void main(String[] args) {
String[] source = {"cat","act","tca", "good", "dogo", "waste", "read", "dear"};
printSameKind(source, "good");
printSameKind(source, "read");
printSameKind(source, "act");
}
public static void printSameKind(String[] source, String str){
Hashtable<String, List<String>> ht = new Hashtable<String, List<String>>();
MergeSort sorter = new MergeSort();
List<String> values;
char[] chr;
for(int i=0;i<source.length;i++){
chr = source[i].toCharArray();
sorter.sort(chr);
String sortedString = String.valueOf(chr);
if(ht.get(sortedString)==null){
values = new ArrayList<String>();
}else{
values = ht.get(sortedString);
}
values.add(source[i]);
ht.put(sortedString, values);
}
chr = str.toCharArray();
sorter.sort(chr);
str = String.valueOf(chr);
List<String> result = ht.get(str);
System.out.println(result);
}
}
(I have used mergesort to sort the string)
public class MergeSort {
private char[] c;
private char[] helper;
private int number;
public void sort(char[] chr){
this.c = chr;
this.number = chr.length;
this.helper = new char[number];
mergesort(0,number-1);
}
private void mergesort(int first, int last){
if(first<last){
int mid = first + (last-first)/2;
mergesort(first,mid);
mergesort(mid+1,last);
merge(first,mid,last);
}
}
public void merge(int start,int mid, int end){
//Copy both parts to helper array
for(int i=start;i<=end;i++){
helper[i] = c[i];
}
int i = start;
int j = mid+1;
int k = start;
while(i<=mid && j<=end){
if(helper[i]<=helper[j]){
c[k] = helper[i];
i++;
}else{
c[k] = helper[j];
j++;
}
k++;
}
while (i <= mid) {
c[k] = helper[i];
k++;
i++;
}
while (j <= end) {
c[k] = helper[j];
k++;
j++;
}
}
}
1. convert strings to character arrays using toCharArray()
2. sort the arrays using Arrays.sort()
3. compare the arrays Arrays.equals()
package goldmansachs;
import java.util.Arrays;
public class anagram {
public static void main(String args[]){
String arr[] ={"cat","tac","act","xyz"};
String s = "tac";
for(int i =0;i<arr.length;i++){
if(isAnagram(s,arr[i])){
System.out.println(arr[i]);
}
}
}
public static boolean isAnagram(String x,String y){
char a[] = x.toCharArray();
char b[] = y.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
if(Arrays.equals(a,b)){
return true;
}
return false;
}
}
I have tested Its working.
public class MiscDemo {
public static void main(String[] args) {
String []input = {"cat","good","tac","act","odog"};
MiscDemo misc = new MiscDemo();
misc.segragateAnagram(input);
System.out.println();
}
public void segragateAnagram(String input[]){
Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
Set<String> keys = map.keySet();
String word;
for(int i=0; i<input.length;i++){
if(this.matchingAnagramKey(keys, input[i])!=null){
word = this.matchingAnagramKey(keys, input[i]);
map.get(word).add(input[i]);
}else{
map.put(input[i], new ArrayList<String>());
}
}
System.out.println(map.get("cat").size());
}
public String matchingAnagramKey(Set<String> keys, String b){
for(String word:keys){
if(isAnagram(word, b)){
return word;
}else{
}
}
return null;
}
public boolean isAnagram(String a, String b){
// Their length shoud be same \
// Their both String contain same character and same number of character but there order might be diifer.
int m = a.length();
int n = a.length();
if(m!=n){
return false;
}
int []count1 = new int[26];
int []count2 = new int[26];
// using single count array
for(int i=0;i<n;i++){
count1[a.charAt(i)-97]+=1;
}
for(int i=0;i<n;i++){
count1[b.charAt(i)-97]-=1;
}
for(int i=0;i<26;i++){
if(count1[i]!=0){
return false;
}
}
return true;
}
}
public class MiscDemo {
public static void main(String[] args) {
String []input = {"cat","good","tac","act","odog"};
MiscDemo misc = new MiscDemo();
misc.segragateAnagram(input);
System.out.println();
}
public void segragateAnagram(String input[]){
Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
Set<String> keys = map.keySet();
String word;
for(int i=0; i<input.length;i++){
if(this.matchingAnagramKey(keys, input[i])!=null){
word = this.matchingAnagramKey(keys, input[i]);
map.get(word).add(input[i]);
}else{
map.put(input[i], new ArrayList<String>());
}
}
System.out.println(map.get("cat").size());
}
public String matchingAnagramKey(Set<String> keys, String b){
for(String word:keys){
if(isAnagram(word, b)){
return word;
}else{
}
}
return null;
}
public boolean isAnagram(String a, String b){
// Their length shoud be same \
// Their both String contain same character and same number of character but there order might be diifer.
int m = a.length();
int n = a.length();
if(m!=n){
return false;
}
int []count1 = new int[26];
int []count2 = new int[26];
// using single count array
for(int i=0;i<n;i++){
count1[a.charAt(i)-97]+=1;
}
for(int i=0;i<n;i++){
count1[b.charAt(i)-97]-=1;
}
for(int i=0;i<26;i++){
if(count1[i]!=0){
return false;
}
}
return true;
}
}
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<map>
#include<string.h>
typedef unsigned int UINT;
UINT IsProperWord(const char* str);
int main(int argc, char* argv[]){
if(argc < 3){
printf("\nUsage ./a.out <number of words> <word1> <word2> <word3> ... \n");
printf("\n Example : ./a.out 5 cat act hat god dog\n");
return -1;
}
int numOfWords = atoi(argv[1]);
if(numOfWords != (argc -2)){
printf("\n number of words and words count are not matching !!!\n");
return -1;
}
numOfWords = argc - 2;
std::map<UINT, std::vector<int> > valueToWordIndexMap;
std::map<UINT, std::vector<int> >::iterator mapIter;
std::vector<int>:: iterator vecIter;
int i = 2;
while(i < argc){
UINT key = IsProperWord(argv[i]);
if(key){
//printf("\nKey:%u Word:%s",key,argv[i]);
mapIter = valueToWordIndexMap.find(key);
if(mapIter != valueToWordIndexMap.end()){
mapIter->second.push_back(i);
}else{
std::vector<int> indexVec;
indexVec.push_back(i);
valueToWordIndexMap.insert(std::pair<UINT,std::vector<int> >(key,indexVec));
}
}else{
return -1;
}
i++;
}
for(mapIter = valueToWordIndexMap.begin(); mapIter != valueToWordIndexMap.end(); ++mapIter){
for(vecIter = (mapIter->second).begin();vecIter != (mapIter->second).end(); ++vecIter){
printf("%s ",argv[*vecIter]);
}
printf("\n");
}
return 0;
}
UINT IsProperWord(const char* str){
int size = strlen(str);
bool alphabets[26] = { };
UINT key = 0;
//Convert to lower case
//97 - a 122 - z
int i = 0;
while(i < size){
int alphaIndex = 0;
if( *(str +i) >= 'a' && *(str+i) <= 'z'){
alphaIndex = *(str+i) - 97;
// do nothing
}else if(*(str+i) >= 'A' && *(str+i) <= 'Z'){
alphaIndex = *(str+i) - 65 ;
}else{
return 0;
}
// check the duplicate of characters
if(alphabets[alphaIndex]){
printf("\nDuplicate characters in word : %s\n",str);
return 0;
}else{
alphabets[alphaIndex] = true;
}
i++;
}
// convert the bool to decimal value
i = 0;
while(i < 26){
if(alphabets[i]){
key += (2 ^ i);
}
i++;
}
return key;
}
package com.sumit;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution15 {
public static void main(String[] args) {
String[] dict = { "abc", "cab", "dac", "bed", "few", "deb", "acd" };
String input = "cad";
Map<String, List<String>> dictMap = new HashMap<>();
for (int i = 0; i < dict.length; i++) {
String[] carr = dict[i].split("");
Arrays.sort(carr);
String key = Arrays.toString(carr);
if (dictMap.containsKey(key)) {
List<String> lst = dictMap.get(key);
lst.add(dict[i]);
dictMap.put(key, lst);
} else {
List<String> lst = new ArrayList<>();
lst.add(dict[i]);
dictMap.put(key, lst);
}
}
//System.out.println(dictMap);
String[] carr = input.split("");
Arrays.sort(carr);
String key = Arrays.toString(carr);
System.out.println(dictMap.get(key));
}
}
- Vir Pratap Uttam May 01, 2015