Snap Interview Question: Given two words (beginWord an... | Glassdoor

Interview Question

Software Engineer Interview San Francisco, CA

Given two words (beginWord and endWord), and a dictionary's

  word list, find the length of shortest transformation sequence from beginWord to endWord, such that: 1.Only one letter can be changed at a time 2.Each intermediate word must exist in the word list
Answer

Interview Answer

2 Answers

1

Using BFS, Loop through 'a' to 'z' to replace each char of the neighbors word then check if it matches wordList.If so, add it into queue.count the level and return the level when you find a word which equals to the endWord.
here is my solution code:
    public int ladderLength(String beginWord, String endWord, Set wordList) {
        Queue q = new LinkedList();
        int level = 1;
        q.offer(beginWord);
        int cnt = q.size();
        while(!q.isEmpty()){
            String tmp = q.poll();
            cnt--;
            char[] cArr = tmp.toCharArray();
            for(int i = 0; i < cArr.length; i++){
                for(char c = 'a'; c <= 'z'; c++){
                    cArr[i] = c;
                    String str = new String(cArr);
                    if(str.equals(endWord)){
                        return level + 1;
                    }
                    if(wordList.contains(str)){
                        wordList.remove(str);
                        q.offer(str);
                    }
                }
                cArr[i] = tmp.charAt(i);
            }
            if(cnt == 0){
                cnt = q.size();
                level++;
            }
        }
        return 0;
    }

Interview Candidate on Jun 8, 2016
0

Assumes "beginWord" and "endWord" are the same length "wordLen". Finds all possible combinations of words that are 1,2,...,wordLen away for both beginWord and endWord and calls them "comb1" and "comb2" respectively (ex: if begin word is "now", Combo1 is made of 3 lists each consisting of words that are 1,2, and 3 changes respectively away from now like [[not, new, tow, cow, etc....], [nut, nap, bot, cot, etc... ], [lab, dad, rid, cat, etc... ] ]). Goes through both the combo sets and finds the intersection with the smallest number of transformations then returns the number of transformations.

main method -> runs tests
getTransLen -> compares array of arrays comb1 and comb2 to find smallest intersection
getTransformations -> returns an array of arrays of words in dict that are 1,2,...,wordLen different from the word given
                                    (ex: for "now", [ [not, new, tow, cow, etc....], [nut, nap, bot, cot, etc... ], [lab, dad, rid, cat, etc... ] ])

words.txt downloaded from:
https://raw.githubusercontent.com/dwyl/english-words/master/words.txt

==========================================

import java.util.*;
import java.lang.*;
import java.io.*;

public class SnapchatQ1 {

    public static void main(String args[]) {
        ArrayList dictList = new ArrayList();
        try {
            BufferedReader br = new BufferedReader(
                                    new InputStreamReader(
                                        new FileInputStream("words.txt")));
            try {
                String line;
                while ((line = br.readLine()) != null) {
                    dictList.add(line);
                }
            } finally {
                br.close();
            }
        } catch (Exception e) {

        }

        Set dictSet = new HashSet(dictList);
        int answer1 = getTransLen("not", "new", dictSet);
        System.out.println("Answer 1 - Expected: 3 Received " + answer1);
        int answer2 = getTransLen("cold", "tell", dictSet);
        System.out.println("Answer 2 - Expected: 4 Received " + answer2);
        int answer3 = getTransLen("smile", "speak", dictSet);
        System.out.println("Answer 3 - Expected: 5 Received " + answer3);
    }

    public static int getTransLen(String beginWord, String endWord, Set wordList) {
        ArrayList comb1 = getTransformations(beginWord, wordList);
        ArrayList comb2 = getTransformations(endWord, wordList);
        int smallNum = -1;
        for (int i = comb2.size() - 1; i >= 0; i--) {
            for (int j = 0; j ) comb2.get(i)) {
                    if (((ArrayList)comb1.get(j)).contains(currWord)) {
                        int newNum = i + j + 1;
                        if (newNum wordList) {
        int wordLen = word.length();
        ArrayList toReturn = new ArrayList();
        for (int i = 0; i ());
        }
        for (String compWord : wordList) {
            if (compWord.length() == wordLen) {
                int diffNum = 0;
                for (int i = 0; i ) toReturn.get(diffNum)).add(compWord);
            }
        }
        return toReturn;
    }
}

==========================================

Possibly Faster Answer on Dec 4, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.