Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 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.
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

It's a select k problem similar to LeetCode 973. K Closest Points to Origin where k = 3.

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

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.
0
of 0 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
Comment hidden because of low score. Click to expand.
0
of 0 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 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


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