Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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