Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

A modified version of levenshtein distance should do.

- Ashutosh December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the input in levenshtein algo is two words. and output is distance.

This is a different problem altogether.
how about

for (index= 0; index < strlen(input_string); index++)
{
 for (char ch = 'a', ch < 'z', ch++)
   {
      if (lookup_dictionary( swap (inut_string[index], ch) ))
      add the word to output list
  }
}

- Amit Priyadarshi December 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@amit
I dont think we have to iterate through all the characters. We have initial and final word. Find the indices of the characters which are different in initial and final word. Then just iterate through those character indices

- Anonymous December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

build a graph starting from the initial word and use the dijkstra's algo to find the shortest path

- Anonymous December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the graph here will be a huge huge graph, the interviewer on my replies seemed worried about generation of such a graph !

- perlscar December 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

just do simple BFS

- Anonymous December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A node here could have more then 2 childs (the initial word will generally contain more then 2 chars), that's why we must use agraph instead of binary tree

- Anonymous December 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we create a tree for all the dictionary words and then for initial and final word length , just look for paths till that height and then we can go node by node for intermediate steps..

- Abhinav December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use HashMap<Integer,Set<Word>> where key is the length of the word..
get the Set<Word> for the given length and use a function

boolean isWord(String input)
      {
                     // which returns true if a word which differs by one character exists and also not visited before..
                   // this process repeated till we reach the target word or null... 
      }

- cobra December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Edit distance is the answer i guess ....... using DP.

- vK December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a graph of words same length using the dictionary. Each word will be a node. Words are connected (weight of connecting edge) by number of dissimilar characters. Now, use the shortest path algorithm to move along the lines of weight one to the target word. If we can't reach target word, there is no solution.

- Venki December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first check which character position is changed. prepare hash table with chaining for all possible valid dictionary word with one character changed. for example, boy -> toy then keep toy in hash table at position 1. Now hash the table according to which character position is changed and look for the word. Before doing hashing, we should check how many characters are changed using EXOR operation for each character. If there are two changes then we will just return.

- Punit December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <conio.h>
#include <string>
using namespace std;

/*
Example: input: cat,target: dog, paths:cat->cot->dot->dog or cat->cot->cog->dog
assume cot,cog to be valid words 
*/

bool validWord(string s){
	if(s == "cog" || s == "cot"  || s == "dot" || s == "dog")	return true;
	
	return false;
}

int printTransformation(string input,string target,string print){
	
	for(int i=0;i<input.length();i++){
		char tmp = input[i];	
		for(int j='a';j<='z';j++){
			input[i] = (char) j;
			if(validWord(input) && print.find(input) ==string::npos){
				print = print+"->"+input;
				if(input != target){
					printTransformation(input,target,print);
				}
				if(input == target){
					cout<<"\n Path "<<print;
					return 0;	
				}
				print = print.substr(0,print.length()-input.length()-2);
			}
		}
		input[i] = tmp;
	}
}

int main()
{
	string str1,str2,str3;
	cout<<"\n enter the input string: ";
	cin>>str1;
	cout<<"\n enter the target string: ";
	cin>>str2;
    str3 = str1;
	
	printTransformation(str1,str2,str3);
	
  getch();
  return 0;
}

- badshah December 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am a bit confused about the question itself.
Should the program tell how many intermediate steps are there or illustrate the steps in detail ?
function_name("TAP", "TOP") => 1
function_name("TAP", "PAN") => 2
function_name("TAP", "PIT") => 3

Can anybody put a sample output ?

- krshnaprsad December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think like as follows:
Is there a path from RUN to SUM
RUN -> SUN(valid dictionary word) -> SUM (valid dictionary word) with distance = 2

- BoredCoder December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool can_convert(char* first, char* second)
{
 bit_set different = get_diff(first, second);
 if(different.enabled.count <= 1)
  return true;
  
  for(int index = 0 ; index < different.size(); ++index)
  {
    if(different[index])
    {
       string next = first;
       next[index] = second[index];
       if(is_valid_word(next) && can_convert(next, second))
         return true;       
    }
  }

bit_set get_diff(string& first, string% second)
{
bit_set diff(first.size);
assert(first.size == second.size);
for(int index = 0 ; index < first.size ; ++index)
{
 diff[index ] = first[index] == second[index];
}
return diff;

}

- anon_dog December 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic: We can just do BFS here. Generating all possible words at a distance 1 from the current word. Store all the paths once you reach the destination.

If you want the shortest path. U can just return a single list of string tracking the size of list and updating it if you find smaller length string.

private static List<List<String>> convert(String source, String destination) {
        Map<String, String> validAndInvalidPaths = new HashMap<String, String>();
        Set<String> visited = new HashSet<String>();
        
        Queue<String>  queue = new LinkedBlockingDeque<String>();
        queue.add(source);
        visited.add(source);
        List<List<String>> allValidPaths = new ArrayList<List<String>>();
        
        while(!queue.isEmpty()){
        
            String word = queue.poll();
            
            Set<String> oneDistanceWords = getAllPossibleWordsAtDistanceOne(source);
            
            for(String candidateWord : oneDistanceWords){
                
                if( candidateWord.equals(destination)) { // Found One Path
                    validAndInvalidPaths.put(candidateWord, word);
                    String tempWord = candidateWord;
                    List<String> setOfWords = new ArrayList<String>();
                    
                    while(!tempWord.equals(source)){
                        tempWord = validAndInvalidPaths.get(tempWord);
                        setOfWords.add(tempWord);
                    }
                    setOfWords.add(source);
                    allValidPaths.add(setOfWords);
                    
                } else if (isInDictionary(candidateWord) && !visited.contains(candidateWord)) {
                    validAndInvalidPaths.put(candidateWord, word);
                    visited.add(candidateWord);
                    queue.add(candidateWord);
                }
            }
            
        }
        return allValidPaths;
    }

- Akshat January 05, 2013 | 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