Google Interview Question for Site Reliability Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 8 vote

pre-process the entire dictionary and form a graph. Now start from the first word (source node) and do Breadth first search and you will get the shortest path from the source word to the target word.

- rkt September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh sorry, didn't notice this, and posted a similar answer.

- Loler September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry once again!! LOL

- Loler September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One of the worst solution. LOL

- Loler October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Data Structure : stack s;
step1 :s<-push(DAMP)
step2: w<-pop(s)
if(w!=LIKE)
go to step3
else
return
step3: push all word which are in dictionary and can be get after changing at single place of w into stack if it is not present and it wasn't pushed earlier.
go to step 2

- ivikas007 October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Java Solution

Assuming the dictionary is a set of strings, make a HashSet<char[]> and implement a method to find the next change need that returns null if no possible change. Iterate through the char[] of the input, or you can also iterate while the char[] inputs are not equal.

public static List<String> getChanges(String first, String last, Set<String> dict) {
	Set<char[]> charDict = new HashSet<char[]>();
	for (String word : dict) {
	charDict.add( word.toCharArray() );
	}
	char[] from = first.toCharArray();
	char[] to = last.toCharArray();
	List<String> changes = new LinkedList<String>();
	while (! from.equals(to)) { //array equality
		changes.add(from.toString());
		from = next(from, to, dict);
		if (from == null)
			return null;
	}
	changes.add( to.toString() );
	return changes;
}

public static char[] next(char[] from, char[] to, Set<char[]> dict) {
	for (int i =0; i < to.length; i++) {
		if ( from[i] != to[i] ) {
			char temp = from[i];
			from[i] = to[i];
			if ( dict.contains(from) )
				return from;
			from[i] = temp;
		}
	}
	if (!from.equals(to))
		return null;
	else
		return to;
}

- derp October 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can't edit posts? Wow, well there are some simple errors in there such as

from = next(from, to, dict)

which should be

from = next(from, to, charDict)

I'm sure there is more, as I didn't put this through a compiler or anything, but you get the gist of things

- derp October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@derp: You can edit the posts if you login.

- Anonymous October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

OK, here is a solution using BFS.

Note that I abstracted away things like dictionary representation and getting all the words that differ from the given word in just one character. There are several different ways to implement these and there's no point polluting the solution with unnecessary detail. Plus a few people before me have code snippets that could be used for that.

If you are really going read this, I'd suggest to paste the code into Visual Studio (or your favorite editor that has syntax highlighting).

#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
// Hash table? Trie? BST? Your  choice :-)
class Dictionary
{
public:
    Dictionary(string path);
    ~Dictionary();
    // Generate the next word that differs from s only in s[position].
    // If there are no such words, s is returned.
    // Repeatedly calling this function will eventually return the 
    // string that we started with.
    // One possible implementation of this is to increment s[position] 
    // mod 26 until a word in the dictionary is found.
    const string & GetNextWord(string s, int position) const;
};


bool FindPath(
    const Dictionary * pDict,
    string start,
    string end,
    map<string, string> & mpCP)
{
    mpCP[start] = "";		// Put start in the map with empty parent
    queue<string> q;
    q.push(start);			// Enqueue start
    int length = start.size();
    //
    // Repeat until we found end or until no more words left
    while(!q.empty())
    {
        // Get the next word from the queue
        string word = q.front();
        q.pop();
        // Because of the early out below, this can only happen when start==end
        if (word == end)
            return true;
        //
        // Generate all possible children (that we have not seen before)
        // and put them in the queue
        for (int i = 0; i < length; ++i)
        {
            string s = word;
            while ((s = pDict->GetNextWord(s, i)) != word)
            {
                // We have already seen this word, do nothing
                if (mpCP.count(s) > 0)
                    continue;
                // We have not yet seen this word, let's add it
                // to the map (with its parent) and to the queue
                mpCP[s] = word;
                // Early out - we found our target!!!
                if (s == end)
                    return true;
                q.push(s);
            }
        }
    }
    return false;
}


// Print path (up to word end) using entries in the map
void PrintPath(const map<string, string> & mpCP, const string & end)
{
    string parent = mpCP.find(end)->second;
    if (parent != "")
    {
        PrintPath(mpCP, parent);
        cout << " -> " << end;
    }
}

int main()
{
    string start = "CAT";
    string end = "DOG";
    if (start.size() != end.size())
    {
        cout << "String lengths don't match, exiting ..." << endl;
        return 1;
    }
    Dictionary dict("FileWithAllWords.txt");
    map<string, string> mpChildParent;
    bool success = FindPath(&dict, end, -1, mpChildParent, q);
    if (success)
    {
        cout << "Path from " << start << " to " << end << " exists!" << endl;
        cout << start;
        PrintPath(mpChildParent, end);
    }
    else
    {
        cout << "Path from " << start << " to " << end << " does not exist!" << endl;
    }
    return 0;
}

