CareerCup

Constraints:
1. Web-service should return the result with in sub-second (< 1 second)
2. Using the permutation mechanism can slow down the processing
3. The data structure used to store the dictionary should be explained as well

Algorithm:
1. Pre-processing: Store the dictionary as multimap <Key, words>. Construct the key by sorting the letters of the word. (Use quick sort for sorting the letters)
2. Web-Service: The web-service takes the word as input and sort the letters using quick sort O(nlogn) and query the multimap O(1) for all the anagrams.

This is like asking to print all the 'valid' permutations of the word, the validity of whom is checked against a given dictionary.

We make hash map, from sorted word letters. When we recieve a request with word, we sort it and return all words from appropriate bucket. Also hash table can be distributed. We assign to node some interval from aaaaaa to xxxxxx, for instance. Each node is responsible for continious interval of sorted in lexicographicsl order strings. So we can very fast make decision which node shoud proceed request.

For a one-off puzzle, you could just do the permutations approach. For a web service though, it wouldn't make sense to re-compute the permutations every time a request is received.

My suggestion would be to simply structure the dictionary as a hash map, where the keys are unique sorted words and the values are all words which when sorted yield the key.

The problem gets a lot more interesting if your service has to support other queries as well, not just finding anagrams. The above representation of the dictionary is ideal for anagrams but maybe bad for different sorts of queries.

#include <iostream>                                                             
                                                                                
using namespace std;                                                            
                                                                                
void backtrack(string s, string sofar)                                          
{                                                                               
  if (s == "")                                                                  
  {                                                                             
    cout << sofar<<endl;                                                        
  }                                                                             
  for(int i=0; i< s.length(); i++)                                              
  {                                                                             
    int len= s.length();                                                        
    char c= s[i];                                                               
    sofar.append(1, c);                                                         
    string snew= s.substr(0,i);                                                 
    if(i<s.length())                                                            
      snew.append(s.substr(i+1));                                               
    backtrack(snew, sofar);                                                     
    sofar.erase(sofar.length()-1, 1);                                           
  }                                                                             
}                                                                               
                                                                                
                                                                                
int main()                                                                      
{                                                                               
  string s;                                                                     
  cin>>s;                                                                       
  backtrack(s,"");                                                              
  return 0;                                                                     
}

import java.util.*;
import java.io.*;
import java.net.*;

public class Anagrams
{
	public static void main(String[] args) throws IOException
	{
		URL url = new URL("dictionary.txt");
		Scanner sc = new Scanner( url.openStream() );

		HashMap<String, ArrayList<String>> map =  new HashMap<String, ArrayList<String>>();

		while( sc.hasNextLine() )
		{
			String word = sc.nextLine();
			String sortedWord = sortString(word); // this is a key

			ArrayList<String> anagrams = map.get( sortedWord );  //this is a value

			if( anagrams == null ) anagrams = new ArrayList<String>();

			anagrams.add(word);
			map.put(sortedWord, anagrams);
		}
		System.out.println(map.get(sortString("bread")));   //testing

	}
	private static String sortString( String w )
	{
		char[] ch = w.toCharArray();
		Arrays.sort(ch);
		return new String(ch);
	}
}

Generate all the permutaion of the string and check against the dictionary whether the word is valid or not.

public class Practice55 {
	public static void main(String args[]){
		String str = "abc";
		printPermu("",str);
	}
	
	public static void printPermu(String prefix,String str){
		int n = str.length();
		if(n == 0){
			//Write here the code to check whether the word is present in dictionary. If yes, print it. 
			System.out.println(prefix);
		}else{
			for(int i=0;i<n;i++){
				printPermu(prefix + str.charAt(i),str.substring(0,i) + str.substring(i+1,n));
			}
		}
	}
}