## Google Interview Question for Software Engineers

• 3

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];
}``````

Comment hidden because of low score. Click to expand.
0

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.

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

``````public static void main(String[] args) {
Set<String> set = new HashSet<>();
}

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

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

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

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

if (!word.equals(beginWord)) {
}

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)){
wordDict.remove(newWord);
}
arr[i]=temp;
}
}
}
return result;
}``````

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<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;
}

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;
}
}
}``````

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``````

Comment hidden because of low score. Click to expand.
0

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.

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``````

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)
}
return result;
}``````

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``````

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);
}
}
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();
}

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)

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;
}``````

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

f

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;
}``````

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;
}``````

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;
}``````

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)``````

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;
}``````

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

``````def match_list(L, w):
l = len(w)
ret_list = []
count = 0
for ele in L:
if len(ele) == l:
for i in range(l):
if ele[i] == w[i]:
count +=1
elif count == 2:
ret_list.append(ele)
count = 0
else:
if count == 2:
ret_list.append(ele)
count = 0
return ret_list``````

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));
}``````

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();
return set;
}
if(match == a.length() - 1)
}
if(set.size() > 0) {
return set.stream()
.limit(3)
}
return set;
}
}

public static void main(String args[]) {
Set<String> set = new HashSet<>();
System.out.println(Dictionary.findSimillar("sot",set));
}
}``````

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();
return set;
}
if(match == a.length() - 1)
}
if(set.size() > 0) {
return set.stream()
.limit(3)
}
return set;
}
}

public static void main(String args[]) {
Set<String> set = new HashSet<>();
System.out.println(Dictionary.findSimillar("sot",set));
}
}``````

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.

### 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.