Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

This can be solved two ways:

BFS solution using backtracking HashMap:

private static LinkedList<String> transformBFS(String start, String end, HashSet<String> dict) {
        LinkedList<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        Map<String, String> wordBackTrack = new HashMap<>();
        q.add(start);
        visited.add(start);
        while (!q.isEmpty()) {
            String currentWord = q.poll();
            for (String neighbour : getOneEditAwayWords(currentWord, dict)) {
                if (neighbour.equals(end)) {
                    LinkedList<String> path = new LinkedList<>();
                    path.add(neighbour);
                    while (currentWord != null) {
                        path.add(currentWord);
                        currentWord = wordBackTrack.get(currentWord);
                    }
                    return path;
                }
                if (!visited.contains(neighbour)) {
                    wordBackTrack.put(neighbour, currentWord);
                    q.add(neighbour);
                    visited.add(neighbour);
                }
            }
        }
        return null;
    }

    private static ArrayList<String> getOneEditAwayWords(String word, HashSet<String> dict) {
        ArrayList<String> oneEditAwayWords = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                String s = word.substring(0, i) + c + word.substring(i + 1);
                if (dict.contains(s))
                    oneEditAwayWords.add(s);
            }
        }
        return oneEditAwayWords;
    }

Or using recursive DFS, the benefit of this is that we can utilise the recursion stack to do the backtracking:

private static LinkedList<String> transformDFS(String start, String end, HashSet<String> dict) {
        return transformDFS(new HashSet<String>(), start, end, dict);
    }
    
    private static LinkedList<String> transformDFS(HashSet<String> visited, String start, String end, HashSet<String> dict) {
        if (start.equals(end)) {
            LinkedList<String> path = new LinkedList<>();
            path.add(end);
            return path;
        }

        if (visited.contains(start)) return null;

        visited.add(start);

        for (String v : getOneEditAwayWords(start, dict)) {
            LinkedList<String> path = transformDFS(visited, v, end, dict);
            if (path != null) {
                path.add(start);
                return path;
            }
        }

        return null;
    }

    private static ArrayList<String> getOneEditAwayWords(String word, HashSet<String> dict) {
        ArrayList<String> oneEditAwayWords = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                String s = word.substring(0, i) + c + word.substring(i + 1);
                if (dict.contains(s))
                    oneEditAwayWords.add(s);
            }
        }
        return oneEditAwayWords;
    }

- Coder May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is a graph problem.
Construction of graph involves, connecting all words that vary by a distance of one.
Then the problem is reachability from one vertex to another.

- deepanprabhu October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cycles will be generated, how do you deal with them?

- cdhsiung November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use BFS to find the shortest path from the start to the end.

- cdhsiung November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a python implementation. Assuming that the source word and destination word needn't be of the same size, transformation could involve (+) adding / (-) removing a character from the word for the transformation too.

Considering all the words in the dictionary to be nodes in a graph, process the whole dictionary once and create the graph. Then given two words initiate a BFS from source to destination and we'll have the shortest chain of transformations required.

In the worst case, we might have to traverse the whole graph to find a transformation or a transformation may not exist at all. This function returns the list / array of the transformation strings, using len(returnedArray) we can get the required result.

import os
import collections
import string

def constructGraph(dictionary):
	graph=collections.defaultdict(list)
	letters=string.lowercase
	for word in dictionary:
		for i in range(len(word)):
			remove=word[:i]+word[i+1:]
			if remove in dictionary:
				graph[word].append(remove)

			for char in letters:
				change=word[:i]+char+word[i+1:] 
				if change in dictionary and change!=word:
					graph[word].append(change) 

		for i in range(len(word)+1):
			for char in letters:
				add=word[:i]+char+word[i:]
				if add in dictionary:
					graph[word].append(add)

	return graph

def transformWord(graph, start, goal):
	paths=collections.deque([ [start] ])
	extended=set() 
	#Breadth First Search 
	while len(paths)!=0:
		currentPath=paths.popleft()
		currentWord=currentPath[-1]
		if currentWord==goal:
			return currentPath
		elif currentWord in extended:
			continue

		extended.add(currentWord)
		transforms=graph[currentWord]
		for word in transforms:
			if word not in currentPath:
				paths.append(currentPath[:]+[word])
	return []

