Status: 4 years experience
Position: SRE-SWE L4 at Google
Location: London, UK
Date: Spring, 2022

I just completed my 5 round on-site interviews with Google. That's my personal summary of the interviews:

• Googliness / Leadership (45 min) : Chilled talk, I focused on communication and I think I did well overall. The situations were easilly related to real world situations I have lived so I didn't have to imagine a lot.
• First DSA interview (45 min):
  • Question: Given a string and an alphabet decide if the string contained the alphabet in order.
  • Example: string = "abc", alphabet = "abc" -> True | string = "bbccbbaaaaac", alphabet = "abc" -> False
  • Follow-up: Find the shortest substring that contained the alphabet in order.
  • Impressions: I did the first question rather quickly after discussing some edge cases. Proposed a O(n) solution for the follow up but didn't have time to implement it. I'd give a 6/10 to my performance.
• Second DSA interview (45 min):
  • Question: A cargo plane is loaded with weights. Given that the weights are filled in containers in a FIFO (first in first out) fashion and the containers are filled in the plane in a LIFO (last in first out) fashion return the unload sequence. The input was given as a string encoding the weights comma separated.
  • Example: "20,9,3,2", containerCapacity = 30 -> "3,2,20,9". In this example the first container will hold [20,9] and the second [3,2]. They will be unloaded first [3,2] then [20,9] forming the output "3,2,20,9".
  • Follow-up: If two neighbouring weights could be swapped to improve the loading process what would be the unload sequence?
  • Impressions: The question was really straight forward, I implemented a solution real quickly and had time to implement the follow up. I didn't understand how swaping the weights could optimize the use of the containers, but the objective was to simulate the process rather than optimizing it.
• Third DSA interview (45 min):
  • Question: Given an on-screen keyboard layout encoded as layout = { row_spacing: float, rows: List[row] } and row = { keys: List[str], key_spacing: float, left_offset: float} write a function that takes a position x, y and outputs the corresponding pressed key. If no key was found at the position x, y return None
  • Follow-up 1: Change the code to return None for ambiguous cases (touches in the border of keys when spacing = 0).
  • Follow-up 2: How would you save and load different keyboard layouts?
  • Impressions: I Implemented a solution with guard clauses. Answered all follow ups and suggested convinient tests and SerDes techniques to save/load the keyboard layout. I finished the whole thing 25 minutes earlier so we chatted a little about Google / SRE.
• Systems design interview (1 hour):
  • Question: Design a mapping service that would serve 100M active users / day with satelite / aerial photos.
  • Impressions: I think I managed to build a reasonable system that answered the requirements of the intervew. It was not my best one but I think I did not fail either. My solution was based on using a CDN to shard geographically close images together and reduce the access to the central service. The only bottleneck was the storage.
• Extra DSA round 1 (45 minutes):
  • Given a (potentially huge) sorted list of strings count the number of strings containing a given prefix.
  • Example: arr = ["a","aa","aab","abc"], pre = "aa" -> count = 2
  • Follow up 1: For a fixed list of strings (not necessarily sorted) count the number of strings containing a given prefix. In this case the count function would be called multiple times.
  • Follow up 2: How would you change the previous answer to take into account near matches of a given prefix. A near match is a match were at most k letters could differ from the given prefix.
  • Impressions: Implemented the first one using three binary searches, one to find one string containing the prefix, a second one to find the first one to contain it and the third one to find the last string containing it. O(log n * k) time complexity for len(arr) = n and max(len(arr[i])) = k and constant space complexity. I implemented the first follow up with a Trie storing the count at each node. The time complexity for the setup would be O(n * k) and O(len(pre)) for a query. The space complexity would be O(n * k) as well to store the Trie. The last follow up was only discussed orally and I decided to use a DFS with a counter as a first approach (there were 2 minutes left).
• Extra DSA round 2 (45 minutes):
  • Given a rectangular matrix representing a grid of roads. At wich intersection there is a trafic light. Each entry in the array corresponds to the time at which a trafic light would go from red to green. Calculate the minimum time by which a car leaving the top left corner would reach the bottom right corner. The car can only move down or right.
  • Follow up: What if the car could go to any cardinal direction at any given time?
  • Extra question: Given a round pizza with a certain amount of mushrooms in each slice, calculate the maximum number of mushrooms one could eat by only taking non adjacent pieces.
  • Impressions: The first one was a classic Union-Find question, the follow up was a direct extension. I didn't have much time to think about the extra question, but I suggested a solution with a memoized exploration function (DP) but wasn't able to estimate the complexity. The optimal solution was O(n^2) so I was a bit far from it, the brute force was ok for 15 minutes I guess.

I am currently waiting for their feedback, I hope it works out.
How do you think I did? I know the questions were easy but I am not confident at all about the whole thing.

Update: Got accepted for L3 and since most feedback was strong hire except from the systems design one I was suggested to do two aditional DSA interviews to upgrade to L4.

Update: Got accepted for L4.