## Google student Interview Question for Students

• 0

Country: United States
Interview Type: Phone Interview

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

A trie is the obvious answer, but there's this bizarre stipulation to use a binary tree (note: not necessarily a BST).

Normally 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.

Comment hidden because of low score. Click to expand.
0

Nice solution

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

Could you please give an example

Comment hidden because of low score. Click to expand.
0

How would we retireve .. suppose we have 11000111 as a binary representation for a particular string , then even if we trie it , won't it be difficult to get the word to which this string belongs ?

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

Trie.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Could you provide an implementation for this one?

Comment hidden because of low score. Click to expand.
0

i want the implementation of binary tree in java for this problem

Comment hidden because of low score. Click to expand.
0

Making BST is not a problem. Problem is fetching valid word back from BST.

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

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?

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

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

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

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.

Comment hidden because of low score. Click to expand.
0

5 words is just a simplification of a larger problem. A trivial solution will not suffice when problem set expands.

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

We can use Btree.

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

This is simple:
a) Find prefix set for each word in dictionary. Ex...for CAT => {C, CA, CAT}
b) Merge all the sets and then sort them in dictionary order.
c) Create a balanced binary tree from this array
d) Any lookup will take log n

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.

### 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.