dictionary = ['cat', 'bat', 'bet', 'bed', 'at', 'ad', 'ed', 'cat', 'cog', 'dog', 'cot'] #Complete dictionary passed here.
graph = constructGraph(dictionary) # Constructing the graph
print len(transformWord(graph, 'bat' , 'bed')) # Transform word and return []; find its length using len()
print len(transformWord(graph, 'bat' , 'cat'))
print len(transformWord(graph, 'cat' , 'bet'))
print len(transformWord(graph, 'cat' , 'dog'))
print len(transformWord(graph, 'bat' , 'hat'))

One problem with this is that if there's no transformation it returns an empty transformation list [ ] and the len([ ]) is 0, but rather has to be shown as null, a simple if statement would resolve this.

- Sudheesh Singanamalla October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I did not check for all the possibilities but here is the code in python. I am assuming a predefined dictionary is present.

def indict(word):
    diction = ['cat', 'bat', 'bet', 'bed', 'at', 'ad', 'ed', 'cat', 'cog', 'dog', 'cot']
    if word in diction:
        return True
    else:
        return False
    
def stepschange(word1, word2):
    if not (len(word1)!= len(word2)) and indict(word1) and indict(word2):
        breaking1 = [i for i in word1]
        counter =0
        for j in word2:
            if j in breaking1:
                counter = counter +1
        return 1+len(word1)-counter
    else:
        return 0

print stepschange('bat' , 'bed'),"11"
print stepschange('bat' , 'cat'),"11"
print stepschange('cat' , 'bet'),"11"
print stepschange('cat' , 'bog'),"11"

- revanthpobala October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Test
    public void testDictionary() {
        // Turn cat into dog
        dictionary.add("cat");
        dictionary.add("cot");
        dictionary.add("dot");
        dictionary.add("cog");
        dictionary.add("dog");

        convert("cat", "dog");

    }

    public static List<String> dictionary = new LinkedList<>();


    public String convert(String changing, String end) {
        if (changing.equals(end)) return end;

        int i = 0;

        for (char c : end.toCharArray()) {
            char[] changingArray = changing.toCharArray();

            if (changingArray[i] != c) {
                changingArray[i] = c;

                if (dictionary.contains(new String(changingArray))) {
                    System.out.println(new String(changingArray));
                    return convert(new String(changingArray), end);

                }
            }
            i++;

        }
        return "impossible";
    }

- Jody October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store the dictionary as a graph. Have it set up so that you have vertices with labels 1, 2, 3, etc (these represent the number of letters in the word). From each of these, create complete-subgraphs, where every node (representing a word) with n characters, is connected to every other node with n characters. Every edge from a node is given by the letter that is changed, and the position of that new character.

Assume your classes appear as follows:

public class Vertex {
    // Adjacency list, where the key is the index of the letter to change, and the value is
    // another map, where the key is the character to change, and the value is the 
    // vertex of the new word
    Hashmap<Integer, Hashmap<Character, Vertex>> adj = 
                        new Hashmap<Integer, Hashmap<Character, Vertex>>();
    String data;

    public Vertex getAdjacentVertex(int index, char letter) {
        if (!adj.containsKey(index)) 
            return null;
        return ajd.get(index).get(letter);
    }
}

Then you can find the number of steps it takes to get there with the following:

public Integer numSteps(Vertex word, String target) {
    if (word == null) return null;
    if word.data.equals(target) return 0;
    Map<Integer, Character> wordMap = new HashMap<Integer, Character>();
    for (int i = 0; i < target.length(); i++) {
        wordMap.put(i, target.charAt(i));
    }
    int numSteps = 0;
    while (!wordMap.empty() && !target.equals(word.data)) {
        Iterator<Integer> wordKeys = wordMap.keySet().iterator();
        boolean foundEdge = false;
        while (wordKeys.hasNext()) {
            Integer wordKey = wordKeys.next();
            if (word.getAdjacentVertex(wordKey, wordMap.get(wordKey)) != null) {
                word = word.getAdjacentVertex(wordKey, wordMap.get(wordKey));
                wordMap.remove(wordKey);
                foundEdge = true;
                numSteps++;
                break;
            }
        }
        if (!foundEdge) 
            return null;
    }
    return numSteps;
}

