Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

Most answers (I did not check them all) scan the collection of words
and check if they differ by 1 character from the input. That may work
fine for the given example, but is not too scalable. Here's my C++
solution:

1. Build a dictionary of patterns that can be matched by the given
words. For example: "?at" => "pat", "sat", "vat".

std::unordered_set<std::string> words({ "vil", "sit", "flick", "pat", "pluck", "sat", "vat", "vit" });
	std::unordered_map<std::string, std::unordered_set<std::string>> dictionary;
	for (auto w : words)
	{
		std::string k = w;
		for (int i = 0; i < k.size(); i++)
		{
			k[i] = '?';
			dictionary[k].insert(w);
			k[i] = w[i];
		}
	}

2. Build all possible patterns from the input word and check
them against this dictionary:

std::string s = "vit";
	std::string k = s;
	for (int i = 0; i < k.size(); i++)
	{
		k[i] = '?';
		auto it = dictionary.find(k);
		if (it != dictionary.end())
		{
			for (auto& w : it->second)
			{
				if (w != s)
					std::cout << w << std::endl;
			}
		}
		k[i] = s[i];
	}

- hb March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why it is not scalable ?. We can segregate the dictionary by word length.
Map<Integer, HashSet<String>> map; //key - length & value - set of words
and this would also be helpful in decreasing the lookup time in the set.

However, I believe the most efficient way is to use Trie.

The main assumption here is that the character is mistyped not and not left over.

- Popeye May 18, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("vil");set.add("sit");set.add("flick");set.add("pat");set.add("pluck");set.add("sat");set.add("vat");
        System.out.println(ladderLength("vit", 3, set));
    }

    public static List<String> ladderLength(String beginWord, int count, Set<String> wordDict) {
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        List<String> result = new ArrayList<>();

        while(!queue.isEmpty()){
            String word = queue.poll();

            if(result.size() == count){
                break;
            }

            if (!word.equals(beginWord)) {
                result.add(word);
            }

            char[] arr = word.toCharArray();
            for(int i=0; i<arr.length; i++){
                for(char c='a'; c<='z'; c++){
                    char temp = arr[i];
                    if(arr[i]!=c){
                        arr[i]=c;
                    }
                    String newWord = new String(arr);
                    if(wordDict.contains(newWord)){
                        queue.add(newWord);
                        wordDict.remove(newWord);
                    }
                    arr[i]=temp;
                }
            }
        }
        return result;
    }

- sj March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Example {
    public static void main(String[] args) {
        Example e = new Example();
        List<String> list = new ArrayList<>();
        list.add("vil");
        list.add("sit");
        list.add("flick");
        list.add("pat");
        list.add("pluck");
        list.add("sat");
        list.add("vat");
        List<String> r = e.getClosestStrings("vit", list, 1);
        r.forEach(System.out::println);
    }

    public List<String> getClosestStrings(String str, List<String> list, int maxDist) {
        if (str == null || list == null || list.isEmpty()) return null;
        List<String> res = new ArrayList<>();

        PriorityQueue<StringDist> pq = new PriorityQueue<>(Comparator.comparingInt(s1 -> s1.dist));

        Map<Character, Integer> charCountMap = getCharCountMap(str);
        for(String s: list) {
            int dist = getDist(getCharCountMap(s), charCountMap);
            pq.offer(new StringDist(s, str, dist));
        }

        while (!pq.isEmpty()) {
            StringDist sd = pq.poll();
            if (sd.dist > maxDist) break;
            res.add(sd.source);
        }

        return res;
    }

    private Map<Character, Integer> getCharCountMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        for(char c: str.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        return map;
    }

    private Integer getDist(Map<Character, Integer> map1, Map<Character, Integer> map2) {
        int diff = 0;
        for(Map.Entry<Character, Integer> e: map1.entrySet()) {
            diff += map2.containsKey(e.getKey()) ? Math.abs(e.getValue() - map2.get(e.getKey())) : e.getValue();
        }

        return diff;
    }

    private class StringDist {
        String source;
        String target;
        Integer dist;

        public StringDist(String source, String target, Integer dist) {
            this.source = source;
            this.target = target;
            this.dist = dist;
        }
    }
}

