CareerCup

Here is the full java implementation:
It takes advantage of hashing and sorting. Sort each string alphabetically via quicksort.
Hash each string to avoid multiple comparisons, we can compare numbers easily.
Then print out buckets which are just hashtable values.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramBucket {
	/*
	 *  Input - List<String> ["star", "rats", "ice", "cie", "arts"] 
	 *	print all anagrams in buckets: 
	 *  ["star", "rats", "arts"] 
	 *  ["ice", "cie"] 
	 * 
	 *  Our implementation will take advantage of hashing and string sorting.
	 *  This is O(n*mlog(m)) where m is the length of average string, n=# strings.
	 *  We first sort each string using quicksort on the characters.
	 *  Then, hash the sorted strings into numbers which takes O(n*m). 
	 *  Then we make one more pass and dump them into buckets.
	 *  
	 */
	static String sortstr(String str) {
		/* encapsulating original sortstr method */
		char[] chararr = str.toCharArray();
		sortstr(chararr, 0, str.length()-1);
		return new String(chararr);
	}
	
	static void sortstr(char[] arrchar, int start, int end) {
		/* inplace quicksort, car=>acr */
		if (start > end)
			return;
		
		int piv = arrchar[end];
		int lo = start;
		int hi = end;
		while (lo <= hi) {
			while (arrchar[lo] < piv)
				lo += 1;
			while (arrchar[hi] > piv)
				hi -= 1;
			if (lo <= hi) {
				char tmp = arrchar[lo];
				arrchar[lo] = arrchar[hi];
				arrchar[hi] = tmp;
				lo += 1;
				hi -= 1;
			}
		}
		sortstr(arrchar, start, hi);
		sortstr(arrchar, lo, end);
	}
	
	static void anagrambuckets(List<String> input) {
		HashMap<Integer, List<String>> map = 
				new HashMap<Integer, List<String>>();
		
		for (int i=0; i<input.size(); i++) {
			String srtedstr = sortstr(input.get(i));
			int code = srtedstr.hashCode();
			if (map.containsKey(code)) {
				map.get(code).add(input.get(i));
			}
			else {
				List<String> z = new ArrayList<String>();
				z.add(input.get(i));
				map.put(code, z);
			}
		}
		
		for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
			System.out.println("Key " + entry.getKey() + 
				" bucket: " + entry.getValue().toString());
		}
	}
	
	public static void main(String[] args) {
		List<String> input = new ArrayList<String>();
		input.add("star");
		input.add("rats");
		input.add("ics");
		input.add("cie");
		input.add("arts");
		anagrambuckets(input);
	}
}

Sorry I am not going to answer this in java,

>>> words=["star", "rats", "ice", "cie", "arts"]
>>> from itertools import groupby
>>> [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]
[['star', 'rats', 'arts'], ['ice', 'cie']]
>>>

