Amazon Interview Question
Software Engineer / DevelopersUse suffix trees. Another problem on a similar note.
how would you implement word completion on a telephone keypad ?
While generating a permutation of the string itself, check for the validity by using a prefix Tree(Trie).
How about having a hash table with keys as sorted letters combined to make a string, of the valid dictionary words and the value as all the possible words in the dictionary that fit into the group of letters which make up the key.
For eg --> Valid words like 'dog','god' will be values in a hash table entry with key as 'dgo' {sorted order of letters that make up the word}
This is precomputed, assuming we have access to the dictionary.
Now try checking for a word, which would essentially mean sorting all the letters of the word. Then basically it many involve performing a look up for the values for this key and print all the words in the value List.
Any opinions ?
One of the methods is to print all possible permutations of the string.
Implementation:
#include<bits/stdc++.h>
using namespace std;
void swap(char *x, char *y){
int temp = *x;
*x = *y;
*y = temp;
}
void printanagrams(char *str, int l, int r){
if(l == r)
cout<<str<<endl;
else{
for(int i = l; i <= r; i++){
swap((str+l), (str+i));
printanagrams(str, l+1, r);
swap((str+l), (str+i));
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
printanagrams(str, 0, n-1);
return 0;
}
isnt it same as finding all permutations of a string ?
- Anonymous November 11, 2008