- guilhebl March 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def misspelled_match(input,dictionary):
    output = []
    n = len(input)
    for word in dictionary:
        if len(word) == n:
            count = 0
            for i,e in enumerate(word):
                if e not in input:
                    if count == 0:
                        count += 1
                    else:
                        break
                if i == n-1:
                    output.append(word)
                    #print(word)
    return output

- Sandhya March 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I may see that in the solution you ignore the order of letters in the dictionary and given input.
What is about words in the dictionary like "tis","ilv","itv" . They consist of the same letters but they have more differences if order is taken into account.

- Siam March 14, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def misspelled_match(input,dictionary):
    output = []
    n = len(input)
    for word in dictionary:
        if len(word) == n:
            count = 0
            for i,e in enumerate(word):
                if e not in input:
                    if count == 0:
                        count += 1
                    else:
                        break
                if i == n-1:
                    output.append(word)
                    #print(word)
    return output

- Anonymous March 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static List<String> findWordInDictWith1Mistake(List<String> dict, String word) {
        List<String> result = new ArrayList<>();
        for( String s : dict ) {
            int foundMistake=0;
            for( int i = 0 ; i < word.length() && foundMistake < 2 ; ++i ) {
                if(s.charAt(i) != word.charAt(i))
                    ++foundMistake;
            }
            if(foundMistake == 1)
                result.add(s);
        }
        return result;
    }

- DevilDeepu March 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def compute_distance(w,q):
    assert len(w) == len(q)
    dist = 0
    for k in range(len(w)):
        if w[k] != q[k]:
            dist = dist +1
    return dist

def miss_splell(words, query):
    result = []
    for w in words:
        if len(w) == len(query):
            dist = compute_distance(w, query)
            if dist == 1:
                result.append(w)
            if len(result) == 3:
                break
    return result

- autoboli March 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static List<String> findWords(String str)
{
List<String> result = new ArrayList<String>();
int allowedMatchCount = (str.length()/2)+1;
for(String str2:dict1)
{
if(getCountOfMatches(str, str2)>=allowedMatchCount)
{
System.out.println(str2);
result.add(str2);
}
}
return result;
}

static int getCountOfMatches(String str1, String str2)
{
BitSet bs = new BitSet(str1.length());
for(int i=0;i<str1.length();i++)
{
bs.set(i, str1.charAt(i) == str2.charAt(i));
}
return bs.cardinality();
}

- Anonymous March 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

diff = get difference with each string in dictionary.
diff needs to be encoded as [0, 0, 0, 4] or [0,6,0,0] i.e. just having one non-zero number
and hence those diffs are valid (ofcourse lengths of strings should be same)

- Anonymous March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I also thought storing all patterns into hash table.
But, there are a lot of cases of the patterns. Using the memory space will increase terribly.
I thought using the Trie could be efficient. So, modified trie.

class ClosetTrie
{
	class Node;
	typedef unordered_map<char, Node*> _children;
	class Node
	{
	public:
		_children children;
		~Node()
		{
			for (pair<const char, Node*>& child : children)
				delete child.second;
		}

		void insert(const char* str)
		{
			if (*str == '\0')
				children['\0'] = NULL;
			else
			{
				_children::const_iterator it = children.find(*str);
				Node* child;
				if (it == children.end())
				{
					child = new Node;
					children[*str] = child;
				}
				else
					child = it->second;

				child->insert(str + 1);
			}
		}

		void find(const char* str, int diff, const string& prefix, list<string>& ret)
		{
			if (ret.size() >= 3)
				return;

			_children::const_iterator it = children.find(*str);
			if (it != children.end())
			{
				if (*str == '\0')
				{
					ret.push_back(prefix);
				}
				else
					it->second->find(str + 1, diff, prefix + *str, ret);
			}

			if (diff == 0)
				return;
			
			const char* next = *str == '\0' ? str : str + 1;
			--diff;
			for (pair<const char, Node*>& child : children)
			{
				if(child.first!=*str)
					child.second->find(next, diff, prefix + child.first, ret);
			}
		}
	};
	Node root;

public:
	ClosetTrie(const unordered_set<string>& dict)
	{
		for (const std::string& str : dict)
			root.insert(str.c_str());
	}

