Google Four-Round Interview Experience
Summary
I experienced a four-round interview process at Google, which included three challenging coding rounds focused on graph algorithms, data stream manipulation, and string processing, alongside a Googleyness behavioral round. While some coding problems were tough, I felt I performed well in others and approached the behavioral questions confidently.
Full Experience
I recently completed a comprehensive four-round interview process with Google. The first round was focused on coding, presenting a challenging graph problem about finding the lowest total cost for two individuals traveling to a common destination. I struggled with this, perhaps overthinking for an optimal solution instead of starting with a brute-force approach as hinted by the interviewer. I couldn't fully solve it during the interview.
The second coding round involved designing a function to store integers in a data stream and, after each insertion, identify a triplet where all pairwise absolute differences were within a given distance. Initially, I considered dynamic programming, but with a subtle hint from the interviewer to view the stream as a number line, I pivoted to an approach involving maintaining a sorted order and using a linear scan. I further optimized this with monotonic and temporary stacks, which the interviewer appreciated, and I felt quite confident about my performance in this round.
My third coding interview asked me to identify ambigrams from a list of words. This felt more straightforward; I used a double-pointer method with character-to-bidirectional character conversion, and the interviewer seemed satisfied. A follow-up question about 'interesting words' was too vague to provide a concrete solution.
Finally, the fourth round was the Googleyness interview. Here, I was asked about past failures and experiences where I created something from nothing. I believe that by understanding Google's culture and preparing relevant stories using the STAR method, one can navigate this round successfully.
Interview Questions (5)
Given a graph of cities, two individuals, A and B, live in different cities and are both traveling to the same destination city. The task is to find the lowest total cost required for both A and B to reach that common destination.
Implement a function fn(value: int) that takes an integer and adds it to a data stream. After each insertion, the function must return a triplet (x, y, z) from the data stream that satisfies the conditions abs(x-y) <= distance, abs(y-z) <= distance, and abs(z-x) <= distance. If no such triplet exists, return None.
Given a list of words, return a new list containing only the words that are ambigrams (words that read the same when rotated 180 degrees).
Tell me about a time you experienced failure, detailing the situation and what transpired.
Tell me about a specific instance where you initiated and built something from scratch.