This solution would run in O(n) time, but use O(n^2) space.

- effy October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Solution with Dynamic programming, although, haven't even compiled, idea is like, if replacing one character results into a valid word in dictionary then its a similar sub-problem like what's the minimum iterations required from that point onwards.
findMinWays(string str)
{
	if (str == endWord) {
		return 0;
	}
	int min=MAX_INT, num=0;
	for (int i=0; i<str.length-1; i++) {
		if ( dict.exists( str.replace(i, endWord[i]) ) ) {
			
			num = findMinWays(str.replace(i, endWord[i]));
			if (num < min)
				min = num;
		}
	}
	if (min==MAX_INT)
		return 0;
	return min;
}

- JoyZombie October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do breath first search. Space required is upper bounded by dictionary size. Same for time if we consider inner two loops 'constant' because of 26 letters and maximum length word :)

import string
def dict_distance(dict, source_word, target_word):
    processed = {}
    horizon = {source_word:0}
    keep_going = True
    while keep_going:
        new_horizon = {}
        for key, value in horizon.iteritems():
            if key == target_word:
                return value
            else:
                processed[key] = value
                for char in string.ascii_lowercase:
                    for idx in range(0,len(key)):
                        new_word = key[:idx] + char + key[idx+1:]
                        if new_word in dict and new_word not in processed and new_word not in new_horizon:
                            new_horizon[new_word] = value + 1
        keep_going = len(new_horizon) > 0
        horizon = new_horizon
    return None

- rizTaak November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a minimum edit distance problem. see tutorials on youtube.

- angie November 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some people try to change one character from start[i] to end[i] at a time, and check if the the dictionary contains that word. It could be wrong in some cases for example, dictionary= [cut, cug, cog]

- jiahuang November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TransformWithDictionary {

    public static Integer getMinTransformations(String[] dictionary, String start, String end) {
        // Construct Map of words to a Set of their adjacent words in the dictionary
        Map<String, Set<String>> adjacent = new HashMap<>();
        for (String s : dictionary) {
            Set<String> adjacentWords = new HashSet<>();
            for (String s2 : dictionary) {
                if (s == s2) continue;
                if (isOneEditAway(s, s2)) adjacentWords.add(s2);
            }
            adjacent.put(s, adjacentWords);
        }

        return getMinTransformations(adjacent, start, end, null, 0);
    }

    /**
     * Checks if start can be transformed into end by changing no more than one letter
     */
    public static boolean isOneEditAway(String start, String end) {
        if (start == null || end == null) return false;
        int edits = 0;
        int index = 0;
        while (edits < 2 && index < end.length()) {
            if (start.charAt(index) != end.charAt(index)) edits++;
            index++;
        }
        return edits == 1;
    }

    public static Integer getMinTransformations(Map<String, Set<String>> dictionary, String start, String end,
                                                Integer min, int steps) {
        if (min != null && steps == min) return null; // This path is already longer than the min, just return null

        Set<String> adjacentWords = dictionary.get(start);
        if (adjacentWords == null) return null; // No adjacent words remaining, return null
        if (adjacentWords.contains(end)) return 1; // Base case

        // Remove the current word from dictionary to prevent an endless loop
        dictionary.remove(start);
        // Loop through adjacent words looking for min transformation steps
        for (String word : adjacentWords) {
            Integer result = getMinTransformations(dictionary, word, end, min, steps + 1);
            if (result != null) {
                min = min == null ? result + 1 : Math.min(min, result + 1);
            }
        }
        // Finally, return the minimum number of transformations we found
        return min;
    }

    public static void main(String[] args) {
        String[] dictionary = new String[] {
                "cat", "dog", "pog", "bog", "cot", "all", "yew", "nit", "cog", "raw", "sew", "mow", "saw", "was", "pam",
                "sam", "lit", "bit", "wit", "vim", "war", "rat", "mat", "log", "cow", "paw" };
        System.out.println("pog -> dog = " + getMinTransformations(dictionary, "pog", "dog")); // 1
        System.out.println("pam -> saw = " + getMinTransformations(dictionary, "pam", "saw")); // 2
        System.out.println("cat -> dog = " + getMinTransformations(dictionary, "cat", "dog")); // 3
        System.out.println("sam -> lit = " + getMinTransformations(dictionary, "sam", "lit")); // null
    }
}

