CareerCup

Here is a full implementation. It expects a file containing list of words as command line argument. The implementation uses Trie and PriorityQueue.

// Implement a T9 Dictionary
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Comparator;

public class T9Dictionary {

	Trie trie;

	public static void main (String [] args) {
		if (args.length != 1) {
			System.err.println("There should only be one and only one command line argument.");
		}
		BufferedReader reader = null;
		try {
			reader = new BufferedReader(new FileReader(args[0]));
		}
		catch (FileNotFoundException e) {
			System.err.println("File not found");
			return;
		}
		
		List<String> words = new ArrayList<String>();
		String str;
		try {
			while ((str = reader.readLine()) != null) {
				words.add(str.toLowerCase());
			}
		}
		catch (IOException e) {
			System.err.println("Some error while reading file");
			System.exit(1);
		}
		

		T9Dictionary t9Dict = new T9Dictionary();
		t9Dict.createTrie(words);

		System.out.println("Enter the numeric string to search: ");
		Scanner s = new Scanner(System.in);
		String numString = s.nextLine();

		List<String> suggestions = t9Dict.getSuggestions(numString);
		System.out.println("Suggestions: ");
		if (suggestions != null) {
			for (String word : suggestions) {
				System.out.print(word + "\t");
			}
		}
		else {
			System.out.println("No suggestions");
		}

	}

	public T9Dictionary() {
		trie = new Trie();
	}

	private void createTrie(List<String> words) {
		for (String word : words) {
			trie.add(word);
		}
	}

	// Returns the first three suggestion based on the string passed.
	public List<String> getSuggestions(String numString) {
		List<String> results = trie.search(numString);
		if (results != null) {
			return results.subList(0, Math.min(3, results.size()));
		}
		return null;
	}
}

class Trie {
	Node node;
	Trie[] children;

	// Create an empty trie
	Trie() {
		node = new Node();
		children = new Trie[8];
	}

	void add(String str) {
		char [] chrs = str.toCharArray();
		Trie node = this;
		for (int i = 0; i < chrs.length; i++) {
			int index = getNodeIndexFromChar(chrs[i]);
			if (node.children[index] == null) {
				node.children[index] = new Trie();
			}
			node = node.children[index];
		}
		node.node.addWord(str);
	}

	// The str passed should be a string with digits only between (2 to 9)
	List<String> search(String str) {
		System.out.println("Searching for " + str);
		List<String> list = null;
		Trie trie = this;
		char[] chrs = str.toCharArray();
		for (char chr : chrs) {
			if (chr < '2' || chr > '9') {
				System.err.println("Wrong search string: " + str);
				return null;
			}
			else {
				trie = trie.children[getNodeIndexFromNumChar(chr)];
				if (trie == null) {
					System.out.println("No matching string found.");
					return null;
				}
			}
		}
		if (!trie.node.isLeafNode()) {
			System.out.println("Node found but not a leaf node.");
		}
		else {
			PriorityQueue<Word> pq = trie.node.pq;
			list = new ArrayList<String>();
			List<Word> wordList = new ArrayList<Word>();
			int size = pq.size();
			for (int i = 0; i < 3 && i < size; i++) {
				Word word = pq.poll();
				list.add(word.word);
				wordList.add(word);
			}
			for (Word word : wordList) {
				pq.offer(word);
			}
		}
		return list;
	}

	 int getNodeIndexFromChar(char ch) {
	 	if (ch == 'a' || ch == 'b' || ch == 'c') {
	 		return 0;
	 	}
	 	if (ch == 'd' || ch == 'e' || ch == 'f') {
	 		return 1;
	 	}
	 	if (ch == 'g' || ch == 'h' || ch == 'i') {
	 		return 2;
	 	}
	 	if (ch == 'j' || ch == 'k' || ch == 'l') {
	 		return 3;
	 	}
	 	if (ch == 'm' || ch == 'n' || ch == 'o') {
	 		return 4;
	 	}
	 	if (ch == 'p' || ch == 'q' || ch == 'r' || ch == 's') {
	 		return 5;
	 	}
	 	if (ch == 't' || ch == 'u' || ch == 'v') {
	 		return 6;
	 	}
	 	if (ch == 'w' || ch == 'x' || ch == 'y' || ch == 'z') {
	 		return 7;
	 	}
	 	return -1;
	 }

