Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
Right idea, but you'd do better with a heuristic than a simple BFS. See my comment below.
Seems like there has to be a faster way. Building a graph of all dictionary words, which are connected to those that differ by only one letter would take a really long time.
Sure the Dijkstra's algorithm afterwards would be relatively quick, but it would take a long time to build the graph in the first place.
I don't have another proposal, but it seems like there should be a faster solution.
General idea
bool CanNavigate(string& start_word, string& end_word, set<string> &dictionary)
{
queue<string> candidates;
candidates.push_back(start_word);
dictionary.erase(start_word);
while(candidates.empty() == false)
{
string nextword = candidates.top() ;
candidates.pop()
for(int i =0; i< nextword.size(); ++i)
{
// change every position from 'A' to 'Z'
string mutable = nextword;
for(int j=0; j<26; ++j)
{
mutable[i] = j+'A';
if(mutable == end_word)
return true;
if(!dictionary.exists(mutable)
continue; // no such word or already handled
dictionary.erase(mutable); // consider as handled
candidate.push(mutable);
}
}
}
}
To add on to this:
Construct a graph of all the words, with edges between words that can be transformed from one to the other.
Locate the start node, and use a heuristic to determine the next best node. If all nodes have the same score, do a breadth-first traversal to examine the neighbors, use the heuristic, rinse, repeat.
The simplest heuristic would be to examine how many letters are in the correct location for the final word; for instance:
cat -> dog
rat has a score of "0", because no letters are shared with dog
cot has a score of "1", because the "o" is in the right location, when compared to dog
cog has a score of "2", because both the "o" and "g" are correctly placed
Finally, "dog" is the end word.
You can use this in an A* path traversal, to traverse the graph. Faster and "better" than a simple breadth-first search
While definitely faster at getting to the final word, one of the stated requirements is to only change one letter at a time, so scoring has no benefit.
public class NavigationString {
public HashMap<Character,Integer> dic = new HashMap<Character,Integer>();
public NavigationString(HashMap<Character,Integer>dic){
this.dic = dic;
}
public String isNavigate(String str1,String str2){
StringBuilder sb = new StringBuilder(str1);
if(str1.length() != str1.length()){
return "Not Possible";
}
for(int i=str1.length()-1;i>=0;i--){
if(checkDic(str1.charAt(i)) && checkDic(str2.charAt(i))){
if(str2.charAt(i) == str1.charAt(i)){
continue;
}
sb.setCharAt(i,str2.charAt(i));
System.out.println("-> "+sb);
}else{
return "Not Possible";
}
}
return "Possible";
}
public boolean checkDic(Character c){
if(dic.get(c) != null && dic.get(c) == 1){
return true;
}
return false;
}
public static void main(String args[]){
HashMap<Character,Integer>map = new HashMap<Character, Integer>();
map.put('f',1);
map.put('e',1);
map.put('l',1);
map.put('t',1);
map.put('p',1);
NavigationString obj = new NavigationString(map);
System.out.println(obj.isNavigate("feel", "pelt"));
}
}
I would use graph to solve this problem.
The dictionary of valid words is given.
1) Construct the graph where each node represents a word from the dictionary. Connect a words which differ only by one letter.
2) Find the shortest path between str1 and str2. If path not exists print error msg.
Form a graph of words in the dictionary (two words adjacent if you can get from one to another in one step).
- Anonymous April 03, 2014Then do BFS starting with given string.