## Linkedin Interview Question

Country: United States
Interview Type: In-Person

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

There are two ways to approach the problem(code in C#) -
1.) One way BFS
a.) Create a class to store word and the level of the word from the root.
b.) Maintain a queue of the above class to do BFS.
c.) loop until queue is not empty
d.) For each char replace it with 26 possible chars and check if it exists in dictionary
e.) if found return the level.

``````public class WordNode
{
public string word;
public int numsteps;

public WordNode(string word, int numsteps)
{
this.word = word;
this.numsteps = numsteps;
}
}
public int LadderLength(string beginWord, string endWord, ISet<string> wordList) {
if(beginWord ==null || endWord ==null)
return 0;
if(beginWord.Length != endWord.Length)
return 0;
if(beginWord.Length ==1)
return 2;
if(!wordList.Contains(beginWord) || !wordList.Contains(endWord))
return 0;

int maxCount=Int32.MaxValue;
Queue<WordNode> myq = new Queue<WordNode>();
myq.Enqueue(new WordNode(beginWord,1));

while(myq.Count!=0)
{

WordNode top = myq.Dequeue();
if(top.word.Equals(endWord) && maxCount> top.numsteps)
maxCount = top.numsteps;
char [] ch = top.word.ToCharArray();
for(int i =0; i < ch.Length; i++)
{
for(char c = 'a'; c<='z'; c++)
{
char temp = ch[i];
ch[i]=c;
String s = new string(ch);
if(wordList.Contains(s))
{
myq.Enqueue(new WordNode(s, top.numsteps +1));
if(!top.word.Equals(endWord))
wordList.Remove(s);
}
ch[i]=temp;
}
}

}
return maxCount== Int32.MaxValue ? 0 : maxCount;
}``````

2. Biderectional BFS -
a.) In previous solution as we go deeper , the number of words to loop will increase exponentially.
b.) if we consider end word as begin word , we could repeat the same step to find the soultion.
c.) Therefore , if we start from both end and eventually check if we found intermediate target list of words which can eventually form the end word in end list.
d.) Since we are using HashSet , We can save time for lopping through each word at deeper levels.

``````//Two way BFS solution faster than single side BFS
public int LadderLength(string beginWord, string endWord, ISet<string> wordList) {
if(beginWord ==null || endWord==null ||wordList==null)
return 0;
if(beginWord.Length != endWord.Length)
return 0;
HashSet<string> beginSet = new HashSet<string>();
HashSet<string> endSet = new HashSet<string>();
int level=1;

HashSet<string> visited = new HashSet<string>();
while(beginSet.Count!=0 && endSet.Count!=0)
{
//Store next level child element which are one character different
HashSet<string> temp = new HashSet<string>();

if(beginSet.Count > endSet.Count)
{
HashSet<string> swap = endSet;
endSet = beginSet;
beginSet = swap;
}

foreach( var s in beginSet)
{
char[] ch = s.ToCharArray();
for(int i = 0; i < ch.Length; i++)
{
char old = ch[i];
for(char c ='a'; c<= 'z'; c++)
{
if(c!=old)
ch[i]=c;

string target = new string(ch);
if(endSet.Contains(target))
return level+1;

if(!visited.Contains(target)&& wordList.Contains(target))
{
}

ch[i]=old;
}
}
}
beginSet=temp;
level++;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You could do birectional BFS, cutting runtime by a factor of 2 -> O (2^n/2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is'nt this problem same as edit distance, for edit distance there is dynamic programming solution available.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.

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.

### 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.