Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

First question is straightforward so I'll skip it. For second part we can traverse through pairs of synonyms and use find union technique to group all related words. Having that we can easily determine if two sentences are synonymous just by iterating through each word and checking if words from both srntences are in the same group.

- Dante August 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I was asked the same question in my interview. :)

- anaghakr89 August 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first case, I'm thinking of iterating on both sentences, and at each word index 'i', I'll look for the word sentence2[i] in all the possible synonyms of sentence1[i], and if I found a match, I'll mark this word as identical and move on.

- PippityPoppity August 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code below is for the follow up situation.
Another way to build the synonym groups is to build a graph out of the synonym words, and find the synonym groups by extracting connected components out of the graph (using something like DFS BFS).

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

void MergeGroups(unordered_map<int, unordered_set<string>> &groups,
	unordered_map<string, int> &word_to_group_id, int g1, int g2)
{
	if (groups[g1].size() > groups[g2].size()) {
		swap(g1, g2);
	}
	for (auto w : groups[g1]) {
		word_to_group_id[w] = g2;
		groups[g2].insert(w);
	}
	groups.erase(g1);
}

unordered_map<string, int> BuildWordToGroupIdMap(vector<pair<string, string>> const &synonyms)
{
	unordered_map<int, unordered_set<string>> groups;
	unordered_map<string, int> word_to_group_id;
	auto end = word_to_group_id.end();
	int new_group_id = 0;
	for (auto s : synonyms) {
		string const &w1 = s.first;
		string const &w2 = s.second;
		auto it1 = word_to_group_id.find(w1);
		auto it2 = word_to_group_id.find(w2);
		if (it1 == end &&
			it2 != end)
		{
			word_to_group_id[w1] = it2->second;
			groups[it2->second].insert(w1);
		} else if (it1 != end &&
			it2 == end)
		{
			word_to_group_id[w2] = it1->second;
			groups[it1->second].insert(w2);
		} else if (it1 == end &&
			it2 == end)
		{
			int group_id = new_group_id++;
			groups[group_id].insert(w1);
			groups[group_id].insert(w2);
			word_to_group_id[w1] = group_id;
			word_to_group_id[w2] = group_id;
		} else {
			MergeGroups(groups, word_to_group_id, it1->second, it2->second);
		}
	}
	return word_to_group_id;
}

vector<string> ParseSentence(string const &s)
{
	vector<string> words;
	int i = 0;
	while (i < s.size()) {
		while (i < s.size() &&
			s[i] == ' ')
		{
			++i;
		}
		if (i < s.size()) {
			int j = i;
			while (j + 1 < s.size() && s[j + 1] != ' ') {
				++j;
			}
			words.push_back(s.substr(i, j - i + 1));
			i = j + 1;
		}
	}
	return words;
}

bool SynonymSentences(string const &s1, string const &s2,
	unordered_map<string, int> const &word_to_group_id)
{
	vector<string> words1 = ParseSentence(s1);
	vector<string> words2 = ParseSentence(s2);
	if (words1.size() != words2.size()) {
		return false;
	}
	for (int i = 0; i < words1.size(); ++i) {
		auto it1 = word_to_group_id.find(words1[i]);
		auto it2 = word_to_group_id.find(words2[i]);
		if (it1 == word_to_group_id.end() ||
			it2 == word_to_group_id.end() ||
			it1->second != it2->second)
		{
			return false;
		}
	}
	return true;
}

int main(int argvc, char const **argv)
{
	vector<pair<string, string>> synonyms = {{"fast", "quick"}, {"fast", "speedy"}, {"learn", "study"}};
	unordered_map<string, int> word_to_group_id = BuildWordToGroupIdMap(synonyms);
	cout << SynonymSentences("learn quick", "study speedy", word_to_group_id) << "\n";
    return 0;
}

- Alex September 01, 2017 | Flag Reply
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.


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