- czpete425 November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Which data structure is used to maintain the dictionary? or the words in the dictionary are just stored in a file?

- vinodhian September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A trie

- code_monkey September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

From a graph out of the words, word A is adjacent to word B if replacing one character in one gives the other.

Now do a "double" breadth first search, starting a the source and the target. (i.e you start two independent BFS, one from source and one from target, stopping when they meet).

- Loler September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

From yur explanation i can get the distance between these two words , but how can i get all the legitimate words during the transformation?

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That path gives the set of words. (the words are vertices in the graph).

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the reply. if you have a link for the dictionary representation as graph, please post it.. i just wanted to see how the nodes are connected..

- Anonymous September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can also run Dijkstras algorithm. Seems simpler than doing 2 BFS

- Vikas October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Vikas, BFS is more quick, O(n), Dijkstra is O(n^2), because we don't need one node to all nodes, so BFS is enough

- remlostime October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@remlostime , in which world are you living , who told you BFS is O(n) buddy.
it is O(V+E) where E can be V^2 in worst case , so its n^2 only for a graph , for tree yes BFS is O(n)

- Geek January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_in_Dictionary(dic_word):
<CODE TO CHECK WHTHER THE WORD IS IN DICTIONARY>

def find_cloneWord(w1, w2):
for i in range(sw1)
sw1_d = sw1
for j in range(sw2):
sw2_d = sw2
sw2_d[j] = sw1_d[i]
dic_word = ''.join(sw2_d)
if is_in_Dictionary(dic_word) == 1:
print dic_word
num_words = num_words + 1
else:
print "No Word in Dictionary"



#Main Function
w1 = "DAMP"
w2 = "LIKE"

sw1 = w1.strip()
sw2 = w2.strip()
num_words = 0

- Dic September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Data Structure : stack s;
step1 :s<-push(DAMP)
step2: w<-pop(s)
if(w!=LIKE)
go to step3
else
return
step3: push all word which are in dictionary and can be get after changing at single place of w into stack if it is not present and it wasn't pushed earlier.
go to step 2

- ivikas007 October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

2 solutions. First approach is the most scalable one:
Approach 1:

Preprocessing step: Create a graph of all the words in the dictionary such there is an edge between word X to Y only when they differ by one character replacement only.
1. Find the source word in graph.
2. From the source node run a BFS to find the target node.

Approach 2:

1. Do a BFS, but this time you have to generate all posible states at each step, so there would be additional cost of looking up the word in the dictionary.
Time complexity= O(n^n)

- Epic_coder October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Epic_coder, could you explain approach 2 a bit more.

- Vikas October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well in 1st approach you would start from DAMP and generate following in the first step:
LAMP,DIMP,DAKP and DAME, and at the same time look up each of them in the dictionary, and proceed only with those nodes that exist in the dictionary.
While in approach 1 you already know what words could be obtained with one replacement exist, so you don't have to generate n combinations and don't have to lookup each of them in the dictionary at each step because you have direct nodes that you can follow.