// assuming 'star' == 'rats' == Ascii calculation is always same
public static void anagramBuckets(List<String> input) {

HashMap<Integer, List<String>> hashMap = new HashMap<Integer, List<String>>();

for (String stringValue : input) {
      int temp = 0;
      for (int i = 0; i < stringValue.length(); i++) {
             temp = temp + (int) stringValue.charAt(i);
      }
     if (hashMap.containsKey(temp)) {
        List<String> list = hashMap.get(temp);
        list.add(stringValue);
        hashMap.put(temp, list);
     } else {
       List<String> list = new ArrayList<String>();
       list.add(stringValue);
       hashMap.put(temp, list);
     }
}

Set<Integer> keys = hashMap.keySet();
for (Integer key : keys) {
System.out.println(hashMap.get(key));
}

Here's my implementation in Obj-C.

The isAnagram function takes the letters of the first string and puts them in a bag. As we walk through the second string we pull those same letters out. If there are still letters left in the bag when we end, or if any of the letters in the second string aren't in the bag, we return NO;

In the second algorithm I'm trying to limit comparisons by selecting one member of the bucket to act as the prototype (key) for all the members of that bucket. We only compare against the key, and build the list of key/values progressively. Should keep calls to isAnagram a little lower.

BOOL isAnagram(NSString *w1, NSString *w2) {
    if(w1.length != w2.length) {
        return NO;
    }
    
    NSMutableDictionary *chars = [NSMutableDictionary dictionary];
    
    for(int i = 0; i < w1.length; i++) {
        NSString *curChar = [w1 substringWithRange:NSMakeRange(i, 1)];
        NSNumber *count = chars[curChar];
        chars[curChar] = @(count.intValue + 1);
    }
    
    for(int i = 0; i < w2.length; i++) {
        NSString *curChar = [w2 substringWithRange:NSMakeRange(i,1)];
        NSNumber *count = chars[curChar];
        if(count) {
            int newValue = count.intValue - 1;
            if(newValue == 0) {
                [chars removeObjectForKey:curChar];
            } else {
                chars[curChar] = @(newValue);
            }
        } else {
            return NO;
        }
    }
    
    if(chars.count == 0) {
        return YES;
    } else {
        return NO;
    }
}

NSArray *anagramBuckets(NSArray *strings) {
    NSMutableDictionary *buckets = [NSMutableDictionary dictionary];
    
    for(NSString *str in strings) {
        BOOL added = NO;
        for(NSString *key in buckets) {
            if(isAnagram(str, key)) {
                NSMutableArray *bucket = buckets[key];
                [bucket addObject:str];
                added = YES;
                break;
            }
        }
        
        if(!added) {
            buckets[str] = [NSMutableArray arrayWithObject:str];
        }
    }
    
    return [buckets allValues];
}

The output of the following code is:
[ice,cie,]
[star,rats,arts,]

public class AnagramTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] myWords={"star", "rats", "ice", "cie", "arts"};
		List<String> mylist = Arrays.asList(myWords);
		anagramBuckets(mylist);
	}
	public static void anagramBuckets(List<String> input){
		Map<String, List<String>> map = new HashMap<String, List<String>>();
		ArrayList<String> arrayList;
		String temp;
		boolean alreadyPresent;
		if(input.size()>1){
			String first = input.get(0);
			arrayList = new ArrayList<String>();
			arrayList.add(first);
			map.put(first, arrayList);
			for (int i = 1; i < input.size(); i++) {
				temp = input.get(i);
				alreadyPresent = false;
				for (String string : map.keySet()) {
					if(areAnagrams(temp, string)){
						map.get(string).add(temp);
						alreadyPresent = true;
					}
				}
				if(!alreadyPresent){
					arrayList = new ArrayList<String>();
					arrayList.add(temp);
					map.put(temp, arrayList);
				}
			}
		}
		
		for (String string : map.keySet()) {
			System.out.print("[");
			for (String string1 : (ArrayList<String>)map.get(string)) {
				System.out.print(string1+",");
			}
			System.out.println("]");
		}
		
		
	}

	public static boolean areAnagrams(String first, String second){
		if(first.length() != second.length())
			return false;
		int[] char_values = new int[256];
		char charAt;
		int uniqueCharsInFirstString = 0;
		int completedCharsSecondString = 0;
		for (int i = 0; i < first.length(); i++) {
			charAt = first.charAt(i);
			if(char_values[charAt] == 0){
				uniqueCharsInFirstString++;
			}
			char_values[charAt]++;
		}
		for (int i = 0; i < second.length(); i++) {
			charAt = second.charAt(i);
			if(char_values[charAt] == 0)
				return false;
			--char_values[charAt];
			if(char_values[charAt] == 0){
				completedCharsSecondString++;
				if(uniqueCharsInFirstString == completedCharsSecondString){
					return (i == second.length()-1);
				}
			}
		}		
		return false;
	}

}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Sort {

	public static void main(String[] args) {

		String[] words = {"star", "rats", "ice", "cie", "arts"};
		List<List<String>> result = new ArrayList<List<String>>();
		boolean isFound = false;
		char[] charArray = null;
		char[] tempCharArray = null;
		for(String str:words){
			charArray = str.toCharArray();
			isFound = false;
			Arrays.sort(charArray);
			for(List<String> list:result){
				for(String tempStr:list){
					tempCharArray = tempStr.toCharArray();
					Arrays.sort(tempCharArray);
					if(String.valueOf(tempCharArray).equals(String.valueOf(charArray))){
						list.add(str);
						isFound = true;
						break;
					}
				}
			}
			if(!isFound){
				List<String> tempList = new ArrayList<String>(); 
				tempList.add(str);
				result.add(tempList);
			}
			
		}
		System.out.println(result);
	}

}

C# Implementation

namespace fb_anagrambuckets
{
	class Program
	{
		public void AnagramBuckets(List<string> input)
		{
			// map sorted(word) to [word,...]
			var map = new Dictionary<string, List<string>>();

			foreach (string word in input)
			{
				string sortedChars = String.Concat<char>(word.OrderBy(c => c));

				List<string> bucket;
				if (!map.TryGetValue(sortedChars, out bucket))
				{
					map[sortedChars] = bucket = new List<string>();
				}

				bucket.Add(word);
			}

			foreach (var bucket in map.Values)
			{
				string str = bucket.Aggregate((list, word) => list + " " + word);
				Console.WriteLine("[" + str + "]");
			}
		}

