Round 1: Coding

Q: Given a graph of cities, A and B live in two different cities and are traveling to the same city. Find the lowest total cost required to reach the destination.

I did not solve this problem. I was focused on finding an optimal solution. I ignored the interviewer's suggestion to implement a brute-force solution. In fact, you could use binary search to find the answer and then use DFS/BFS to determine feasibility. You could also use a union-find set to find the minimum value, or use Dijkstra's algorithm with the shortest path idea to find the minimum value.

Round 2: Coding

Q: Write a function fn(value: int) that takes an integer as input and stores it in a data stream. After each insertion, the function must return the data stream that satisfies the following conditions: abs(x-y) <= distance && abs(y-z) <= distance && abs(z-x) <= distance. If no such triplet exists, return None.

Initially, I considered using dynamic programming to solve this, but quickly realized it wasn't the optimal solution. The interviewer also suggested treating the data stream as a number line. Then I thought of sorting the data stream after each insertion and using a linear scan to find a subarray of length 3 where the absolute difference between the first and last elements is less than or equal to the distance. To avoid sorting, I proposed an optimized solution using a monotonic stack and a temporary stack to maintain the sorted order of the data stream during insertion. The interviewer also approved of this solution. I felt that I performed reasonably well in this round.

Round 3: Coding

Q: Given a list of words, return a list of ambigrams.

This question was straightforward. I iterated through each word and used a double pointer method to convert each character into a bidirectional character. The interviewer was satisfied with this approach and posed follow-up questions.

Follow-up: Given a list of words, identify the list of interesting words.
I converted the input list into a set to accelerate the search process and then solved the problem using an optimized approach.

Round 4: Googleyness

Q1: Tell me about the last time you failed, and what happened?
Q2: Tell me about a time you created something from nothing

As long as you understand Google's culture and values in advance and prepare relevant experiences and stories, use the STAR method to clearly describe them, and let the interviewer better understand your abilities and performance, this round should be no problem.