- Epic_coder October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            string starttstr = "DAMP";
            string entstr = "LIKE";

            string path = "Dictionary.txt";
            

            try
            {
                var steps = GetSteps(starttstr, entstr, path);
                foreach (var step in steps) {
                    Console.Write("{0}->", step.ToUpper());
                }
                Console.Write("\b\b  \n");
            }
            catch (Exception ex)
            {
                
                Console.WriteLine(ex.Message);
            }
            
            Console.ReadKey();
        }


        
        /// <summary>
        /// Creating steps from starttstr to entstr and sherching this in dictionary file by path
        /// </summary>
        /// <param name="starttstr"></param>
        /// <param name="entstr"></param>
        /// <param name="path"></param>
        /// <returns></returns>
        private static IEnumerable<string> GetSteps(string starttstr, string entstr, string path)
        {
            if ( entstr == null )
            {
                throw new ArgumentNullException("entstr");
            }
            if ( starttstr == null )
            {
                throw new ArgumentNullException("starttstr");
            }
            if ( path == null )
            {
                throw new ArgumentNullException("path");
            }

            if ( starttstr.Length != entstr.Length )
            {
                throw new Exception("Start and End strings not equals by length");
            }
            string basestring = starttstr;
            var result = new List<string> {starttstr};
            while (entstr.ToUpper() != basestring.ToUpper())
            {
                var word = SearchWord(basestring,result,path);
                if (word != null)
                {

                    result.Add(word);
                    basestring = word;

                }
                else {
                    result.Add("Next step is not found");
                    return result;
                }
            }
            return result;
        }
        /// <summary>
        /// Searching first word in dictionary which has one different letter 
        /// </summary>
        /// <param name="basestring"></param>
        /// <param name="arraystr">latest founded strings</param>
        /// <param name="path">path to dictionary file</param>
        /// <returns>founded string or null if string is not found</returns>
        /// <exception cref="FileNotFoundException"></exception>
        private static string SearchWord( string basestring, IEnumerable<string> arraystr,string path )
        {
            if(!File.Exists(path))
            {
                throw new FileNotFoundException("Dictionary ia not found",path);
            }
            using (var reader = new StreamReader(path))
            {
                while (!reader.EndOfStream)
                {
                    var line = reader.ReadLine();

                    if ( !string.IsNullOrEmpty(line) )
                    {
                        if (CompareStrings(basestring, line) == 1 && arraystr.All(str=>str.ToUpper()!=line.ToUpper()))
                        {
                            return line;
                        }
                    }
                }
                return null;
            }
        }

        /// <summary>
        /// Compare two strings
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns>Quantity of differents betwen strings or -1 if strings have different length</returns>
        /// <exception cref="ArgumentNullException"></exception>
        static int CompareStrings(string str1, string str2)
        {
            if ( str1 == null )
            {
                throw new ArgumentNullException("str1");
            }
            if ( str2 == null )
            {
                throw new ArgumentNullException("str2");
            }
            if(str1.ToUpper()==str2.ToUpper())
            {
                return 0;
            }
            if(str1.Length!=str2.Length)
            {
                return -1;
            }

            var ar1 = str1.ToUpper().ToCharArray();
            var ar2 = str2.ToUpper().ToCharArray();
            int comparecounter=0 ;
            for (int i = 0; i < ar1.Count(); i++)
            {
                if(ar1[i]!=ar2[i])
                {
                    comparecounter++;
                }
            }
            return comparecounter;
        }

- Max October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

This is a DFS problem.

Form a graph of all the words in the dictionary. Each word will be a node, and there will be edges between two words which differ by a character only. Now start from the source string, and find all paths to the target string. DFS.

If the question was to find the shortest path to the target, you'd use BFS.

- Bruce Wayne November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you assume we have to find all the paths?

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question does not specify anything about the shortest path. It only asks us to find a path. There can be several such path. Hence, I said DFS. You could clarify this with the interviewer.

- Bruce Wayne November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you efficiently create this graph?

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you create separate trees based on the number of characters, it would optimize the solution. As per my understanding the number of characters in input and output has to be same...so creating separate trees would help.

- pratikrd November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's an implementation that does what I explained above. Exploring all paths. Maybe can be optimized further:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void print(vector<string> list)
{
        for(int i = 0; i<list.size(); i++)
                cout << list[i] << " ";

        cout << endl;
}

void findPath(string input, string output, vector<string> dict, vector<string> list)
{
        if(input == output)
        {
                list.push_back(output);
                print(list);
                return;
        }

        for(int i = 0; i< input.length(); i++)
        {

                for(int j = 0; j < 26; j++)
                {
                        char ch = 'a' + j;
                        if(input[i] != ch)
                        {
                                char temp = input[i];
                                input[i] = ch;

                                if(find(dict.begin(), dict.end(), input) != dict.end() && find(list.begin(), list.end(), input) == list.end())
                                {
                                        input[i] = temp;
                                        list.push_back(input);
                                        input[i] = ch;
                                        findPath(input, output, dict, list);
                                        input[i] = temp;
                                        list.pop_back();
                                }
                                else
                                {
                                        input[i] = temp;
                                }
                        }
                }
        }
}

int main(int argc, char **argv)
{
        int n;
        string input, output;
        getline(cin, input);
        getline(cin, output);

        string dummy;
        cin >> n;
        getline(cin, dummy);

        string word;
        vector<string> dict;

        for(int i =0; i<n; i++)
        {
                getline(cin,word);
                dict.push_back(word);
        }
        vector<string> list;
        findPath(input, output, dict, list);
}

- Bruce Wayne November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

^ Ignore the dummy vars, and other stuff, I just wrote this on top of something else I had lying around. But you get the idea.

- Bruce Wayne November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

The problem could be modeled as a graph traversal (DFS or BFS), but in my opinion it's going to be complicated to implement.

My solution instead is:

