Question

Google | Interview experiences | L4 | 2022 | Set-29

Answer 1

Coding interview question at Google

Given a list of pair of words which are synonyms. Then, write a program to check whether 2 sentences are similar.Ex:
[{'quick', 'fast'}, {'rapid', 'fast'}]"you were quick" and "you were rapid" are similar sentence.We can replace word with their synonym words transitively.

Observations

• We need a function which can tell if two words are similar or not.
• We can put pair of synonym words to a HashMap.

But how do we check if 2 words are synonym transitively?

We need a way to create group of similar words.

Example
'quick', 'fast' and 'rapid' belongs to same group.

Any specific data-structure we can use for this?

Disjoint sets.

We can add each pair of synonym words to disjoint set and if two words belongs to same set then they are similar.

Here is a sample example of disjoint set we can use . Also we can add compression to reduce time complexity.

class DSU {
    Map<String, String> parent;
    
    DSU() {
        parent = new HashMap();
    }
    
    String find(String s) {
        if(s == parent.get(s)) return s;
        parent.put(s, find(parent.get(s)));
        return parent.get(s);
    }
    
    void add(String s1, String s2) {
        if(!parent.containsKey(s1)) parent.put(s1, s1);
        if(!parent.containsKey(s2)) parent.put(s2, s2);
        String parentOfS1 = find(s1);
        String parentOfS2 = find(s2);
        parent.put(s1, parentOfS2);
    }
    
    boolean isInSameSet(String s1, String s2) {
         String parentOfS1 = find(s1);
         String parentOfS2 = find(s2);
        return parentOfS1.equals(parentOfS2);
    }
}

Thanks for reading.

Happy coding !!!