Amazon Interview Question
SDE1sCountry: United States
class SuffixTree implements String_DB{
Node root;
ArrayList<String> search_result;
ArrayList<String> search(String s){
search_result = null;
Node current = root;
int index = 0;
outter : while (current.child.size() != 0){ // until we get to a leaf
char c = s.charAt(index); // what we are looking for right now
inner : for (int i = 0 ; i < current.child.size() ; i++){
if (current.child.get(i).c == c){
current = current.child.get(i);
index++;
break inner;
}
break outter;
}
}
search_result = new ArrayList<String>();
DFS-Visit(current);
return result;
}
void DFS-Visit(Node current , String so_far){
String so_far = so_far + current.c;
if (current.child.size() == 0){
search_result.add(so_far);
return;
}
for (int i = 0 ; i < current.child.size() ; i++)
DFS-Visit(current.child.get(i) , so_far);
return;
}
void insert(String str){
String s = str + "$";
for (int i = s.length - 1 ; i >= 0 ; i--)
insert_sub(s.subtring(i));
return;
}
void insert_sub(String s){
Node current = root;
int index = 0;
outter : while (current.child.size() != 0){ // until we get to a leaf
char c = s.charAt(index); // what we are looking for right now
inner : for (int i = 0 ; i < current.child.size() ; i++){
if (current.child.get(i).c == c){
current = current.child.get(i);
index++;
break inner;
}
break outter;
}
}
if (index == s.length() -1) // it's already in the trie
return;
while (index < s.length()){
Node new = new Node(s.charAt(index));
current.child.add(new);
current = new;
index++;
}
return;
}
class Node{
ArrayList<Node> child;
char c;
public Node(char c){
child = new ArrayList<Node>();
this.c = c;
}
}
}
You may also use KMP string matching algorithm , if the length of the list is O(m) and the length of each string is O(n) , this will take O(m * n) and the insertion takes O(1)
ArrayList<String> list = new ArrayList<String>();
ArrayList<String> search(String p){
ArrayList<String> result = new ArrayList<String>();
int[] func = prefix_function(p);
for (int i = 0 ; i < list.size() ; i++)
if (KMP(list.get(i) , p , func))
result.add(list.get(i));
return result;
}
int[] prefix_function(String P){
int q = 0;
int[] func = new int[P.length];
func[0] = 0;
for (int i = 1 ; i < P.length ; i++){
while (q > 0 && P[q] != P[i])
q = func[q];
if (P[q] == P[i])
q++;
func[i] = q;
}
return func;
}
boolean KMP(String T , String P , int[] func){
int q = 0;
for (int i = 0; i < T.length() ; i++){
while (q > 0 && T[i] != P[q])
q = func[q];
if (T[i] == P[q])
q++;
if (q == P.length)
return true;
}
return false;
}
trie datastructure
- pm June 08, 2013