public static void findPath(String str, Dictionary dict, int pos, String dest, List<String> list) {

    if (str == null || dict == null) return;
    
    if (pos < 0 || pos >= str.size()) return;
    
    if (dest.equals(str)) print(list);
    
    for(Char ch : getChars()) {
        str = str.replace(pos, ch);
        if (!dict.contains(str)) continue;
        findPath(str, pos+1, dest, list.add(str);
    }
    
}

Essentially, given the starting string I explore sistematically all the valid paths.

- Claudio November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u explian ur approach plz

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't handle the case when the first change of the only solution is to change a character not in the first index or the character in a position needs to be changed multiple times during the conversion.

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting idea but it would not work for any of the examples provided. The only paths that it produces are the ones where the position of the character being changed is increasing which restricts the choices considerably.

- czpete425 November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

claudio can u explain ur code plz

- Anonymous November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need count and changed?

- code_monkey November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
                const int strlength = 100;
                char sourceStr [strlength] = {'\0'};
                char destStr [strlength] = {'\0'};
                int nStr = 0;
                char temp;

                bool fRestart = true; // variable to be checked at the end of loop to see whether rerun is required

                cout <<"\nEnter source sring: ";
                cin >> sourceStr;
                cout <<"\nEnter destination sring: ";
                cin >> destStr;

                nStr = strlen(sourceStr);

                cout << "\nString Conversion Process: " << sourceStr;
                

                while (fRestart)
                {
                    fRestart = false;

                    for (int i = 0; i < nStr; i++)
                    {
                        temp = sourceStr[i];
                        if (sourceStr[i] != destStr[i])
                        {
                            sourceStr[i] = destStr[i];

                            if (false == isValidWord(sourceStr))   // isvalid checks dictionary, if the wor is valid
                            {
                                sourceStr[i] = temp;
                                fRestart = true;
                            }
                            else
                            {
                                cout << " -> " << sourceStr;
                            }
                        }
                    }
                };


            }

- Gupt November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't handle the case when the first change of the only solution is to change one of the characters in source string to a character different to the character in the same position in destined string.

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I believe this would work

int tbool=0,i=0,changed=0,count=0;
	
	if(strlen(src)==strlen(dest))
	{
		int len=strlen(src);
		char* str=new char[len];
		int* modified=new int[strlen(src)];
		count=2*len;
		for(i=0;i<len;i++)
		{
			modified[i]=0;
		}
		//Changing the source
		strcpy(str,src);
		while(strcmp(str,dest)&& count>0)
		{
			for(i=0;i<len;i++)
			{
				if(src[i]!=dest[i]&& modified[i]!=1 )
				{
					str[i]=dest[i];
					if(dic.find(str))
					{
						modified[i]=1;
						cout<<str<<endl;
						changed++;
						count--;
					}
					else
						str[i]=src[i];
				}
				else if(src[i]==dest[i])
				{
					modified[i]=1;
					changed++;
					count--:
				}
			}
		}
		if(count==0)
			cout<<"Could not convert from source to destination in limited span";
	}
	else
		cout<<"String length not equal";

- beginner November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't handle the case when the first change of the only solution is to change one of the characters in source string to a character different to the character in the same position of destination string.

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need count and changed?

- code_monkey November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use Trie data structure and try finding all the paths. I am sorry if this solution is mentioned anywhere in this page.

- praveen November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A few comments ...

DFS - you would run out of memory very quickly because the recursion tree can be as deep as the number of words of given length in the dictionary. Plus you'd need to remember which words you had already visited to avoid visiting them repatedly with different prefixes.

BFS - that seems to be the only reasonable solution. The difficult part is doing BFS efficiently using a reasoably clean code.

If you doing anything else, seemingly clever, make sure that your code works for the 2 examples. And please add some explanation/comments (@Sunny and others). Blasting code on the page without any explanation is not helping anybody.

- czpete425 November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fast fastest solution that does not use graph for DFS. For dictionary with 120K words solution for EVERY input can be obtained in 0.12sec.

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>

using namespace std;

static constexpr int alphabetSize = 'z' - 'a' + 1;

class FinderResult {
public:
    
    FinderResult & operator <<(string s) {
        sequence.push_back(s);
        return *this;
    }
    
    void outputToStream(ostream &out) const {
        if (sequence.size() == 0) {
            out << "(not found)";
        } else {
            for (const string &s : sequence) {
                out << s;
                if (&s != &sequence.back()) {
                    out << ", ";
                }
            }
        }
    }
    
private:
    
    vector<string> sequence;
};

ostream & operator <<(ostream &out, const FinderResult &result) {
    result.outputToStream(out);
    return out;
}

class MaskCache {
public:
    vector<int> indices;
};

class PositionCache {
public:
    map<string, MaskCache> mask;
};

class Dictionary {
public:
    
    Dictionary & operator <<(string word) {
        int wordIndex = size();
        for (int position = 0; position < length_; position++) {
            char saved = word[position];
            word[position] = '*';
            PositionCache &positionCache = positions[position];
            auto iterator = positionCache.mask.find(word);
            if (iterator == positionCache.mask.end()) {
                MaskCache maskCache;
                maskCache.indices.push_back(wordIndex);
                positionCache.mask.insert(std::make_pair(word, maskCache));
            } else {
                iterator->second.indices.push_back(wordIndex);
            }
            
            word[position] = saved;
        }
        words.push_back(word);
        return *this;
    }
    