	void find(const char* word, list<string>& ret)
	{
		root.find(word, 1, "", ret);
	}
};

int main()
{
	ClosetTrie trie({ "vil", "sit", "flick", "pat", "pluck", "sat", "vat" });
	list<string> closets;
	trie.find("vit", closets);

	return 0;
}

- lesit.jae March 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

f

- hmm March 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

using namespace std;

int main(int argc, char** argv) {
	set<string> dict = { "vil", "sit", "flick", "pat", "pluck", "sat", "vat", "vit" };
	map<int, vector<string>> myMap;
	string result[3];

	string input = "vit";

	for(auto iter = dict.begin(); iter != dict.end(); ++iter) {
		if(input.length() != iter->length()) continue;

		int diffCount = 0;
		for(int i = 0; i < input.length(); ++i) {
			if(input.at(i) != iter->at(i)) diffCount++;
		}

		myMap[diffCount].push_back(*iter);
	}

	for(int i = 0; i < 3; ++i) {
		result[i] = myMap[1][i];
		cout << result[i] << endl;
	}

	return 0;
}

- alanwuha March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

using namespace std;

int main(int argc, char** argv) {
	set<string> dict = { "vil", "sit", "flick", "pat", "pluck", "sat", "vat", "vit" };
	map<int, vector<string>> myMap;
	string result[3];

	string input = "vit";

	for(auto iter = dict.begin(); iter != dict.end(); ++iter) {
		if(input.length() != iter->length()) continue;

		int diffCount = 0;
		for(int i = 0; i < input.length(); ++i) {
			if(input.at(i) != iter->at(i)) diffCount++;
		}

		myMap[diffCount].push_back(*iter);
	}

	for(int i = 0; i < 3; ++i) {
		result[i] = myMap[1][i];
		cout << result[i] << endl;
	}

	return 0;
}

- alanwuha March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

using namespace std;

int main(int argc, char** argv) {
	set<string> dict = { "vil", "sit", "flick", "pat", "pluck", "sat", "vat", "vit" };
	map<int, vector<string>> myMap;
	string result[3];

	string input = "vit";

	for(auto iter = dict.begin(); iter != dict.end(); ++iter) {
		if(input.length() != iter->length()) continue;

		int diffCount = 0;
		for(int i = 0; i < input.length(); ++i) {
			if(input.at(i) != iter->at(i)) diffCount++;
		}

		myMap[diffCount].push_back(*iter);
	}

	for(int i = 0; i < 3; ++i) {
		result[i] = myMap[1][i];
		cout << result[i] << endl;
	}

	return 0;
}

- alanwuha91 March 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following code should have run time complexity On^3.

def findClosetWords(list_input,word):
    list_ans = []

    for input in list_input:
            cnt = 0
            for char_ in input:
                for char in word: 
                    if char == char_:
                        cnt += 1
            if (cnt == len(word)-1) | (cnt == len(word)+1):
                list_ans.append(input)
    return list_ans
                            
list_input = ['vit','sitt','flick','pii','pluck','sat','vat']
word = "sit"
ans = findClosetWords(list_input,word)
print(ans)

- caspergreen31 March 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear time C++ solution, using a hash set and a heap to collect the nearest results.
The heap contains the 3 results that have the minimum distance of the mistype.
Time complexity is O(n*26*log(3)) = O(n) where n is the length of the word (not of the dictionary, that usually is orders of magnitude bigger).

#include <iostream>
#include <unordered_set>

typedef std::pair<int, string> diffType;

vector<string> findAlternatives(string s, const unordered_set<string> &dict)
{
	vector<string> out;

	if (dict.empty()) return out;

	priority_queue<diffType> pq;
	const int maxElements = 3;
	
	for (int i = 0; i < s.length(); ++i)
    {
        char backupChar = s[i];

        for (char c = 'a'; c <= 'z'; ++c)
        {
            s[i] = c;

            if (dict.find(s) != dict.end())
            {
                pq.push({std::abs(c - backupChar), s});
                if (pq.size() > maxElements)
                    pq.pop();
            }
        }

        s[i] = backupChar;
    }

	while (!pq.empty())
	{
		out.push_back(pq.top().second);
		pq.pop();
	}

	return out;
}