	 int getNodeIndexFromNumChar(char chr) {
	 	return chr - '0' - 2;
	 }
}

class Node {
	public static WordComparator comp = new WordComparator();
	private boolean isLeaf;
	PriorityQueue<Word> pq;

	Node () {
		isLeaf = false;
	}

	public boolean isLeafNode() {
		return isLeaf;
	}

	public void addWord(String str) {
		if (this.isLeaf == false) {
			this.isLeaf = true;
			WordComparator comp = new WordComparator();
			pq = new PriorityQueue<Word>(10, comp);
		}
		// Check if the word is in the queue, if yes, increase its frequency
		Word w = new Word(str, 1);
		for (Word word : pq) {
			if (word.word.compareTo(str) == 0) {
				pq.remove(word);
				word.frequency++;
				w = word;
				break;
			}
		}
		pq.offer(w);
	}
}

class Word{
	int frequency;
	String word;

	Word (String word, int frequency) {
		this.word = word;
		this.frequency = frequency;
	}
}

class WordComparator implements Comparator<Word>{
	public int compare(Word w1, Word w2) {
		return w2.frequency - w1.frequency;
	}
}

this could be solved with a trie data structure.
1) let's create a trie from dictionary
2) for every node in trie, let's precalculate and cache top 3 words based on ranking. This could be done with dfs(node), where dfs returns minHeap with top 3 words matching the current prefix. In every node, heap does not contain more than 3 elements in it. Once we reach a new word in trie, we compare its ranking with min value in heap, replace iff curValue > minValue.
3) Having built trie, let's try all possible strings that can be formed with given digits. In worst case that would be O(3^m), where m is the number of typed digits. However, having trie we won't generate strings that we definetely now not in dictionary

So overall complexity is O(3^m + sum(length of words in dictionary))

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class WordRanking {

	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new FileReader(new File("4000MostCommonWords"))); /* file that has ranking of most commonly used words */
		String str = null;
		Trie trie = new Trie(); // my Trie implementation
		int count = 1;
		while((str = br.readLine()) != null) {
			trie.addWordRank(str, count++);
		}
		br.close();
		br = new BufferedReader(new InputStreamReader(System.in)); / * read numerickey from console */

		KeyPadT9 keyPadT9 = new KeyPadT9(trie);
		System.out.println("Enter keys in your numeric keypad");
		String key = br.readLine();
		
		System.out.println(Arrays.toString(keyPadT9.findImportantWordsForKey(key).toArray()));
	}
}


class KeyPadT9 {
	
	Trie rankedWords = null;
	Map<Integer, List<Character>> map = null;
	PriorityQueue<WordRank> queue = null;
	Comparator<WordRank> comparator = null;
	public KeyPadT9(Trie trie) {
		this.rankedWords = trie;
		this.map = new HashMap<Integer, List<Character>>();
		initializeMap();
		setComparator();
	}
	
	private void setComparator() {
		comparator = new Comparator<WordRank>() {
			
			@Override
			public int compare(WordRank o1, WordRank o2) {
				if(o1.rank > o2.rank)
					return 1;
				else if(o1.rank < o2.rank) 
					return -1;
				else 
					return 0;
			}
		};
	}
	
	private void initializeMap() {
		char c = 'a';
		int count = 0;
		for(int i=2; i<=9; i++) {
			map.put(i, new ArrayList<Character>());
			count = 0;
			while(count < 3 && c <= 'z') { /* constructing keypad */
				map.get(i).add(c++);
				count++;
			}
		}
	}
	
	public List<WordRank> findImportantWordsForKey(String key) {
		
		queue = new PriorityQueue<>(3, comparator); // we only want top 3
		findImportantWordsForKey(key, "");
		List<WordRank> list = new ArrayList<>();
		while(!queue.isEmpty()) {
			list.add(queue.poll());
		}
		return list;
	}
	
