Goldman Sachs新鲜电面

安吉拉

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

PattyZhou

Is it your homework?????