CareerCup

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.

Trie.

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.

We can use Btree.

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