		static void Main(string[] args)
		{
			Program p = new Program();
			p.AnagramBuckets(new List<string> { "star", "rats", "ice", "cie", "arts" });
		}
	}
}

Sort each string and put it in a trie.
Sorting a string can be done in O(n) time and constant space - keep track of count of each characters and print in sorted order.
Trie insertion = O(n)
Total complexity - O(n*m)
m = number of strings in array
n = size of strings in array.

I would use the List<String> as a dictionary and do the following:
1. Pre-process
-- Sort letters in string and form key
-- Add the word from list to hash table, with key from previous step
2. Print values (list of words with same key) for each key in bucket

class AnagramAI
    {
        public static void Do()
        {
            List<string> inputs = new List<string>() { "star", "rats", "ice", "cie", "arts" };
            AnagramBuckets(inputs);
        }

        public static void AnagramBuckets(List<string> input)
        {
            List<string> processed = new List<string>();
            List<List<string>> buckets = new List<List<string>>();

            List<string> anagrams = null;
            for (int i = 0; i < input.Count; i++)
            {
                //Console.Write("{0}", input[i]);
                if (processed.Contains(input[i]))
                {
                    continue;
                }
                else
                {
                    anagrams = new List<string>();
                    anagrams.Add(input[i]);
                    processed.Add(input[i]);
                }
                for (int j = i + 1; j < input.Count; j++)
                {
                    if (!processed.Contains(input[j]) && IsAnagram(input[i], input[j]))
                    {
                        //Console.Write(",{0}", input[j]);
                        anagrams.Add(input[j]);
                        processed.Add(input[j]);
                    }
                }
                //Console.WriteLine();
                buckets.Add(anagrams);
            }

            foreach (List<string> buck in buckets)
            {
                foreach (string s in buck)
                {
                    Console.Write("{0},", s);
                }
                Console.WriteLine();
            }
        }

        private static bool IsAnagram(string a, string b)
        {
            if (a.Length == b.Length)
            {
                char[] charas = a.ToCharArray();
                Array.Sort<char>(charas);
                char[] charbs = b.ToCharArray();
                Array.Sort<char>(charbs);

                for (int i = 0; i < charas.Length; i++)
                {
                    if (charas[i] != charbs[i])
                    {
                        return false;
                    }
                }

                return true;
            }

            return false;
        }
    }

package com.test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Anagram {

/**
* @param args
*/
public static void main(String[] args) {
List<String> anagrams = new LinkedList<String>();
anagrams.add("star");
anagrams.add("rats");
anagrams.add("ice");
anagrams.add("cie");
anagrams.add("arts");

List<ArrayList<String>> anagramBuckets = anagramBuckets(anagrams);
System.out.println(anagramBuckets);

}

public static List<ArrayList<String>> anagramBuckets(List<String> input) {
List<ArrayList<String>> buckets = new LinkedList<ArrayList<String>>();
for (String instr : input) {
int i = 0;
System.out.println(i);
while (true) {
if (i == buckets.size()) {
//System.out.println(i);
System.out.println(instr);
buckets.add(new ArrayList<String>());
buckets.get(i).add(instr);
break;
} else if (isAnagram(buckets.get(i).get(0), instr)) {
// System.out.println(instr);
buckets.get(i).add(instr);
break;
}
i++;
}
}
return buckets;
}

public static boolean isAnagram(String str1, String str2) {

for (int i = 0; i < str1.length(); i++) {
int indexOf = str2.indexOf(str1.charAt(i));
if (indexOf < 0) {
return false;
}
String tmp = str2.substring(0, indexOf)
+ str2.substring(indexOf + 1, str2.length());
str2 = tmp;
}
if (str2.equals("")) {
return true;
} else {
return false;
}
}

}

n max number of chars in a string (sort the chars)
m number of strings (group and print strings)
Total complexity: O(m*nlogn)
Code in C#:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
       List<String>  Input = new List<String> (){"star", "rats", "ice", "cie","arts" };
       
       var dict = Input.ToDictionary( item => item ,
       item =>sortIt(item.ToCharArray())) /*sorted String*/
       .GroupBy(a => a.Value); 
    
   
	foreach (var pair2 in dict)
	{ string Line= "[";
      foreach (var pair in pair2)
	  {
	    Line += "\""+pair.Key+"\",";
      }
      Line = Line.Remove(Line.Length-1); //remove last ","
      Line +="]";
      Console.WriteLine(Line);
    }}
    
     static string sortIt(char[] chArray) {
    	Array.Sort<char>(chArray); return new string (chArray);
	}
}