- damien5314 November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

can you please explain how result gets updated each time?
Thanks!

- Ragav Krishna Ramakrishna December 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry for the fancy dictionary!

class WordTransform {

    static def dictionary = ["black", "browk", "brown", "blowk", "block", "white"]

    static void main(String... args) {
        println iterationsToTransform("brown", "black")
        println iterationsToTransform("white", "black")
    }

    static Integer iterationsToTransform(String from, String to) {
        if (from && to && from.length() == to.length()
            && dictionary.contains(to)) {
            int iterations = 0
            int index = 0
            while (!from.equals(to) && index < from.size()) {
                def word = tryToReplace(from, to, index++)
                if (word != from) {
                    iterations++
                    index = 0
                }
                from = word
            }
            if (from.equals(to))
                iterations
        }
        else null
    }

    static String tryToReplace(String from, String to, int index) {
        def word = from.replace(from.charAt(index), to.charAt(index))
        dictionary.contains(word) ? word : from
    }
}

- simona.valenti.0 December 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.

using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MinimumNumberOfTransformations {

    using Graph = Dictionary<string, HashSet<string>>;

    public static class WordsTransformer {

        //implements BFS
        public static string GetMinNumOfTransformations( string startWord, string endWord ) {

            // perform here all necessary checks: the words' lengths must be equal, etc...

            _startWord = startWord;
            _endWord = endWord;
            _graph = new Graph();
            _counter = 0;

            var frontier = new HashSet<string> { _startWord };

            while ( frontier.Count != 0 ) {

                _counter++;
                var tmpHashSet = new HashSet<string>();
                foreach ( var word in frontier ) {
                    
                    //add node
                    _graph.Add( word, new HashSet<string>() );                    
                    
                    //add its descendants
                    var res = AddDescendants( word );
                    
                    // if endWord is among descendants - return
                    if ( res != null ) { return res; }

                    tmpHashSet.UnionWith( _graph[ word ] );
                }
                frontier = tmpHashSet;
            }
            return null;
        }

        private static string AddDescendants( string word ) {

            for ( int i = 0; i < word.Length; i++ ) {

                var wordAsCharArr = word.ToCharArray();

                foreach ( var ch in Alphabet ) {
                    wordAsCharArr[ i ] = ch;
                    var newWord = wordAsCharArr.RestoreString();
                    AddNewWord( word, newWord );

                    // if endWord is among descendants of "word" - return
                    if ( newWord == _endWord ) {
                        return BuildUpPathAndNumOfSteps( word );
                    }
                }
            }
            return null;
        }

        private static string BuildUpPathAndNumOfSteps( string word ) {

            string path = word + "->" + _endWord;
            var curr = word;
            for ( int j = 0; j < _counter-1; j++ ) {
                var kvp = _graph.FirstOrDefault( x => x.Value.Contains( curr ) );
                curr = kvp.Key;
                path = curr + "->" + path;
            }
            return _counter + ", " + path;
        }

        private static void AddNewWord( string key, string newWord ) {
            if ( Dictionary.Contains( newWord ) &&
                !_graph.Values.Any( x => x.Contains( newWord ) ) && 
                  !_graph.Keys.Any( y => y.Contains( newWord ) ) )
            {
                _graph[ key ].Add( newWord );
            }
        }

        static string RestoreString( this IEnumerable<char> arr ) {
            var chArr = arr.ToArray();
            var sb = new StringBuilder();
            for( int i = 0; i < chArr.Length; i++ ) {
                sb.Append( chArr[ i ] );
            }
            return sb.ToString();
        }

        static readonly List<string> Dictionary = new List<string> {
            "cot","cog", "sat","sad","car","bar","bag","cab","rat","ray","say","cat", "dog", // etc...
            "cut", "cug"
        };

        static readonly List<char> Alphabet = new List<char> {
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','r','s','t','u','v','w','x','y','z'
        };

        private static string _startWord;
        private static string _endWord;
        private static Graph _graph;
        private static int _counter;
    }
}

