Ebay Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
Looks good
Chintamani can you please elaborate your algo with a small example.
you can use a adjacency matrix to represent the graph.
Yep, that's good sol. Basically you have to construct the graph in a way that each world is connected with worlds which has only one latter different. Then do BFS or DFS.
The solution to this question is present in Cracking The Coding Interviews fifth edition, in the last chapter. The solution does not require pre-processing step, so there is no need to create a graph of the dictionary words. Complexity is O(nm) where n = length of start word and m = length of end word.
This can be solved using recursion
Please let me know if I have messed up somewhere here.
void FromTo(char *source, char *dest, char **stackofWords, int wordCount)
{
if(strcomp(source, dest) == 0)
{
print(stackofWords, wordcount);
return;
}
else
{
for(int i=0;i<strlen(source);i++)
{
for(int j=0;j<26;j++)
{
if((char)((int)'A' + j) != source[i])
source[i] = (char)((int)'A' + j);
else
continue;
stackofwords[wordcount] = source;
Fromto(source, dest, stackofWords, wordcount+1);
}
}
}
}
Algo
I am changing every letter with all the alphabets in the english dictionary and then comparing with the desitnation.
according to this algo we can replace the character, which is in dictionary but how we can know that if it is makes any meaningful word or not?
Oh yes I forgot to add that logic.
You can use with a simple check in the beginning to know. Use a trie for the dictionary.
We can solve by first creating graph which connects one word to another if only one letter difference. So after creation of this graph we can find two words and find the shortest path among them.
Here two way graph can be generated. If its one time work then we can create adhoc basis and find only words which are similar letters and draw graph..
else if its for longer term purpose we can draw graph for all the words in dictionary save it and at the time of finding we just need to find the shortest path. This may save a lot of time..
You can preprocess the dictionary and create this graph, should look like:
stack jack
| |
| |
smack back -- pack -- pick
You can then have a mapping from the word to the node representing the word, for this you can use a hash table, height balanced BST ...
Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS or DFS.
So you can summarize the algorithm as:
preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
Not possible to convert
else
n1 = get_node(w1)
n2 = get_node(w2)
if(path_exists(n1,n2))
Possible and nodes in the path represent intermediary words
else
Not possible
My solution by a BFS.
void doPath( vector<string> &path, map<string,string> &M, string s) {
if(s == "-")
return;
doPath(path, M, M[s]);
path.push_back(s);
}
vector<string> find(string &orig, string &dest, HashTable dic) {
queue<string> Q;
map<string,string> M;
Q.push(orig);
M[orig] = "-";
bool can = false;
while(Q.empty() == false) {
string top = Q.top();
Q.pop();
if(top == dest) {
can = true;
break;
}
for (int i = 0; i < top.size(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
string ss = top;
top[i] = c;
if(M.find(ss) == M.end()) {
Q.push(ss);
M[ss] = top;
}
}
}
}
vector<string> path;
if(can == false)
return path;
return doPath(path, M, dest);
}
public static boolean isValid(String word)
{
Set<String> dict = new HashSet<String>();
dict.add("cat");
dict.add("car");
dict.add("tar");
dict.add("tor");
dict.add("toy");
if (dict.contains(word))
return true;
return false;
}
public static void main(String[] args)
{
System.out.println(minTransforms(Arrays.asList(0, 1, 2), "cat", 0, "toy"));
}
public static int minTransforms(List<Integer> indxes, String word, int len, String dest)
{
if (word.equals(dest))
return len;
int lenT = Integer.MAX_VALUE;
for (int i=0;i<word.length();i++)
{
if(word.charAt(i)==dest.charAt(i))continue;
List<String> words = generateWords(i, word);
List<Integer> ind = new ArrayList<>(indxes);
for (String word_new: words)
{
if (!word_new.equals(word) && isValid(word_new))
{
//ind.remove(indx);
lenT = Math.min(minTransforms(ind, word_new, len + 1, dest), lenT);
}
}
}
return lenT;
}
public static List<String> generateWords(int indx, String word)
{
List<String> words = new ArrayList<String>();
char chr[] = word.toCharArray();
for (char a = 'a'; a <= 'z'; a++)
{
chr[indx] = a;
String str = new String(chr);
words.add(str);
}
return words;
}
You need to build a graph with an edge connecting two words which can be transformed to each other.
- Chintamani May 24, 2013Once, you build the graph, start from the starting words, check if the second word is connected to the first word. We can do a BFS if we want the shortest path as well.