Google student Interview Question
StudentsCountry: United States
Interview Type: Phone Interview
Building a trie out of the contents of the dictionary seems to solve the problem. Since the question states that a binary search tree needs to be utilized, it seems we will need to build a balanced binary search tree out of dictionary data. The dictionary is typically presented in sorted order (e.g. look at /usr/dict/words or /usr/share/dict/words in some systems). The BST can be built recursively by looking at the middle element and then building the left and right halves.
I think for this particular question is to sort strings in dictionary and then use binary search to find the input string at prefix of some words. Of course, as ogzd said, we can use trie to get best solution with O(n) time, where n is the number of letters in all words. But in this question, I think they are asking something about binary search. Am I thinking right?
Here is the general outline for a DFS
Build a tree with the supplied words
Make a stack s
s.push(root of the tree)
bool found = false;
while (s.isEmpty == false) {
node = s.pop();
if (node.data.startsWith("foo") || node.data.compareTo("foo") == 0) { // let foo be the string we are checking
found = true;
print(node.data);
s.push(node.left);
s.push(node.right);
}
else if (found == false && node.data.compareTo("foo") > 0) { // "foo" < node.data
s.push(node.left);
}
else if (found == false && node.data.compareTo("foo") < 0 { // "foo" > node.data
s.push(node.right);
}
}
Here is the general outline for a BFS
Build a tree with the supplied words
Make a queue q
q.enqueue(root of the tree)
bool found = false;
while (q.isEmpty == false) {
node = q.dequeue();
if (node.data.startsWith("foo") || node.data.compareTo("foo") == 0) { // let foo be the string we are checking
found = true;
print(node.data);
q.enqueue(node.left);
q.enqueue(node.right);
}
else if (found == false && node.data.compareTo("foo") > 0) { // "foo" < node.data
q.enqueue(node.left);
}
else if (found == false && node.data.compareTo("foo") < 0 { // "foo" > node.data
q.enqueue(node.right);
}
}
I don't quite understand this problem. If there are only five 5 words in the dictionary and the words are fixed. For each input string, simply compare it with all 5 words and find if it is a prefix of any. The cost will be constant.
A trie is the obvious answer, but there's this bizarre stipulation to use a binary tree (note: not necessarily a BST).
- fwiffo October 17, 2012Normally a trie would have one child node for each possible next character. For example, the root node would have children for 'A', 'B', and 'C', because those are the possible starting characters of our set of strings.
So instead, we can build a binary trie by using the binary representations of the strings.