Google | L4 | India | Onsite | DSA | Round 3

Interviewer told there will be only 1 question no follow ups, need to write complete code with complexity analysis

Problem Statement
Given list of words, count the number of buddy pairs (need only count not the string itself)
A pair of strings is a buddy pair if all characters of string a and b follow the same gap

e.g. "abc" is buddy pair for "def"

Asked a lot of clarifying questions and finalised below

1. For two strings to be pair, their lengths should be same
2. Assume only lowercase characters in strings
3. Empty strings are not present
4. We need to find circular difference i.e. dist(a,b)!=dist(b,a)
   dist(b,e) = 3
   dist(e,b) = 23 (get distance from e to z and then to b)
5. Initially, list of strings wont have duplicate strings
6. String is not a buddy pair with itself

Solution
Discussed brute force approach to check every pair is buddy or not
TC - O(n^2L)

Told myself that we can optimise it and started thinking about the optimisation

Discussed trie solution that we can create insert all words in a trie
Then iterate the input list again and try to find its buddy pairs and keep on incrementing count
but string will
TC - O(nL)

Optimised Approach 1
Interviewer said this approach is interesting and asked me if I can write the code in 10-15 mins
I said yes and was about to start the code.
He interrupted me and asked me if I would like to take 2 mins and think of another approach

I said yes and started thinking

Optimised Approach 2
Came up with another approach that for every string transform it into shifted string and put in set and return set count in the end
Then I told set won't work here will need to use hashmap and for every matched word just append count with its frequency in map
TC - O(nL)
SC - O(nL)

Interviewer said this is fine and asked to code

Quickly coded it down
Struggled while writing the transform function and the interviewer helped a bit there to find the difference and get the correct new char

Interviewer asked now what if duplicates are present in the input
I told we can use set of string for every string and match it
He said it wont work and then I told we can pre filter the string to remove duplicates and then use above method again
He said it is fine, did not ask me to write the code

Then he came to my hashmap, it was
Map<String, Integer> buddyMap = new HashMap<>();
He told what will be space, I said O(nL)
He asked can we use integer as key
I said yes, create hash of every string and use that as key
He asked how to generate hash of string
Told him to use a prime number(7) and a module(101)
I told space will reduce to O(n) then
He asked what if hash collisions occur
I told we can shift prime number used in such case but it will not work for correct matches
He then told we can use generate two hashes for every string and match only if both hash matches
This will drop down hash probability to a*b