    void init(int length) {
        length_ = length;
        positions.resize(length);
    }
    
    string & operator [](int index) {
        return words[index];
    }
    
    int size() {
        return words.size();
    }
    
private:
    
    // cache
    int length_;
    
public:
    
    vector<string> words;
    vector<PositionCache> positions;
};

class Finder {
public:
    
    Finder(string fromString, string toString) : fromString_(fromString), toString_(toString) {
    }
    
    void load() {
        length_ = fromString_.size();
        dictionary_.init(length_);
        
        ifstream dictionaryFile("EnglishWords");
        string word;
        while (!dictionaryFile.eof()) {
            dictionaryFile >> word;
            if (word.size() == fromString_.size()) {
                int wordIndex = dictionary_.size();
                if (fromString_ == word) {
                    fromIndex_ = wordIndex;
                }
                if (toString_ == word) {
                    toIndex_ = wordIndex;
                }
                dictionary_ << word;
            }
        }
        visited_ = vector<bool>(dictionary_.size(), false);
        sequence_ = vector<string>();
    }
    
    FinderResult find() {
        FinderResult result;
        if (fromIndex_ != -1 && toIndex_ != -1) {
            if (fromIndex_ == toIndex_) {
                result << fromString_;
            } else {
                bool found = internalFind(fromIndex_);
                if (found) {
                    result << dictionary_[fromIndex_];
                    for (int i = sequence_.size() - 1; i >= 0; i--) {
                        result << sequence_[i];
                    }
                }
            }
        }
        return result;
    }
    
protected:
    
    bool internalFind(int wordIndex) {
        if (visit(wordIndex)) {
            if (wordIndex == toIndex_) {
                return true;
            } else {
                for (int position = 0; position < length_; position++) {
                    string &currentString = dictionary_[wordIndex];
                    PositionCache &positionCache = dictionary_.positions[position];
                    if (!positionCache.mask.empty()) {
                        char saved = currentString[position];
                        currentString[position] = '*';
                        auto maskCacheIterator = positionCache.mask.find(currentString);
                        if (maskCacheIterator != positionCache.mask.end()) {
                            vector<int> &indices = maskCacheIterator->second.indices;
                            for (int index : indices) {
                                if (internalFind(index)) {
                                    sequence_.push_back(dictionary_[index]);
                                    currentString[position] = saved;
                                    return true;
                                }
                            }
                        }
                        currentString[position] = saved;
                    }   
                }
            }
        }
        return false;
    }
    
    bool visit(int index) {
        if (visited_[index]) {
            return false;
        } else {
            visited_[index] = true;
            return true;
        }
    }
    
private:
    
    // cache
    int length_;
    string fromString_;
    string toString_;
    
    vector<bool> visited_;
    
    vector<string> sequence_;
    
    int fromIndex_ = -1;
    int toIndex_ = -1;
    
    Dictionary dictionary_;
};

int main(int argc, char **argv) {
    if (argc < 3 || argc > 4) {
        cout << "Wrong count of arguments, should be 2 or 3, given " << argc - 1 << endl;
        return -1;
    } else {
        Finder finder(argv[1], argv[2]);
        finder.load();
        FinderResult result;
        result = finder.find();
        if (argc == 4 && argv[3][0] == '1') {
            cout << "Result: " << result << endl;
        }
    }
}

- A.Y.R. November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I wanted to say "my fastest solution" but have mistaken. The variants with graphs are much slower (from 0.2 to 7 seconds with non-constant speed).

- A.Y.R. November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my DFS in Racket Scheme:

#lang racket

(define (match? src str)
  (and (= (string-length src)
          (string-length str))
       (= 1
          (count identity
                 (map (lambda (lhs rhs) (not (eq? lhs rhs)))
                      (string->list src)
                      (string->list str))))))

