Google

## Round 1 ### Introduction The interview started with my introduction. I gave a brief intro about my course at IIITB and myself. I also mentioned the "Google Cloud course" and highlighted the deep learning courses I took during the last two years of engineering. ### DSA Problems #### Problem 1 (Very Easy) Given a string, create a function `xyz` which returns the score of the string. The score is defined as the sum of differences of all adjacent characters. * **Example:** "adc" has a score of |a-d| + |d-c| = 3 + 1 = 4. * **Self-Correction:** I initially forgot to use the absolute value in the sum, but I noticed it quickly during a dry run with the interviewer's examples. #### Problem 2 (Follow-up on Problem 1) You are given a dictionary (vector or array of strings) and a target string. You have to return a string from the dictionary that has the same `hashValue` as the given string and the maximum `xyz` score (calculated in Problem 1). * **Note:** The `hashValue` is a pseudo-function where any string with the same characters rearranged has the same hash (e.g., "abc" and "bac" have the same hashValue). * **Constraint:** Implement this within a class structure such that multiple queries do not cause repetitions/redundant work. * **Approach:** I initialized the dictionary once during class instantiation and then passed strings as parameters to the function. This optimized the complexity for multiple queries. #### Problem 3 (Follow-up on Problem 2) What if the dictionary is extremely large (e.g., the Oxford dictionary)? * **Approach:** I used a Map-based approach to handle the scale. The interviewer approved the final complexities. ### Conclusion I asked the interviewer about their work at Google and the culture/life at the company. --- ## Round 2 ### Introduction Similar introduction as Round 1. ### Problem Statement **Given a binary tree, pretty print it.** Example output format: ``` 3 / \ 2 1 / \ / \ 4 5 6 7 ``` ### Discussion and Implementation * I created a function to generate a level-order traversal stored in a `vector>` to be used by a printing function. * While writing the printing logic, the interviewer pointed out that my spacing logic failed starting from the third level. * I eventually figured out the logic for the spaces and explained it verbally, but I was unable to complete the full implementation within the time limit. * The time and space complexities of the code I did manage to write were as expected. ### Conclusion I asked similar questions as in Round 1 regarding the interviewer's experience at Google.