	private void findImportantWordsForKey(String key, String word) {
		 
		if(key.isEmpty()) {
			queue.addAll(rankedWords.getAllWordsStartingWith(word));
			return;
		}
		
		int keyNum = Integer.parseInt(key.substring(0, 1));
		List<Character> chars = map.get(keyNum);
		for(char c : chars) {
			findImportantWordsForKey(new String(key.substring(1)), new String(word+c));
		}
		
	}
	
	
}

It seems somewhat complicated because it uses a bottom up dynamic programming algorithm.

public static List<string> GetTopWords(int[] keys, Dictionary<string,int> words, int top)
{
	if(keys == null || keys.Length == 0) 
		return null;
	
	List<string> possibleStrings = GetAllPossibleStrings(keys);

	SortedDictionary<int, string> sorter = new SortedDictionary<int, string>();

	foreach(string ps in possibleStrings)
	{
		if(words.ContainsKey(ps))
		{
			sorter.Add(words[ps], ps);
		}
	}

	List<string> result = new List<string>();
	foreach(var kvp in sorter)
	{
		if(top == 0)
			break;

		result.Add(kvp.Value);
		top--;
	}

	return result;
}



List<string> GetAllPossibleStrings(int[] keys)
{
	// Bottom-up algorithm using dynamic programming

	List<string> results = new List<string>();
	int start = keys.Length - 1;

	// Populate the last letter
	foreach(char c in getChars(keys[start--])
	{
		result.Add(c.ToString());
	}

	start --;
	while(start >=0)
	{
		List<string> temp = new List<string>();
		foreach(char c in getChars(keys[start--])
		{
			foreach(string r in result)
			{
				temp.Add(c + r);
			}
		}

		result = temp;
	}

	return result;
}

package t9keyboard

/**
 You have a list of words with ranking.
 Now you need to create a function that will take this list as input and provide a way so that a T9 keyboard
 can provide three top results of probable words based on rankings for the numbers punched in.
 Created by Felipe on 24/03/2015.
 */
class T9Keyboard extends Trie {

    @Override
    Node search(Object key) {
        def node = super.search(key)

        // if found
        if (node) {
           node.readData()
        }
        return node
    }

    /**
     * Returns the first three suggestion based on the string passed.
     */
    def suggestions(String word) {
        Node node = search(word)
        def suggestions = []
        if (node && !node.isLeaf()) {

            int i = 0;
            def it = node.queue.iterator() // iterator on descending rank order
//                for (int i = 0; i < 3 && i < node.children.size(); i++) {
            while (it.hasNext() && i<3) {
                Node suggestion = it.next();
                suggestions << suggestion.suggestion
                i++
            }
        }
        suggestions
    }

    static void main(String[] args) {

        def t = new T9Keyboard()
        t.add("trie")
        t.add("tree")
        t.add("i")
        t.add("it")
        t.add("ite")

        assertFound(t, "t")
        assertFound(t, "tr")
        assertFound(t,"tri")
        assertFound(t,"trie")
        assertFound(t,"tre")
        assertFound(t,"i")
        assertFound(t,"it")
        assertFound(t,"ite")

        assert null == t.search("triex")
        assert null == t.search("treexx")
        assert null == t.search("ix")

        assert t.suggestions("tr") == ['trie','tree']

        // increase tree rank
        assertFound(t,"tre")
        assertFound(t,"tre")
        assert t.suggestions("tr") == ['tree','trie']

        println "T9Keyboard test OK"
    }

    static def assertFound(def t, String key) {
        assert t.search(key)?.data == key
    }

}


package t9keyboard

/**
 * Created by Felipe on 28/03/2015.
 */
class Trie {

    /*root node with empty data*/
    def root = new Node(data:'')

    Node search(Object key) {
        def node = root
        def result = key.find {
            node = node.children[it]

            node == null
        }

        node
    }

    def add(key) {
        def node = root
        key.each {
            /*find the relevant child node*/
            def child = node.children[it]

            /*if child does not exist, creates it*/
            if (child == null) {
                child = node.addChild(it)
            }
            node = child
        }

        node
    }

}


package t9keyboard

import groovy.transform.EqualsAndHashCode

/**
 * Created by Felipe on 24/03/2015.
 */
@EqualsAndHashCode(includes = ['data'])
class Node {
    static Comparator rankComparator = [compare:{a,b->  b.rank <=> a.rank }] as Comparator

    // priority queue
    def queue = new PriorityQueue<Node>(30, rankComparator)

    /*data to be save*/
    def data

    /*child nodes of this node*/
    def children = [:]

    // frequency of data access
    private int rank = 0

    Node parent

    def readData() {
        // remove this node from parent's children
        if (parent.queue.remove(this)) {
            rank++
            parent.queue.add( this )
        }
        data
    }

    def isLeaf (){
        children.isEmpty()
    }

    def addChild(def key) {
        def child = children[key] = new Node(data: (data + key), parent: this)
        queue.add(child)
        child
    }

    String getSuggestion() {
        Node child = queue.peek()
        if (child) {
            child.suggestion
        } else
            data

    }
}

Here is the c++ version of solution.

I used the map to keep the dictionary and priority queue based on linked list to keep the top 3 frequent words.

Time complexity is as follows:
initialization: O(N Log N) due to the insert operation for map (it could be better O(N) if I use hash table)

search: O(N LogN) due to the search operation for std::map.

Any critics are welcomed.

#include<list>
#include<map>
#include<iostream>
#include<string>

using namespace std;

struct wordrank {
  string word;
  long rank;
  wordrank * next;
  wordrank(string s, int v):word(s), rank(v), next(0){}
};

class Dictionary{

public:

list<string> search(string key)
{
  list<string>result;
  wordrank * cur = 0;
  map<string, wordrank* >::iterator found;
  if ((found=dictionary.find(key))!= dictionary.end())
  {
    cur = found->second;
  }
  while (cur)
  {
    result.push_back(cur->word);
    cur = cur->next;
  }
  return result;
}

wordrank* add(wordrank *head, wordrank source)
{
  wordrank * new_word = new wordrank(source.word, source.rank);
  wordrank * cur = head;
  wordrank *prev = 0;
  int i = 0;
  while (cur)
  {
    if (new_word->word == cur->word)
      return head;

    if (new_word->rank > cur->rank)
	   {  
      if (prev) {
        prev->next = new_word;
      } else {
        head = new_word;
      }
      new_word->next = cur;
      break;
    }
    prev = cur;
    cur = cur->next;
  }
  if (!cur)
  {
    if (prev)  prev->next = new_word;
  }

  cur = head;
  while (cur)
  {
    if (i == 2)
    {
      cur->next = 0;
    }
    i++;
    cur = cur->next;
  }
  return head;
}

void generate_prefix(wordrank source, int len)
{
  string cur;

  for (int i = 0; i < source.word.length(); i++)
  {
    cur.push_back(source.word[i]);
    if (cur.length() == len)
    {
      if (dictionary.find(cur) != dictionary.end())
      {
        dictionary[cur] = add(dictionary[cur], source);
      }
      else {
        dictionary[cur] = new wordrank(source.word, source.rank);
      }
      cur.erase(0, 1);
 }
  }
}

void populate(wordrank source)
{
  string cur;
  for (int l = 1; l <=source.word.length(); l++)
  {
    generate_prefix(source, l);
  }

}

void initialize(wordrank * input, int len)
{
  for (int i = 0; i <len; i++)
  {
    populate(input[i]);
  }
}

private:
map<string,wordrank * > dictionary;

};

int main()
{
  wordrank input[10] = { wordrank("1231", 500), wordrank("1221", 60), wordrank("3312", 200), wordrank("5512", 1000),wordrank("6612", 102),wordrank("5121", 50),wordrank("9911", 100), wordrank("5533", 400), wordrank("987612", 800), wordrank("649320", 100)};

  Dictionary d;
  d.initialize(input, 10);
  bool exit = false;
  string in;
  while (!exit)
  {
    cout <<"enter search string (enter \"exit\" to end) : ";
    cin>> in;
    if (in == "exit")
    {
      exit = true;
      continue;
    }
    list<string> result = d.search(in);
    list<string>::iterator iter;
    for (iter = result.begin(); iter != result.end(); iter++)
      cout<< (*iter)<<endl;
    cout<<endl;
  }
  return 1;
}

W T F