Ruby Implementation:-

a = ['star', 'rats', 'ice', 'cie', 'arts']

a.group_by{|x| x.chars.sort.join}

Ans:
#<OrderedHash {"arst"=>["star", "rats", "arts"], "cei"=>["ice", "cie"]}>

void ShowAnagrams(list<string>str)
{
	if(str.empty())
		return;
	multimap<string,string>m;
	multimap<string,string>::iterator ptr;
	list<string>::iterator p;
	for(p=str.begin();p!=str.end();p++)
	{
		string s=(*p);
		sort(s.begin(),s.end());
		m.insert(make_pair(s,(*p)));
	}
	
	string prev=str.front();
	sort(prev.begin(),prev.end());
	for(ptr=m.begin();ptr!=m.end();ptr++)
	{		
		if(prev==(*ptr).first)
			cout<<(*ptr).second<<"\t";
		else
		{
			prev=(*ptr).first;
			cout<<endl;
			cout<<(*ptr).second<<"\t";
		}
	}
}

public static void anagramBuckets(List<String> input) {		
		
		Map<String, Collection<String>> bucket = new HashMap<String, Collection<String>>();
		for (String word : input) {
			char[] charArr = word.toCharArray();
			Arrays.sort(charArr);
			Collection<String> collection = null;
			String str = new String(charArr);
			if (bucket.containsKey(str)) 
				collection = bucket.get(str);			
			else 
				collection = new ArrayList<String>();			
			collection.add(word);
			bucket.put(str, collection);
		}
		
		for (Entry<String, Collection<String>> entry : bucket.entrySet()) {
			System.out.println(entry.getValue());			
		}
	}

Simple one via C#:

static List<List<string>> GroupAnagrams(string[] words)
{
    Dictionary<string, List<string>> d = new Dictionary<string, List<string>>();
    foreach (var word in words)
    {
        string key = new string(word.ToCharArray().OrderBy(_ => _).ToArray());

        if (!d.ContainsKey(key))
        {
            d.Add(key, new List<string>());
        }

        d[key].Add(word);
    }

    return d.Values.ToList();
}

similiar solutions. 1. go through the list 2. for each string in the list, change it to char array. 3. sort the char array. Put the sorted char array as key, the original string as value, to a HashMap. 4. compare each sorted string with the HashMap. 5. go through the hashmap to print all the result.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class RearrangeWords {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("star");
        list.add("rats");
        list.add("ice");
        list.add("cie");
        list.add("arts");
        Map<String, List<String>> map = storeStrings(list);
        printMap(map);
    }
    
    public static void printMap(Map<String, List<String>> map) {
        for(String key : map.keySet()) {
            for(String item : map.get(key)) {
                System.out.print(item + " ");
            }
            System.out.println();
        }
    }

    public static Map<String, List<String>> storeStrings(List<String> list) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for(String str : list) {
            char[] chars = str.toCharArray();
            sort(chars, 0, chars.length - 1);
            String sortedStr = new String(chars);
            if(map.containsKey(sortedStr)) {
                map.get(sortedStr).add(str);
            } else {
                List<String> array = new ArrayList<String>();
                array.add(str);
                map.put(sortedStr, array);
            }
        }

        return map;
    }

    public static void sort(char[] charlist, int l, int r) {
        if(l < r) {
            int p = partition(charlist, l, r);
            sort(charlist, l, p - 1);
            sort(charlist, p + 1, r);
        }
    }

    public static int partition(char[] charlist, int l, int r) {
        char val = charlist[r];
        int j = l - 1;
        for(int i = l; i < r; i++) {
            if(charlist[i] < val) {
                j++;
                swap(charlist, i, j);
            }
        }
        swap(charlist, j + 1, r);

        return j + 1;
    }

    public static void swap(char[] charlist, int i, int j) {
        char temp = charlist[i];
        charlist[i] = charlist[j];
        charlist[j] = temp;
    }

