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;
        beginSet.Add(beginWord);
        endSet.Add(endWord);
        
        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))
                        {
                            temp.Add(target);
                            visited.Add(target);
                        }
                        
                        ch[i]=old;
                    }
                }
            }
            beginSet=temp;
            level++;
        }
        
        return 0;
    }

- agarwalanshul1987 May 22, 2016 | Flag Reply
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)

- Sam December 06, 2015 | Flag Reply
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.

- Balaji December 07, 2015 | Flag Reply
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.


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