- zr.roman December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

$dictionary = ['cap', 'cup', 'cod', 'fog', 'cut', 'hut', 'hot', 'hit', 'cat', 'cot', 'cog', 'dog'];
$results = search($dictionary, 'cat', 'dog');

var_dump($results);

/**
 * @param string[] $dictionary
 * @param string $start
 * @param string $end
 *
 * @return int|null
 */
function search(array $dictionary, $start, $end)
{
  $graph = prepareGraph($dictionary);
  $path[$start] = [$start];
  $queue[] = $start;
  
  while($queue) {
    $currentWord = current($queue);
    $currentPath = $path[$currentWord];
     
    if ($end === $currentWord) {
      return count($currentPath) - 1;
    }
    
    if (false === isset($graph[$currentWord])) {
      return null;
    }
    
    foreach($graph[$currentWord] as $nextWord) {    
      if (array_key_exists($nextWord, $path)) {
        continue;
      }
      
      $queue[] = $nextWord;
      $path[$nextWord] = array_merge($currentPath, [$nextWord]);
    }
    
    next($queue);
  }
}

/**
 * @param string[] $dictionary
 *
 * @return array
 */
function prepareGraph(array $dictionary)
{
  $dictionary = array_map('str_split', $dictionary);
  
  $result = [];
  foreach ($dictionary as $word1) {
    foreach ($dictionary as $word2) {
      if (1 === count(array_diff_assoc($word1, $word2))) {
        $result[implode('', $word1)][] = implode('', $word2);
      }
    }
  }
  
  return $result;
}

- abobola December 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript solution:

function getMinimumChanges(start, end, dictionary) {
    var matchingChars;
    var charsThatMatchEnd;
    var newWordindex;
    var newWordDistance;
    var currentWord = start;
    var count = 0;
    
    dictionary = dictionary.filter(function(val, index, array) {
        return getNumberOfMatchingChars(val, start) > 0 && getNumberOfMatchingChars(val, end) > 0;
    }); 

    // Add the end word to the dictionary
    dictionary.push(end);
    
    while (dictionary.length > 0 && currentWord !== end) {
        count ++;
        newWordCharsThatMatchEnd = 0;
        newWordindex = -1;

        dictionary.map(function (val, index) {
            matchingChars = getNumberOfMatchingChars(val, currentWord);
            if (matchingChars !== (start.length - 1)) {
                // More than 1 char away so we can't use this
                return;
            }
            // get the item closest to the end word from the dictionary
            charsThatMatchEnd = getNumberOfMatchingChars(val, end);
            if (charsThatMatchEnd > newWordCharsThatMatchEnd) {
                newWordCharsThatMatchEnd = charsThatMatchEnd;
                newWordindex = index;
            }
        });
        if (newWordindex === -1) {
            // There is no way to get to the end
            return null;
        }
        currentWord = dictionary[newWordindex];
        // remove the word from the dictionary so we don't get into a loop
        dictionary.splice(newWordindex, 1);
    }  
  
    function getNumberOfMatchingChars (first, second) {
        var i;
        var matchingIndex;
        var matchingChars = 0;

        for (i = 0; i < first.length; i++)  {
            matchingIndex = second.indexOf(first[i]);
            if (matchingIndex === -1) {
                continue;
            }
            matchingChars += 1;
        }

        return matchingChars;
    }

    return count;
}

- nabilgod January 15, 2017 | Flag Reply


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