public static void anagramBuckets(List<String> input) {
		Map<Integer, List<String>> anagrams = new HashMap<Integer, List<String>>();

		for (String word : input) {
			TreeMap<Character, Integer> tree = getTree(word);
			if (anagrams.containsKey(tree.hashCode())) {
				List<String> words = anagrams.get(tree.hashCode());
				anagrams.remove(tree.hashCode());
				words.add(word);
				anagrams.put(tree.hashCode(), words);
			} else {
				List<String> words = new ArrayList<String>();
				words.add(word);
				anagrams.put(tree.hashCode(), words);
			}
		}

		for (Entry<Integer, List<String>> entry : anagrams.entrySet()) {
			System.out.println(entry.getValue());
		}

	}

	private static TreeMap<Character, Integer> getTree(String word) {
		TreeMap<Character, Integer> tree = new TreeMap<Character, Integer>();

		for (int i = 0; i < word.length(); i++) {
			tree.put(word.charAt(i), 0);
		}

		return tree;
	}

Sort all words and compare - n*k*logk
Using hashing that always works will make the sort redundant - n*k (I don't know how to do a hash that always works)

public void anagramBuckets(List<String> input) {
	HashsMap<Integer, List<String>> map = new ...;
	for(String string : input) {
		int hash = string.hashCode();
		List<String> bucket = map.get(hash);
		if (bucket == null) {
			bucket = new ArrayList<...>();
			map.put(hash, bucket);
		}
		bucket.add(string);
	}
	// Contains the sorted string as key and the original as value
	HashMap<String, List<String>> sorted = new ...;
	for(List<String> hashedBucket : map.values) {
		if (hashBucket.size() == 1) {
			List<String> bucket = new ArrayList<String>();
			sorted.put(sortedString, bucket);
			bucket.add(string);
			continue;
		}
		for(String string : hashBucket) {
			String sortedString = sort(string);
			List<String> bucket = sorted.get(sortedString);
			if (bucket == null) {
				bucket = new ArrayList<String>();
				sorted.put(sortedString, bucket);
			}
			bucket.add(string);
		}
	}
	for(List<String> bucket : sorted.values) {
		print(bucket);
	}
}

vector < vector < string > > anagrambuckets(vector < string > s)
{
    int n = s.size();
    map < string, vector < string > > track;
    vector < vector < string > > ret;
    for(int i = 0; i < n; ++i)
    {
        string sorted = s[i];
        sort(sorted.begin(), sorted.end());
        track[sorted].push_back(s[i]);
    }
    for(map < string, vector < string > >::iterator it = track.begin(); it != track.end(); ++it)
    {
        ret.push_back(it->second);
    }
    return ret;
}

private static void anagrams() {
        String[] list = new String[]{"star", "rats", "ice", "cie", "arts"};

        Map<Integer, List<String>> anagramsMap = new HashMap<>();

        for (String word : list) {
            ArrayList<Character> charList = new ArrayList<>();
            for (char character : word.toCharArray()) {
                charList.add(character);
            }
            Set<Character> set = new TreeSet<>(charList);
            StringBuilder sb = new StringBuilder();
            Iterator<Character> iterator = set.iterator();
            while (iterator.hasNext()) {
                sb.append(iterator.next());
            }

            if (sb != null && sb.length() > 0) {
                String newWord = sb.toString();
                int hashCode = newWord.hashCode();
                if (anagramsMap.containsKey(hashCode)) {
                    anagramsMap.get(hashCode).add(word);
                } else {
                    ArrayList<String> valueList = new ArrayList<>();
                    valueList.add(word);
                    anagramsMap.put(hashCode, valueList);
                }
            }
        }

        for (List<String> anagramsList : anagramsMap.values()) {
            System.out.println("[ " + StringUtils.join(anagramsList, ", ") + " ]");
        }
    }

from collections import defaultdict

buckets = defaultdict(list)
words = ["star", "rats", "ice", "cie", "arts"]

for i in xrange(len(words)):
    sort = ''.join(sorted(words[i]))
    buckets[sort].append(words[i])

For each string in the list, sort the string alphabetically and store in a hashmap.
For a given key, the values will be the anagrams.
// Sample
HashMap<String, List<String>> anagramsBuckets = new HashMap<String, List<Strings>();
//Parse the input and store in map
star, rats, arts will be arst sorted alphabetically
arst -> rats, star, arts
(key) -> (values)

For the given input string whose anagrams we should find, sort the input again and find all values for that key. That will be all the anagrams of the string.

One needs two things to identify elements belonging to the same bucket:
1.length
2.A bit string that correspond to the asciii values present in the anagram. This will be a 32bit int value if the words are limited to lower case.
---------------
declare a list for buckets: listB
then iterate though the input list
for each element in the input list, iterate through listB
if(cur belongs to a bucket in listB)
{add cur to listB}
else
{establish a new bucket based on the two aforementioned properties of cur}