## student student Interview Question for Students Students

• 0

Country: United States

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

You can use the dictionary data structure to store the words of the dictionary.

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

The question asks for searching all strings that have the prefix. Therefore, dictionary data structure would not work. A Trie is a good bet.

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

Yes a Trie is the best data structure here. Not sure why you would even consider a binary tree for this solution, unless it is just something to tinker with.

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

``````Node* construct_tree() {
// left means matching, right means not matching
Node* root = new Node("AP");
root->left = new Node("APP");
root->left->left = new Node("APPLE");
root->left->right = new Node("APE");
root->right = new Node("B");
root->right->left = new Node("BAB");
root->right->left->left = new Node("BABY");
root->right->left->right = new Node("BALL");
root->right->right = new Node("CAT");
}``````

``````vector<string> find_matches(string str, Node* root) {
Node* last = NULL;
Node* curr = root;
// Find the last matching node
while (curr) {
int min_len = min(str.length(), curr->str.length());
bool str_eq = str.substr(0, min_len).compare(0, curr->str.substr(min_len)) == 0;
bool too_long = str.length <= curr->str.length();
if (str_eq && too_long) { last = curr; break; }
else if (str_eq) { last = curr; curr = curr->left; }
else curr = curr->right;
}
// Now collect all the leaves under last
vector<string> matches;
queue<Node*> nodes;
nodes.push(last);
while (nodes.size() > 0) {
Node* n = nodes.pop();
if (!n->left && !n->right) matches.push_back(n->str);
if (n->left) nodes.push(n->left);
if (n->right) nodes.push(n->right);
}
return matches;
}``````

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

One should ask, will we necessarily have only 5 words. In that case I would use simple string matching
On the other hand, if the number of words are large, I will use a Trie.

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

i have to solve using trie.....
i have problem in that.....plz give me an example of it.....

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.