Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
package com.eb.corealgo;
import javax.print.attribute.standard.MediaSize.Other;
public class StringAnagram {
public String anagramGroup(String []input){
String anagramGroup="";
String notAnagram="";
anagramGroup+="{";
for(int i=0;i<input.length;i++){
for(int j=i+1;j<input.length;j++){
//check for anagram if yes return group
boolean isAnagram=isAnagramGruop(input[i],input[j]);
if(isAnagram){
anagramGroup+="("+input[i]+","+input[j]+")";
}
}
}
return anagramGroup+"}";
}
public boolean isAnagramGruop(String input1,String input2){
//from second to one comparing
int j=input2.length()-1;
for(int i=0;i<input1.length();i++){
if(input1.charAt(i)==input2.charAt(j)){
j--;
continue;
}
else
{
return false;
}
}
return true;
}
//app test
public static void main(String args[]){
StringAnagram an=new StringAnagram();
String input[]=new String[]{"star","dog","car","rats","god"};
System.out.println(an.anagramGroup(input));
}
}
package com.eb.corealgo;
import javax.print.attribute.standard.MediaSize.Other;
public class StringAnagram {
public String anagramGroup(String []input){
String anagramGroup="";
String notAnagram="";
anagramGroup+="{";
for(int i=0;i<input.length;i++){
for(int j=i+1;j<input.length;j++){
//check for anagram if yes return group
boolean isAnagram=isAnagramGruop(input[i],input[j]);
if(isAnagram){
anagramGroup+="("+input[i]+","+input[j]+")";
}
}
}
return anagramGroup+"}";
}
public boolean isAnagramGruop(String input1,String input2){
//from second to one comparing
int j=input2.length()-1;
for(int i=0;i<input1.length();i++){
if(input1.charAt(i)==input2.charAt(j)){
j--;
continue;
}
else
{
return false;
}
}
return true;
}
//app test
public static void main(String args[]){
StringAnagram an=new StringAnagram();
String input[]=new String[]{"star","dog","car","rats","god"};
System.out.println(an.anagramGroup(input));
}
}
public class StringAnagram {
public String anagramGroup(String []input){
String anagramGroup="";
anagramGroup+="{";
for(int i=0;i<input.length;i++){
for(int j=i+1;j<input.length;j++){
//check for anagram if yes return group
boolean isAnagram=isAnagramGruop(input[i],input[j]);
if(isAnagram){
anagramGroup+="("+input[i]+","+input[j]+")";
}
}
}
return anagramGroup+"}";
}
public boolean isAnagramGruop(String input1,String input2){
//from second to one comparing
int j=input2.length()-1;
for(int i=0;i<input1.length();i++){
if(input1.charAt(i)==input2.charAt(j)){
j--;
continue;
}
else
{
return false;
}
}
return true;
}
package com.eb.corealgo;
public class StringAnagram {
public String anagramGroup(String []input){
String anagramGroup="";
anagramGroup+="{";
for(int i=0;i<input.length;i++){
for(int j=i+1;j<input.length;j++){
//check for anagram if yes return group
boolean isAnagram=isAnagramGruop(input[i],input[j]);
if(isAnagram){
anagramGroup+="("+input[i]+","+input[j]+")";
}
}
}
return anagramGroup+"}";
}
public boolean isAnagramGruop(String input1,String input2){
//from second to one comparing
int j=input2.length()-1;
for(int i=0;i<input1.length();i++){
if(input1.charAt(i)==input2.charAt(j)){
j--;
continue;
}
else
{
return false;
}
}
return true;
}
//app test
public static void main(String args[]){
StringAnagram an=new StringAnagram();
String input[]=new String[]{"star","dog","car","rats","god"};
System.out.println(an.anagramGroup(input));
}
}
import java.util.Arrays;
import java.util.HashSet;
public class AnagramGroups {
static HashSet<String> hset = new HashSet<String>();
public static void main(String[] args) {
String str[]={"yxz","car", "god", "arc", "ogd", "xyz","god"};
int l =str.length;
int i;
System.out.print("{");
for(i=0;i<l;i++)
{
if(hset.contains(str[i]))
i++;
else
{
System.out.print("("+str[i]);
CheckAnagram(str[i],str,i+1);
}
System.out.print(")");
}
System.out.print("}");
}
private static void CheckAnagram(String word, String[] str, int i) {
char ch1[] = word.toCharArray();
Arrays.sort(ch1);
int j,l =str.length;
for(j=i;j<l;j++)
{
char ch2[] = str[j].toCharArray();
Arrays.sort(ch2);
if(Arrays.equals(ch1, ch2))
{
hset.add(str[j]);
System.out.print(","+str[j]);
}
}
}
}
void FindAnagrams(vector<string> const& s, vector<vector<string>> &result)
{
map<string, vector<string>> anagrams;
for (vector<string>::const_iterator it = s.begin(); it != s.end(); it++) {
string s1(*it);
sort(s1.begin(), s1.end());
anagrams[s1].push_back(*it);
}
for (map<string, vector<string>>::const_iterator it = anagrams.begin(); it != anagrams.end(); it++)
result.push_back(it->second);
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
packageamazon;
publicclassAnargamProgram{
publicStringanagramGroup(String[]input){
StringanagramGroup="";
anagramGroup+="{";
for(inti=0;i<input.length;i++){
for(intj=i+1;j<input.length;j++){
booleanisAnagram=isAnagramGruop(input[i],input[j]);
if(isAnagram){
anagramGroup+="("+input[i]+","+input[j]+")";
}
}
}
returnanagramGroup+"}";
}
publicbooleanisAnagramGruop(Stringinput1,Stringinput2){
booleangotoNextWord=false;
if(input1.length()!=input2.length()){
gotoNextWord=true;
}
intflag=0;
for(inti=0;i<input1.length()&&!gotoNextWord;i++){
for(intj=0;j<input2.length();j++){
if(input1.charAt(i)==input2.charAt(j)){
flag+=1;
}
if(j==(input2.length()-1)){
if(flag==0){
gotoNextWord=true;
break;
}elseif(flag==(input1.length()-input1.replaceAll(String.valueOf(input1.charAt(i)),"")
.length())){
gotoNextWord=false;
}else{
gotoNextWord=true;
break;
}
}
}
flag=0;
}
return!gotoNextWord;
}
publicstaticvoidmain(Stringargs[]){
AnargamPrograman=newAnargamProgram();
Stringinput[]=newString[]{"star","dog","car","rats","god","tars"};
System.out.println(an.anagramGroup(input));
}
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
package amazon;
public class AnargamProgram {
public String anagramGroup(String[] input) {
String anagramGroup = "";
anagramGroup += "{";
for (int i = 0; i < input.length; i++) {
for (int j = i + 1; j < input.length; j++) {
boolean isAnagram = isAnagramGruop(input[i], input[j]);
if (isAnagram) {
anagramGroup += "(" + input[i] + "," + input[j] + ")";
}
}
}
return anagramGroup + "}";
}
public boolean isAnagramGruop(String input1, String input2) {
boolean gotoNextWord = false;
if (input1.length() != input2.length()) {
gotoNextWord = true;
}
int flag = 0;
for (int i = 0; i < input1.length() && !gotoNextWord; i++) {
for (int j = 0; j < input2.length(); j++) {
if (input1.charAt(i) == input2.charAt(j)) {
flag += 1;
}
if (j == (input2.length() - 1)) {
if (flag == 0) {
gotoNextWord = true;
break;
} else if (flag == (input1.length() - input1.replaceAll(String.valueOf(input1.charAt(i)), "")
.length())) {
gotoNextWord = false;
} else {
gotoNextWord = true;
break;
}
}
}
flag = 0;
}
return !gotoNextWord;
}
public static void main(String args[]) {
AnargamProgram an = new AnargamProgram();
String input[] = new String[] { "star", "dog", "car", "rats", "god", "tars" };
System.out.println(an.anagramGroup(input));
}
}
I would have a Hash string as the key and the value. Iterate over the words and check if the inverse of the word exists in the hash, if so, group it, else just add that word to the hash key with an empty value string.
@Test
public void testGroupAnagrams() {
String entries = "star,dog,car,rats,rac";
Map<String, String> response = groupAnagrams(entries.split(","));
for (Iterator<String> iterator = response.keySet().iterator(); iterator.hasNext();) {
String word = iterator.next();
if (response.get(word) != null) {
System.out.print("(" + word + "," + response.get(word) + "),");
} else {
System.out.print(word);
}
}
}
private Map<String, String> groupAnagrams(String[] words) {
Map<String, String> resp = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String word = words[i];
String inverseWord = invertString(word);
if (resp.keySet().contains(inverseWord)) {
resp.put(inverseWord, word);
} else if (!resp.keySet().contains(word)) {
resp.put(word, null);
}
}
return resp;
}
private String invertString(String word) {
StringBuilder inverted = new StringBuilder();
for (int i = word.length() - 1; i >= 0; i--) {
inverted.append(word.charAt(i));
}
return inverted.toString();
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
public class GroupAllAnagrams {
public static void main(String args[]) throws IOException{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
while(true){
String s= br.readLine();
String[] literls=s.split("\\s+");
/*for(int i=0;i<literls.length;i++){
System.out.println(literls[i]);
}*/
LinkedHashMap<String,ArrayList<String>> mMap=new LinkedHashMap<>();
for(int i=0;i<literls.length;i++){
char[] chrs=literls[i].toCharArray();
Arrays.sort(chrs);
mMap.putIfAbsent(String.valueOf(chrs),new ArrayList<String>());
mMap.get(String.valueOf(chrs)).add(literls[i]);
}
LinkedHashSet finalSet=new LinkedHashSet<String>();
for(ArrayList<String> l:mMap.values()){
finalSet.addAll(l);
}
System.out.println(finalSet);
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
public class GroupAllAnagrams {
public static void main(String args[]) throws IOException{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
while(true){
String s= br.readLine();
String[] literls=s.split("\\s+");
/*for(int i=0;i<literls.length;i++){
System.out.println(literls[i]);
}*/
LinkedHashMap<String,ArrayList<String>> mMap=new LinkedHashMap<>();
for(int i=0;i<literls.length;i++){
char[] chrs=literls[i].toCharArray();
Arrays.sort(chrs);
mMap.putIfAbsent(String.valueOf(chrs),new ArrayList<String>());
mMap.get(String.valueOf(chrs)).add(literls[i]);
}
LinkedHashSet finalSet=new LinkedHashSet<String>();
for(ArrayList<String> l:mMap.values()){
finalSet.addAll(l);
}
System.out.println(finalSet);
}
}
}
public void groupAnagrams(String[] stringList) {
int[] primeMapping = new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
Hashtable<Long, ArrayList<String>> table = new Hashtable<Long, ArrayList<String>> ();
for (int i=0; i<stringList.length; i++) {
String str = stringList[i];
String tmpstr = new String(str.toLowerCase());
long prod = 1;
for (int j=0; j<tmpstr.length(); j++) {
char c = tmpstr.charAt(j);
prod = prod * primeMapping[c-'a'];
}
if(table.containsKey(prod)) {
ArrayList<String> strlist = table.get(prod);
strlist.add(str);
} else {
ArrayList<String> strlist = new ArrayList<String>();
strlist.add(str);
table.put(prod,strlist);
}
}
Set<Long> keys = table.keySet();
for(Long key: keys){
ArrayList<String> strlist = table.get(key);
System.out.print("(");
for (int i=0;i<strlist.size(); i++) {
System.out.print(strlist.get(i) + " ");
}
System.out.println(")");
}
}
import java.util.List;
import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collection;
public class HelloWorld{
public static void main(String []args){
String input = "star,dog,car,rats,arc";
String arr[] = input.split(",");
List<String> list = Arrays.asList(arr);
HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();
for(String word : list) {
char arrCh[] = word.toCharArray();
Arrays.sort(arrCh);
String key = new String(arrCh);
ArrayList<String> anas;
if (!map.containsKey(key)) {
anas = new ArrayList<String>();
map.put(key,anas);
} else {
anas = map.get(key);
}
anas.add(word);
}
for (ArrayList<String> anas : (Collection<ArrayList<String>>)map.values()) {
String out = "(";
for (String word : anas) {
out += word;
out += ",";
}
out = out.substring(0,out.length()-1);
out += ")";
System.out.println(out);
}
}
}
#include<iostream>
#include<string.h>
using namespace std;
int n;
//for storing string sets where no is the count of the set&&count array for storing alphabetic count
struct store
{
int no;
string s[20];
int count[26];
};
//function for checking if its a anagram sequence of an existing set
int check(int alphacount[][26],struct store s1[],string s,int index)
{
int checkflag=-1;
for(int i=0;i<n;i++)
{
if(s1[i].no==0)
continue;
else
{
int testflag=0;
for(int k=0;k<26;k++)
{
if(alphacount[index][k]==s1[i].count[k])
continue;
else
testflag=1;
}
if(testflag==0)
{
checkflag=i;
break;
}
}
}
return checkflag;
}
//function for adding a string to a preexisting anagramic set
void addinset(struct store s1[],string s,int index)
{
s1[index].s[s1[index].no++]=s;
return;
}
//function to add the string to a new set and count of alphabets for the anagramic set is calculated
void add(struct store s1[],string s)
{
for(int i=0;i<n;i++)
{
if(s1[i].no==0)
{
for(int j=0;j<s.length();j++)
{
s1[i].count[(s[j]-'a')]++;
}
s1[i].s[s1[i].no++]=s;
return;
}
}
return;
}
int main()
{
int i,j,k;
cin>>n;
string s[n];
int alphacount[n][26]={0};
for(i=0;i<n;i++)
cin>>s[i];
store s1[n];
for(i=0;i<n;i++)
{
s1[i].no=0;
for(j=0;j<26;j++)
s1[i].count[j]=0;
}
for(i=0;i<n;i++)
{
for(k=0;k<s[i].length();k++)
{
alphacount[i][(s[i][k]-'a')]++;
}
}
int stringadded=0;
for(i=0;i<n;i++)
{
int index=check(alphacount,s1,s[i],i);
//cout<<index;
if(index>=0)
{
addinset(s1,s[i],index);
continue;
}
else
{
add(s1,s[i]);
}
}
for(i=0;i<n;i++)
{
if(s1[i].no==0)
break;
else
{
cout<<"(";
for(j=0;j<s1[i].no;j++)
{
cout<<s1[i].s[j]<<",";
}
cout<<"),";
}
}
return 0;
}
#include<iostream>
#include<string.h>
using namespace std;
int n;
//for storing string sets where no is the count of the set&&count array for storing alphabetic count
struct store
{
int no;
string s[20];
int count[26];
};
//function for checking if its a anagram sequence of an existing set
int check(int alphacount[][26],struct store s1[],string s,int index)
{
int checkflag=-1;
for(int i=0;i<n;i++)
{
if(s1[i].no==0)
continue;
else
{
int testflag=0;
for(int k=0;k<26;k++)
{
if(alphacount[index][k]==s1[i].count[k])
continue;
else
testflag=1;
}
if(testflag==0)
{
checkflag=i;
break;
}
}
}
return checkflag;
}
//function for adding a string to a preexisting anagramic set
void addinset(struct store s1[],string s,int index)
{
s1[index].s[s1[index].no++]=s;
return;
}
//function to add the string to a new set and count of alphabets for the anagramic set is calculated
void add(struct store s1[],string s)
{
for(int i=0;i<n;i++)
{
if(s1[i].no==0)
{
for(int j=0;j<s.length();j++)
{
s1[i].count[(s[j]-'a')]++;
}
s1[i].s[s1[i].no++]=s;
return;
}
}
return;
}
int main()
{
int i,j,k;
cin>>n;
string s[n];
int alphacount[n][26]={0};
for(i=0;i<n;i++)
cin>>s[i];
store s1[n];
for(i=0;i<n;i++)
{
s1[i].no=0;
for(j=0;j<26;j++)
s1[i].count[j]=0;
}
for(i=0;i<n;i++)
{
for(k=0;k<s[i].length();k++)
{
alphacount[i][(s[i][k]-'a')]++;
}
}
int stringadded=0;
for(i=0;i<n;i++)
{
int index=check(alphacount,s1,s[i],i);
//cout<<index;
if(index>=0)
{
addinset(s1,s[i],index);
continue;
}
else
{
add(s1,s[i]);
}
}
for(i=0;i<n;i++)
{
if(s1[i].no==0)
break;
else
{
cout<<"(";
for(j=0;j<s1[i].no;j++)
{
cout<<s1[i].s[j]<<",";
}
cout<<"),";
}
}
return 0;
}
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class AmazonSetAnagrams {
NodeAnagram[] buckets = new NodeAnagram[8];
public static void main(String[] args) {
Set<String> setAnagrams = new HashSet<String>();
setAnagrams.add("star");
setAnagrams.add("dogs");
setAnagrams.add("rats");
setAnagrams.add("car");
setAnagrams.add("rac");
setAnagrams.add("rtsa");
AmazonSetAnagrams amazonSetAnagrams = new AmazonSetAnagrams();
process (setAnagrams, amazonSetAnagrams);
Set<ArrayList<String>> setList = new HashSet<ArrayList<String>>();
for (int index =0;index<amazonSetAnagrams.buckets.length;index++){
ArrayList<String> listStrings = new ArrayList<String>();
NodeAnagram base= amazonSetAnagrams.buckets[index];
while (base != null){
listStrings.add(base.value);
base = base.next;
}
if (!listStrings.isEmpty()){
setList.add(listStrings);
}
}
for (ArrayList<String> arrayList:setList){
System.out.print("(");
for (int index =0;index<arrayList.size();index++){
String base= arrayList.get(index);
System.out.print(base +" ");
}
System.out.println(")");
}
}
private static class NodeAnagram {
String value;
NodeAnagram next = null;
public NodeAnagram (String value){
this.value = value;
}
public String toString(){
return value;
}
}
public void addNodeAnagram(String word){
int position = hash(word);
NodeAnagram node = buckets[position];
NodeAnagram newNode = new NodeAnagram(word);
if (node == null){
buckets[position] = newNode;
}else{
newNode.next = buckets[position];
buckets[position] = newNode;
}
}
private int hash(String word) {
int result = 0;
for (int index=0; index<word.length(); index++){
result = result+word.charAt(index);
}
NodeAnagram previoBucket = buckets[result % buckets.length];
if (previoBucket!=null){
while (previoBucket != null){
if (reviewAnagram(word, previoBucket.value))
previoBucket = previoBucket.next;
}
}
return result % buckets.length;
}
private boolean reviewAnagram(String newString, String strPrevioBucket){
char ch1[] = newString.toCharArray();
char ch2[] = strPrevioBucket.toCharArray();
Arrays.sort(ch1);
Arrays.sort(ch2);
if (ch1.length != ch2.length){
return false;
}
return Arrays.equals(ch1, ch2);
}
public static void process (Set<String> setAnagrams, AmazonSetAnagrams amazonSetAnagrams){
Iterator<String> iterator = setAnagrams.iterator();
while (iterator.hasNext()){
String word = iterator.next();
checkAnagram ( word, amazonSetAnagrams ) ;
}
}
private static void checkAnagram (String word, AmazonSetAnagrams amazonSetAnagrams ){
amazonSetAnagrams.addNodeAnagram( word);
}
}
package jumbled_number;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Anagram {
public static void main(String[] str) {
String[] str_inp = { "car", "krap","god", "rac", "dog", "another","park" };
Map<String, String> str_map = new HashMap<String, String>();
String ana_str = "";
for (int index = 0; index < str_inp.length; index++) {
ana_str = sort_array(str_inp[index]);
if (!str_map.containsKey(str_inp[index]))
{
if (str_map.containsKey(ana_str))
{
str_map.put(ana_str, str_inp[index]);
}
else
{
str_map.put(str_inp[index], null);
}
}
}
for (Object keys : str_map.keySet()) {
System.out.println("{" + keys + ","+ str_map.get(keys) + "}");
}
}
public static String sort_array(String str) {
char[] str_arr = str.toCharArray();
char[] str_arr_tmp;
int len = str_arr.length;
str_arr_tmp = new char[len];
int index = 0;
while (len > 0) {
str_arr_tmp[index++] = str_arr[--len];
}
String tmp = new String(str_arr_tmp);
return (tmp);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Anagram {
public static void main(String[] str) {
String[] str_inp = { "car", "krap","god", "rac", "dog", "another","park" };
Map<String, String> str_map = new HashMap<String, String>();
String ana_str = "";
for (int index = 0; index < str_inp.length; index++) {
ana_str = sort_array(str_inp[index]);
if (!str_map.containsKey(str_inp[index]))
{
if (str_map.containsKey(ana_str))
{
str_map.put(ana_str, str_inp[index]);
}
else
{
str_map.put(str_inp[index], null);
}
}
}
for (Object keys : str_map.keySet()) {
System.out.println("{" + keys + ","+ str_map.get(keys) + "}");
}
}
public static String sort_array(String str) {
char[] str_arr = str.toCharArray();
char[] str_arr_tmp;
int len = str_arr.length;
str_arr_tmp = new char[len];
int index = 0;
while (len > 0) {
str_arr_tmp[index++] = str_arr[--len];
}
String tmp = new String(str_arr_tmp);
return (tmp);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Anagram {
public static void main(String[] str) {
String[] str_inp = { "car", "krap","god", "rac", "dog", "another","park" };
Map<String, String> str_map = new HashMap<String, String>();
String ana_str = "";
for (int index = 0; index < str_inp.length; index++) {
ana_str = sort_array(str_inp[index]);
if (!str_map.containsKey(str_inp[index]))
{
if (str_map.containsKey(ana_str))
{
str_map.put(ana_str, str_inp[index]);
}
else
{
str_map.put(str_inp[index], null);
}
}
}
for (Object keys : str_map.keySet()) {
System.out.println("{" + keys + ","+ str_map.get(keys) + "}");
}
}
public static String sort_array(String str) {
char[] str_arr = str.toCharArray();
char[] str_arr_tmp;
int len = str_arr.length;
str_arr_tmp = new char[len];
int index = 0;
while (len > 0) {
str_arr_tmp[index++] = str_arr[--len];
}
String tmp = new String(str_arr_tmp);
return (tmp);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
public class GroupAllAnagrams {
public static void main(String args[]) throws IOException{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
while(true){
String s= br.readLine();
String[] literls=s.split("\\s+");
/*for(int i=0;i<literls.length;i++){
System.out.println(literls[i]);
}*/
LinkedHashMap<String,ArrayList<String>> mMap=new LinkedHashMap<>();
for(int i=0;i<literls.length;i++){
char[] chrs=literls[i].toCharArray();
Arrays.sort(chrs);
mMap.putIfAbsent(String.valueOf(chrs),new ArrayList<String>());
mMap.get(String.valueOf(chrs)).add(literls[i]);
}
LinkedHashSet finalSet=new LinkedHashSet<String>();
for(ArrayList<String> l:mMap.values()){
finalSet.addAll(l);
}
System.out.println(finalSet);
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
public class GroupAllAnagrams {
public static void main(String args[]) throws IOException{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
while(true){
String s= br.readLine();
String[] literls=s.split("\\s+");
/*for(int i=0;i<literls.length;i++){
System.out.println(literls[i]);
}*/
LinkedHashMap<String,ArrayList<String>> mMap=new LinkedHashMap<>();
for(int i=0;i<literls.length;i++){
char[] chrs=literls[i].toCharArray();
Arrays.sort(chrs);
mMap.putIfAbsent(String.valueOf(chrs),new ArrayList<String>());
mMap.get(String.valueOf(chrs)).add(literls[i]);
}
LinkedHashSet finalSet=new LinkedHashSet<String>();
for(ArrayList<String> l:mMap.values()){
finalSet.addAll(l);
}
System.out.println(finalSet);}}}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
public class GroupAllAnagrams {
public static void main(String args[]) throws IOException{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
while(true){
String s= br.readLine();
String[] literls=s.split("\\s+");
/*for(int i=0;i<literls.length;i++){
System.out.println(literls[i]);
}*/
LinkedHashMap<String,ArrayList<String>> mMap=new LinkedHashMap<>();
for(int i=0;i<literls.length;i++){
char[] chrs=literls[i].toCharArray();
Arrays.sort(chrs);
mMap.putIfAbsent(String.valueOf(chrs),new ArrayList<String>());
mMap.get(String.valueOf(chrs)).add(literls[i]);
}
LinkedHashSet finalSet=new LinkedHashSet<String>();
for(ArrayList<String> l:mMap.values()){
finalSet.addAll(l);
}
System.out.println(finalSet);
}
}
}
class AnagramComparator implements Comparator<String> {
@Override
public int compare(String one, String two) {
String s1 = sortChars(one);
String s2 = sortChars(two);
return s1.compareTo(s2);
}
String sortChars(String str) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
}
private void consecutiveAnagrams(String[] strings) {
Arrays.sort(strings, new AnagramComparator());
}
class AnagramComparator implements Comparator<String> {
@Override
public int compare(String one, String two) {
String s1 = sortChars(one);
String s2 = sortChars(two);
return s1.compareTo(s2);
}
String sortChars(String str) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
}
private void consecutiveAnagrams(String[] strings) {
Arrays.sort(strings, new AnagramComparator());
}
class AnagramComparator implements Comparator<String> {
@Override
public int compare(String one, String two) {
String s1 = sortChars(one);
String s2 = sortChars(two);
return s1.compareTo(s2);
}
String sortChars(String str) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
return new String(chars);
}
}
private void consecutiveAnagrams(String[] strings) {
Arrays.sort(strings, new AnagramComparator());
}
package Amazon;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Anagram {
public static void main(String[] str) {
String[] str_inp = { "car", "krap","god", "rac", "dog", "another","park" };
Map<String, String> str_map = new HashMap<String, String>();
String ana_str = "";
for (int index = 0; index < str_inp.length; index++) {
ana_str = sort_array(str_inp[index]);
if (!str_map.containsKey(str_inp[index]))
{
if (str_map.containsKey(ana_str))
{
str_map.put(ana_str, str_inp[index]);
}
else
{
str_map.put(str_inp[index], null);
}
}
}
for (Object keys : str_map.keySet()) {
System.out.println("{" + keys + ","+ str_map.get(keys) + "}");
}
}
public static String sort_array(String str) {
char[] str_arr = str.toCharArray();
char[] str_arr_tmp;
int len = str_arr.length;
str_arr_tmp = new char[len];
int index = 0;
while (len > 0) {
str_arr_tmp[index++] = str_arr[--len];
}
String tmp = new String(str_arr_tmp);
return (tmp);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Anagram {
public static void main(String[] str) {
String[] str_inp = { "car", "krap","god", "rac", "dog", "another","park" };
Map<String, String> str_map = new HashMap<String, String>();
String ana_str = "";
for (int index = 0; index < str_inp.length; index++) {
ana_str = sort_array(str_inp[index]);
if (!str_map.containsKey(str_inp[index]))
{
if (str_map.containsKey(ana_str))
{
str_map.put(ana_str, str_inp[index]);
}
else
{
str_map.put(str_inp[index], null);
}
}
}
for (Object keys : str_map.keySet()) {
System.out.println("{" + keys + ","+ str_map.get(keys) + "}");
}
}
public static String sort_array(String str) {
char[] str_arr = str.toCharArray();
char[] str_arr_tmp;
int len = str_arr.length;
str_arr_tmp = new char[len];
int index = 0;
while (len > 0) {
str_arr_tmp[index++] = str_arr[--len];
}
String tmp = new String(str_arr_tmp);
return (tmp);
}
}
Runs in O(n) time.
Considering that the random strings are words, real words has a max_size of ~30 chars, or that it's random chars, but with a max of a constant, this will yield O(n * c) where c == avg number of chars in a word, thus it's constant, thus this is O(n).
- Goro May 26, 2016using System; using System.Linq; using System.Collections.Generic; using System.IO; public class Test { public static void Main() { var list = new List<string> { "car", "god", "arc", "dog", "another" }; var dict = new Dictionary<string, List<string>>(); foreach(var word in list) { var sorted = String.Concat(word.OrderBy(c => c)); if (dict.ContainsKey(sorted)) { if (dict[sorted] == null) dict[sorted] = new List<string>(); dict[sorted].Add(word); } else { dict.Add(sorted, new List<string> { word }); } } foreach(var pair in dict) { Console.WriteLine(String.Join(" ", pair.Value)); } } }