## Amazon Interview Question for SDE-2s

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 3 vote

Form a graph of words in the dictionary (two words adjacent if you can get from one to another in one step).

Then do BFS starting with given string.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Right idea, but you'd do better with a heuristic than a simple BFS. See my comment below.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Levenshtein distance: en.wikipedia.org/wiki/Levenshtein_distance‎

Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
}
}

}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

It has benifit, instead of jumping from cot to bot, you will jump to better scoring word like cog which would lead to dog faster.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class NavigationString {

public HashMap<Character,Integer> dic = new HashMap<Character,Integer>();

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);

System.out.println(obj.isNavigate("feel", "pelt"));

}

}``````

Comment hidden because of low score. Click to expand.
-2
of 4 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.