(define (solve src dst words)
  (let solve* ((src src)
               (words words)
               (path '()))
    (cond [(equal? src dst) (cons #t (cons src path))]
          [(null? words) (cons #f path)]
          [else (call/cc
                  (lambda (return)
                    (let ([words (remove src words)])
                      (for-each (lambda (word)
                                  (let* ([path (cons src path)]
                                         [result (solve* word words path)])
                                    (when (car result)
                                      (return (cons #t (cdr result))))))
                                (filter ((curry match?) src) words)))
                      (cons #f path)))])))

(let* ([src "cat"]
       [dst "dog"]
       [words '("cat" "cot" "bat" "dog" "dot")]
       [result (solve src dst words)])
  (if (car result)
    (printf "~a~%" (reverse (cdr result)))
    (printf "failed~%")))

- liancheng November 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My C++ code here. Solved in DFS style, heavily depends on Boost and STL to shorten the code.

The input file:

cat dot
cat cot dot dog

Here's the code:

#include <boost/bind.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/istream_range.hpp>

using namespace boost;
using namespace boost::adaptors;
using namespace std;

bool match (string const& lhs, string const& rhs)
{
    if (lhs.length () != rhs.length ())
        return false;

    auto pos = mismatch (lhs, rhs);

    if (pos.first == lhs.cend ())
        return false;

    pos = mismatch (make_iterator_range (pos.first + 1, lhs.cend ()),
                    make_iterator_range (pos.second + 1, rhs.cend ()));

    return pos.first == lhs.cend ();
}

template <
    typename ForwardTraversalRange,
    typename OutputIterator
>
bool solve (string const&         src,
            string const&         dst,
            ForwardTraversalRange words,
            OutputIterator        output)
{
    if (src == dst)
        return true;

    if (empty (words))
        return false;

    vector<string> candidates;
    auto pred = bind (match, _1, src);
    copy (words | filtered (pred), back_inserter (candidates));

    for (auto word : candidates) {
        vector<string> new_words;
        auto pred = bind (not_equal_to<string> (), _1, src);
        copy (words | filtered (pred), back_inserter (new_words));

        if (solve (word, dst, new_words, output)) {
            *output = word;
            return true;
        }
    }

    return false;
}

int main (int argc, char* argv [])
{
    string src, dst;
    vector<string> words;

    cin >> src >> dst;
    copy (istream_range<string> (cin), back_inserter (words));

    vector<string> path;
    solve (src, dst, words, back_inserter (path));
    path.push_back (src);
    copy (path | reversed, ostream_iterator<string> (cout, "\n"));

    return 0;

}

- liancheng November 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a.) Assume that we have a function that returns a list of words that differ from the given word by a single character.
b.) The distance metric between two words is the number of characters that they differ in.
c.) We can use a linked list to store the sequence of words that were found to help reach the destination.

Now,
1.) starting from the destination find 'all the words' that are at the distance of 1 from the 'current' word.
2.) Find the word from the list such that the sum of the distances of the word from the destination is closest to the distance between the source and the destination.
3.) If the list was empty before step 2.) then backtrack and regenerate the list for the previous word chosen and then choose another word fulfilling the criteria mentioned in step 2.)
4.) Repeat the above process till you reach a destination or till you cannot find another word in a list that you haven't visited. In which case there is no way you can reach the destination.
I guess the time complexity of the above approach would be poor. But it can have an acceptable space complexity since you would be regenerating the lists if you backtrack.
However, I think the approach should work, nonetheless.

- aman December 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Don't use a generic BFS, use A* search. You use the edit distance of each candidate on the horizon to the target as the heuristic. That way you're not searching blindly with BFS. Maintain the dictionary in a trie that supports wildcard search (wildcard char matches any character, go down all branches).

- Nope January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Everyone think about BFS or DFS. But I'm thinking A* search. As you have the whole dictionary you can preprocess the dictionary to have heuristics which assigns a value how many steps will need to transform string A into string B.

- Riyad Parvez July 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an excellent solution:
algorithmproblems.blogspot.com/2013/01/travel-from-string-to-string.html

- Ivan June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My native idea.

2.h, header file for a simple dict implementation with a hash table

// 2.h
#include <string>
#include <map>

class Dict {
private:
    static std::map<std::string, int> ht_;
    static bool inited_;

public:
    static bool has(const std::string& word);
};

2.cpp, impelmentation file

#include "2.h"


std::map<std::string, int> Dict::ht_;
bool Dict::inited_ = false;


bool Dict::has(const std::string& word)
{
    if (!inited_) {
        inited_ = true;
        ht_["COT"] = 1;
        ht_["DOT"] = 1;
        ht_["COG"] = 1;
    }

    return ht_.find(word) != ht_.end();
}

main file

#include "2.h"

#include <stdio.h>
#include <string.h>


int foo(size_t pos, char *src, const char *dest)
{
    static int count = 0;

    printf("calling %d\n", ++count);

    if (strcmp(src, dest) == 0) {
        printf("%s\n", src);
        return 0;
    }

    char temp;

    for (size_t i = pos, l = strlen(dest); i < l; i++) {
        if (src[i] == dest[i]) {
            printf("%s\n", src);
            continue;
        }

        temp = src[i];
        src[i] = dest[i];

        if (Dict::has(src)) {
            printf("%s\n", src);
            return foo(i + 1, src, dest);
        } else {
            src[i] = temp;
            continue;
        }
    }

    return 0;
}


int main()
{
    char src[] = "CAT", dest[] = "DOG";

    printf("%s\n", src);
    foo(0, src, dest);
    printf("%s\n", dest);

    return 0;
}

- Microwish December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this question regarding Levenshtein algorithm? Here is an example:

def levenshtein(a, b)
  case
    when a.empty? then b.length
    when b.empty? then a.length
  else 
     [(a[0] == b[0] ? 0 : 1) + levenshtein(a[1..-1], b[1..-1]),
     1 + levenshtein(a[1..-1], b),
     1 + levenshtein(a, b[1..-1])].min
  end
end

- Roman Lishtaba January 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <queue>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <stack>

struct Node
{
    std::string parentData;
	std::set<Node> adjacentNodes;
	std::string data;
	
	explicit Node(const std::string& dat) : data(dat) 
	{}
	bool operator< (const Node& rhs) const { return data < rhs.data; }
};

struct DictionaryGraph
{
	std::unordered_set<std::string> dictionary;
	std::unordered_map<std::string, Node> graph;
	
	explicit DictionaryGraph(const std::unordered_set<std::string>& dict)
	    : dictionary(dict)
	{
		for( const auto& word : dictionary )
		{
			Node node(word);
			std::set<Node> adjacent_nodes;
			
			for( auto change_char = 'A'; change_char <= 'Z'; ++change_char )
			{
			    if( change_char != word[0] )
				{
					std::string to_find(change_char + word.substr(1,2));
					const auto& found = dictionary.find(to_find);
					if( found != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}
				if( change_char != word[1] )
				{
					std::string to_find(word.substr(0, 1) + change_char + word.substr(2,1));
					if( dictionary.find(to_find) != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}
				if( change_char != word[2] )
				{
				    std::string to_find(word.substr(0, 2) + change_char);
					if( dictionary.find(to_find) != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}	
			}
			node.adjacentNodes = adjacent_nodes;
			graph.insert(std::make_pair(word, node));
		}
	}
};

void BreadthFirstSearch( const Node& root, const std::string& target, std::unordered_map<std::string, Node>& graph )
{
	std::cout << "start:" << root.data << " target:" << target << "\n";
	
	std::unordered_set<std::string> visited;
	std::queue<Node> node_queue;
	node_queue.push(root);
	visited.insert(root.data);
	
	while( !node_queue.empty() )
	{
		Node current_node = node_queue.front();
		node_queue.pop();
		if( current_node.data == target )
		{
			std::cout << "Found target:" << current_node.data << std::endl;
			
			std::stack<std::string> route;
			route.push(current_node.data);
		
			while( !current_node.parentData.empty() )
			{
				route.push(current_node.parentData);
				if( graph.find(current_node.parentData) != graph.end() )
				{
				    current_node = graph.find(current_node.parentData)->second;	
				}
				else
				{
					break;
				}
			}
			if( !route.empty() )
			{
			    std::cout << route.top();
				route.pop();
			}
			while( !route.empty() )
			{
				std::cout << "->" << route.top();
				route.pop();
			}
			break;
		}

		for( auto& node : current_node.adjacentNodes )
		{
			if( visited.find(node.data) == visited.end() )
			{
				Node& graph_node = graph.find(node.data)->second;
				graph_node.parentData = current_node.data;
				node_queue.push( graph_node );
				visited.insert(node.data);
			}
		}
	}
}

int main()
{
	std::unordered_set<std::string> dictionary { "CAT", "COT", "COG", "DOT", "DOG", "BAT", "BIN", "BOG", "GOT", "HIT", "BIT" };
	
	DictionaryGraph dictionary_graph(dictionary);
	
	std::string start_string = "COG";
	std::string end_string = "BIN";
	
	if( dictionary.find(start_string) == dictionary.end() ||
	    dictionary.find(end_string) == dictionary.end() )
	{
	    std::cout << "Bad input strings. Start:" << start_string << " End:" << end_string;
        return 1;		
	}
	
	Node start_node = dictionary_graph.graph.find(start_string)->second;
	BreadthFirstSearch( start_node, end_string, dictionary_graph.graph );
	return 0;
}

- merlinme June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

char * get_string(char *a, char *b, int pos)
{
	char *d=strdup(a)
	return strdup(*(d+pos)=*(b+pos));
}

void main()
{
	// read the strings in a and b...

	char *new_str=a;
	char *buf=strdup(a);
	char *tmp=a;
	int cnt=0;
	int n=strlen(a);

	while(strcasecmp(new_str,b)!=0)
	{
		tmp=get_string(new_str, b, cnt%n);
		if(dict_contains(tmp))
		{
			new_str=tmp;
			// print it...
		}
		cnt++;
	}
}

- Rahul Arakeri September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it would be helpful for us if u could give the logic behind dict_contains( ) funcion...

- vinodhian September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please try to explain algorithm before posting the code..

- loveCoding September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

bool present_in_dict(char* source)
{
	// have a trie.
	// walk it and return true or 
	// false if the string is present in the trie
}
int make (char *source, char s)
{
	// insert a char s into source such 
	// that the resulting string is in the output.
	// GrEeDy :)
	
	int i;
	char ch;
	
	for (i = 0; i < strlen(source); i++)
	{
		ch = source[i];
		source[i] = s;
		if (present_in_dict(source))
		{
			printf("%s",source);
			return 1;
		}
		source[i] = ch;
	}
	
	retirn 0;
}
int Table[26];
void process (char *s)
{
	for (i = 0; i < 26; i++)
	{
		Table[s[i]-'a']++;
	}
}
void insert (char *s, char *d)
{
	int i;
	for (i = 0; i < 26; i++)
	{
		Table[i] = 0;
	}
	process(d);
	for (i = 0; i < 26; i++)
	{
		if (Table[i] > 0 )
		{
			// if the charecter is yet to be taken
			if( make (s, i + 'a') > 0 ) 
			// 0 + a = a, 1 + a = b..
			{
				// this charecter got in.
				Table[i]--;
				// so again start from the beginning 
				// to see if you can insert any 
				// charecters.
				i = 0;
			}
		}
	}
	// when all charecters are inserted this returns
}

Corrections are highly appreciated. :)

--
“A mistake is a crash-course in learning.”
--

- code_monkey September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A java method to transform.
As an interface use a small dictionary to check for the presence of the word.

Small dictionary in java
---------------------------------
HashSet<String> dictionary = new HashSet<String>();
This is used by the method
boolean isPresent(char[] input);

The transformation method in java
-------------------------------------------------

static void transform(char[] source, char[] destination){
		
		if (source.length != destination.length)
			return;
		
		boolean bArray[] =  new boolean[destination.length];
		
		char[] transformedString = source.clone();

		//The main loop
		for (int count=0;count < source.length; count++){

			for (int checkCount = 0; checkCount<bArray.length; checkCount++){
				boolean flag = bArray[checkCount];
				
				if(flag==true)
					continue;
				
				char[] checkTransformation = transformedString.clone();
				checkTransformation[checkCount] = destination[checkCount];
				
				if (isPresent(checkTransformation) == true){
					bArray[checkCount] = true;
					transformedString = checkTransformation;
					break;
				}
			}
			System.out.println(transformedString);
		}

	}

- mohamed.ghouse September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not work if the only path available requires you to transform a character in source into a character that is not equal to the corresponding one in destination.

- IntwPrep August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

I think this piece of code might work

for (DICTIONARY words : EnumSet Range (words.CAT, words.DOG))
System.out.println(words);

- Kumar November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this is my complete solution with a test case..

class Node:
    
    nodes = {}
    
    def __init__(self, value=0):
        self.value = value
        self.nodes = {}
    
    def add(self, n):
        self.nodes[n.value] = n
        
    def getNode(self, value):
        return self.nodes.get(value)
    
    def getValue(self):
        return value
    
    def addValue(self, str):
        new = self.nodes.get(str[0])
        if not new:
            new = Node(str[0])
            self.add(new)
    
        if len(str) > 1:
            new.addValue(str[1:])
            

def replace(source, dest, root):
    
    current_word = source
    current_parent = root
    while (current_word != dest):
    
        current_parent = root
            
        for i in range(0, len(dest)):
            # go through every index
            
            # lets try to replace the ith letter
            if (current_parent.getNode(dest[i])):
                trial_word = current_word[0:i] + dest[i] + current_word[i+1:]
                if (checkPath(current_parent.getNode(dest[i]), current_word[i+1:])):
                    current_word = trial_word
                    print (current_word)
            
            if (current_word == dest):
                break
            
            current_parent = current_parent.getNode(current_word[i])
            
            
            
def checkPath(node, word):
    for w in word:
        node = node.getNode(w)
        if not node:
            return False
    return True
        
    
if __name__ == '__main__':
    
    root = Node()
    
    words = ['dog', 'cot', 'cog', 'dot', 'dog']
    
    for w in words:
        root.addValue(w)
        
    replace("cat", "dog", root)

- Sunny November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

From what I can tell, there is absolutely no bactracking in your code. The test example works only because your dictionary is very small. It would not work in general case. I really cannot follow your code, but it seems that if you add "hat" to your dictionary, you will get stuck with no way of recovering.

- czpete425 November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

transform(String s1, String s2){
         for(int i = 0; i<s1.length; i++){
             if(s1[i]!=s2[i]){
                  s1[i]=s2[i];
              }
         }
    }

- kamoliddin September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I forgot to check new word to check from dictionary:). Can give more detailed example. Sorry

- kamoliddin September 27, 2012 | Flag
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.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Me too! What a coincidence. Now please stop it. You are causing people to downvote valid answers(IMO) out of spite.

- Loler September 28, 2012 | Flag


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