About me

• Tier 3 College
• 3 YOE in a service based company
• From India , currently in Germany (onsite)

How Google HR Contacted Me

I used to apply for the Software Engineer role on the career portal once every month with no luck. I also applied with referrals, but my resume got rejected. However, this time an HR representative from Google reached out to me via email. She asked for information about my current location and my programming language of choice and inquired if I could attend a phone screen round in 2 weeks. I requested 3 weeks instead. She gave me an interview date with 3 weeks to prepare and shared basic documents on the subjects I needed to review.

Google Phone Screen Round

The interview started with the interviewer introducing himself on Google Meet. The interview began when I opened the interview document.

Sample Input

array = ["bomb", "book", "g","gift", "go", "goal", "goat", "gum","xray","yellow","zebra"]
prefix = "go"

Sample Output

3

Problem Statement

Given the sorted array and prefix, return the number of elements in the array that start with the prefix value. I started by giving a linear approach which takes O(n * k) time complexity (n - length of array, k - length of prefix).

Interview Experience

He was looking for an optimized approach. Then, I came up with using binary search to find one element that satisfies the prefix condition and then using two pointers to find the count of elements. This was not good enough as in the worst case it would still be O(n * k).

After some time, the interviewer hinted to use binary search to find the left end and right end of the array that satisfies this condition. I started coding two binary search functions, one to find the leftmost element and the other to find the rightmost element.

The interviewer was satisfied with the first binary search (the one to find the left end). For the second binary search (the one to find the right end), I was missing an extra condition. While trying to figure it out, the time ended (interview time - 45 mins).

The interviewer asked for feedback on how the process was and shared some of his own feedback. He told me my communication was good, but I need to be more open-minded about the logic.

Result

The HR called me the next day and told that the interviewer rejected me and told I can reach back after 1 year.