Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
	}
}

- Sumeet Singhal January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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))

- Darkhan.Imangaliev January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
		}
		
	}
	
	
}

- Rohan February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Nelson Perez March 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }
}

- fop.net March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hankm2004 August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

W T F

- WTF January 17, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More