Implementing a system for fast anagrams retrieval given a large file of words

Question

Srini · Accepted Answer

Process the large file first. Create a hash table with key : sorted characters in the word. values : words from the large file.

Now all you gotta do is , take the word for which you want to find anagrams, sort the characters , lookup the hash table.

Liron · Answer

Great solution Srini :) I coded it as well

package com.google;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class ReadFile {
	private Map words;
	
	public ReadFile(Map words) {
		super();
		this.words = words;
	}

	public Map getWords() {
		return words;
	}

	public void setWords(Map words) {
		this.words = words;
	}

	public void hashWord(String word){
		char[] chars = word.toCharArray();
		List list = new ArrayList();
		for (char c : chars){
			list.add(c);
		}
		Collections.sort(list);
		StringBuffer str = new StringBuffer();
		for (char c : list){
			str.append(c);
		}
		Map map = this.getWords();
		map.put(str.toString(), word);
		this.setWords(map);
	}

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		 
         StringBuffer word = new StringBuffer();
         Map map = new HashMap();
         ReadFile rf = new ReadFile(map);
         
         Scanner input = new Scanner(new File("liron.txt"));
 		
         while(input.hasNext()) {
        	 word .append(input.next());
        	 rf.hashWord(word.toString());
             word.delete(0, word.length());
 		}
 		
                  
         
         map = rf.getWords();
         for (String key : map.keySet()){
        	 System.out.println("key="+key+" "+"value="+map.get(key));
         }
	}

}

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas