Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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
}
}
build a graph starting from the initial word and use the dijkstra's algo to find the shortest path
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...
}
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.
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.
#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;
}
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 ?
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;
}
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;
}
A modified version of levenshtein distance should do.
- Ashutosh December 18, 2012