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.

- Anonymous April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rotinom April 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- static416 April 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- tracer April 03, 2014 | Flag Reply
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);
             }
        }
        
     
   }
}

- Mithya April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- rotinom April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- static416 April 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rams April 14, 2014 | Flag
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>();

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

    }

}

- Anonymous April 04, 2014 | Flag Reply
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.

- thelineofcode April 03, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More