int main()
{
    std::unordered_set<string> dictSet = {"wil", "vil", "sil",
                                          "pil", "men", "pion", "pal"};
    
    std::vector<string> res = findAlternatives("mil", dictSet);
    
    for (string &s: res)
        std::cout << s << " ";
    
    std::cout << std::endl;
}

- bertelli.lorenzo April 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String arg[]){
        String[] dic1={"vil","sit","flick","pat","pluck","sat","vat"};
        String input="vit";
        String[]ans=new String[input.length()];
        int track;
        int count=0,k=0;
        for(int i=0;i<dic1.length;i++){
            track=0;
            if (dic1[i].length() == input.length()) {
            for(int j=0;j<input.length();j++) {
                if (dic1[i].charAt(j) == input.charAt(j)) {
                        track++;
                    }

                }
                if(track==0){

                }
               else if (track== 2) {
                    count++;
                    if (count <=3) {
                        ans[k] = dic1[i];
                        k++;
                    }
                }


            }



        }
        System.out.println(Arrays.toString(ans));
    }

- Saswati Bhattacharjee February 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.*; 
import java.lang.*; 
import java.io.*; 
import static java.util.stream.Collectors.toCollection;
public class MyClass {
    
    static class Dictionary  {
       
       private static int compare(String a, String b) 
        { 
            if(a.length() > b.length() + 1 || a.length() < b.length())
                return -1;
            int match = 0;    
            for(int i = 0; i < a.length(); i++) {
                if(a.charAt(i) == b.charAt(i)) {
                    match ++;
                    continue;
                }
            }
            return match; 
                
        }  
        
        public static Set<String> findSimillar(String a, Set<String> s) {
            Set<String> set = new TreeSet<>();
            for(String m : s) {
                int match = compare(a,m);
                if(match == a.length()) {
                    set.clear();
                    set.add(a);
                    return set;
                }
                if(match == a.length() - 1)
                    set.add(m);
            }
            if(set.size() > 0) {
                return set.stream()
                    .limit(3)
                    .collect(toCollection(LinkedHashSet::new));
            }
            return set;
        }
    }    
        
        
    public static void main(String args[]) {
        Set<String> set = new HashSet<>();
        set.add("vil");set.add("sit");set.add("flick");set.add("pat");set.add("pluck");set.add("sat");set.add("vat");
        System.out.println(Dictionary.findSimillar("sot",set));
    }
}

- Roi S March 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.*; 
import java.lang.*; 
import java.io.*; 
import static java.util.stream.Collectors.toCollection;
public class MyClass {
    
    static class Dictionary  {
       
       private static int compare(String a, String b) 
        { 
            if(a.length() > b.length() + 1 || a.length() < b.length())
                return -1;
            int match = 0;    
            for(int i = 0; i < a.length(); i++) {
                if(a.charAt(i) == b.charAt(i)) {
                    match ++;
                    continue;
                }
            }
            return match; 
                
        }  
        
        public static Set<String> findSimillar(String a, Set<String> s) {
            Set<String> set = new TreeSet<>();
            for(String m : s) {
                int match = compare(a,m);
                if(match == a.length()) {
                    set.clear();
                    set.add(a);
                    return set;
                }
                if(match == a.length() - 1)
                    set.add(m);
            }
            if(set.size() > 0) {
                return set.stream()
                    .limit(3)
                    .collect(toCollection(LinkedHashSet::new));
            }
            return set;
        }
    }    
        
        
    public static void main(String args[]) {
        Set<String> set = new HashSet<>();
        set.add("vil");set.add("sit");set.add("flick");set.add("pat");set.add("pluck");set.add("sat");set.add("vat");
        System.out.println(Dictionary.findSimillar("sot",set));
    }
}

- Anonymous March 11, 2019 | 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