谷歌L5上门

Round 1
Leadership/Behavioural

  1. Tell me about how you led a project
  2. How do you mentor junior candidates ? How do you distinguish them from senior ones ?
  3. How do you deal with cross functional teams ? Give an instance when you couldn’t implement a feature requested by an external team ?

Round 2
Coding

  1. Given an array of random integers, write an iterator to return a random positive integer from the array. There are no duplicates and the positive element returned earlier should not be returned again.
  • The word random was just asked to confuse the user. You could essentially sort the array and have an iterator point to the first positive element and return for each subsequent call.
  1. Given an array of integers, find the max sum of two non-overalapping subarrays.
    [1,2,-3,5]
    Return - Sum( [1,2] , [5] ) = 8

Round 3
Data Structure Design + Coding
Implement a transactional iterator for a blob of data which is loaded into memory from a 1TB file. The maximum memory for holding the data is in the order of 100 MBs. Let’s say you are already given a structure where you have a chunk of data held in memory but you have to design an iterator for that structure which supports following APIs-

  • public boolean hasNext() - returns true if there’s another blob of data to read
  • public Object next() - returns the contents of the next blob of data
  • public void commit() - Commits or creates a checkpoint for all the data until that given memory block.
  • public void rollback() - Rolls back from the current state to the last commited/checkpointed state

The problem definition was very vague and I had to clarify to figure out what exactly was required to be done.

Round 4
System Design
Design a system to handle aggegration of stats for various entities like users, docs, ads and present those real time stats on a user dashboard. How would you reduce latency ? How would you scale the system ? What are the different trade offs in your design ? How would you make it fault tolerant ?

Round 5
Coding

Given a 2-D grid with bombs placed at various coordinates and diffusers placed at another set of coordinates. Multiple bombs could exist at the same coodinate in the 2-D space but diffusers would be unique per coordinate. Using any distance criteria like manhattan distance. The number of diffusers could be less than the number of bombs in which case some bombs might be left unassigned to diffuse.

  1. Find the assignment of diffusers to bombs. (Similar to campus bikes leetcode problem but with a slight modification).
  2. If every bomb has a certain “ttl” to diffuse, and each diffuser has a certain capability to diffuse a bomb in x amounts of time. Find an assignment such that maximum bombs could be diffused in the fastest way. It could be the case that a diffuser assigned to a bomb difuses it and can select another bomb to diffuse it within it’s ttl and capability.
    Example - Bomb1 should be diffused in 2 seconds while diffuser1 takes 3 seconds to diffuse a bomb. Thus diffuser1 cannot be assigned to Bomb1. While if diffuser2 takes 1 second to diffuse a bomb, he can be assigned to diffuse Bomb1. Here since diffuser2 saved 1 second in diffusing Bomb1, diffuser2 can be assigned to another Bomb having a ttl of more than 1 second.