Ebay Interview Question
Member Technical StaffsCountry: United States
Interview Type: Phone Interview
I think Trie Data Structure should work here.
Source : Wikipedia
Insert
=======
algorithm insert(root : node, s : string, value : any):
node = root
i = 0
n = length(s)
while i < n:
if node.child(s[i]) != nil:
node = node.child(s[i])
i = i + 1
else:
break
(* append new nodes, if necessary *)
while i < n:
node.child(s[i]) = new node
node = node.child(s[i])
i = i + 1
node.value = value
Output all keys in the trie by means of pre-order traversal, which results in output that is in lexicographically increasing order
I'm thinking :
- greenwizard April 17, 2014An array (array is not part of Collections) to store all the terms. Keep the array sorted.
An array of linked lists to store the definition. Each term is mapped to an index in the array which stores a linked list of its definitions. To do the mapping, you can device a hash function.