Linkedin Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: In-Person
Preprocessing Step: Basically the dictionary of words is converted into multiple graphs. Each graph is constructed from words of particular size. The graph nodes have an edge if their edit distance (only replacement) is 1. Once you constructed this graph, then the problem is simple. Shortest path from given node to destination node. You can use BFS. The graph is undirected.
Use a bloom filter and force a swap for each character in the string.
If none of them form words, begin with the first character and do a random swap until a word is formed (if any), continue with the second character. And so forth. At each step try to naively switch the characters to save time.
Building up a graph dynamically and returning when target word is found
{
Queue<Tuple<string,int>> grph = new Queue<Tuple<string,int>>();
HashSet<string> words = new HashSet<string>() {"cat","bat","bet","bot","bog","dog","cot","dot","dog"};
HashSet<string> visited = new HashSet<string>();
string allEnglishCharacters = "abcdefghijklmnopqrstuvwxyz";
string start = Console.ReadLine();
string end = Console.ReadLine();
grph.Enqueue( new Tuple<string,int>( start, 1 ));
int level = -1;
while(grph.Count > 0)
{
var target = grph.Dequeue();
string src = target.Item1;
for ( int i = 0; i < src.Length; i++ )
{
foreach(char c in allEnglishCharacters)
{
string res = src.Substring( 0, i ) + c + src.Substring( i+1 );
//Optimization to reduce unnecessary checks
if ( visited.Contains( res ) )
{
continue;
}
else
{
visited.Add( res );
}
// if target word found exit
if ( res == end )
{
level = target.Item2 + 1;
break;
}
// if found in dictionary add
if(words.Contains(res))
{
grph.Enqueue(new Tuple<string,int> (res, target.Item2 + 1 ));
}
}
if ( level != -1 )
break;
}
if ( level != -1 )
break;
}
Console.WriteLine( level );
}
how can you know which words are "valid dictionary words", are you provided a list of valid words?
Lets start with all possible children nodes for cat and make a tree out of it with maintaning parent pointer.
Keep track of the already existing parent words and don't repeat in children. Maintain this in a hashset.
For example:
cat - {(bat, eat, fat, hat, mat, oat, pat, rat, sat, tat), (cot, cut), (cab, cad, cam, can, cap, car)}
Now for each of these words, get all possible valid words which we have not seen before. Add these words to the hashset.
So you will be building a big tree with all unique nodes with 3 letter words
As soon as you see dog, just stop and trace to the parent to the root and count the number of levels. Or we can maintain level info for each node.
int findPathLength(String start, String end){
// put start in queue
// put all the children of start in a queue
ObjectLevel o = new ObjectLevel(start, 0);
Queue<ObjectLevel> q= new LinkedList<ObjectLevel>
q.enque(o);
HashSet<ObjectLevel> allWords = new HashSet<ObjectLevel>();
while (!q.isEmpty()){
// find the valid words children and add
ObjectLevel a= q.dequeue();
boolean isEnd = getValidChildren(a, end, Set<ObjectLevel> s);
if(isEnd) {
return a.level + 1;
}
s.removeAll(allWords);
enqueSet(q, s);
allWords.addAll(s);
}
}
boolean getValidChildren(ObjectLevel a, String end, Set<ObjectLevel>){
// Get all valid permutations of the a.text and check isValidWord against it
…
//check if the children contain the end word
if(children.contains(end))
return true;
}
class ObjectLevel {
String text;
int level;
ObjectLevel(String t, int l){
this.text = t;
this.level =l;
}
}
setup a DAG and use bfs to from the shortest path
- Scott September 23, 2015