Status: I have been working at Visa as Software Engineer for 1 year.
Position: SETI at Google, Bangalore.

Hi, I recently went through a Google Interview and I wanted to share my experince here since LeetCode helped me a lot to prepare for it.

Techical Phone Screen(45 minutes):

1. Given two strings A and B, find the longest common prefix.
2. Given two strings A and B, what's the longest prefix of A which is suffix of B.
3. Given a list of strings, find number of unique prefixes of all the strings.
4. Given a list of string, find the longest common substring of all strings.

Before writing out the code for every question, I was asked the time and space complexity for my solution.

Onsite(5 rounds, 45 minutes each):
In these rounds, a bit more time was given to introductions at the start and to my questions at the end. Around 30 minutes(avg.) was given to solve the problems.

• 1st round(over Hangouts):
  How would you implement searching in a contacts book of a phone. Initally, I was asked for just prefix search, but was asked to expand this to include infix search as well, and implement it.

  Example,

  names = ['rahul', 'rohit', 'varun', 'mohit']
  search_string = 'r' --> expected_search_result = ['rahul', 'rohit', 'varun']
  search_string = 'ra' --> expected_search_result = ['rahul']
  search_string = 'hit' --> expected_search_result = ['rohit', 'mohit']

  Time and space complexity questions after implementing. He touched upon multithreading at the end, but we were short on time.

• 2nd round(in person):

  • Given an array of unique positive integers, for each integer, return the first larger element in the array to the left. If there's no larger element, return -1 for it.
    Example:
    arr = [70, 60, 40, 50, 35, 90, 10]
ans = [-1, 70, 60, 60, 50, -1, 90]
  • In a binary tree, one extra invalid edge has been added by mistake. Given the root node, find and remove the invalid edge from the tree and return the root.

  After each question, I was asked to write what test cases I'd run to make sure the code is correct.

• 3rd round(over Hangouts):

  • Given an array which is permutation of n couples(2n elements), find the minimum number of swaps you have to do to correcly place each couple together. Assume, (1,2) are a couple, (3,4) are couple, ... , (2n-1, 2n) are couple.
    Example:
    [1,3,4,2] -> 1 swap
[2,6,4,5,1,3] -> 2 swaps

  • Given a doubly linked list, remove an element from the list whose value is key.

  Again, time and space complexity questions and test cases were expected.

• 4th round(over Hangouts)
  I had to implement a simple pinball machine. A ball would be put on the board at any valid place with any direction. Simulate the game and print where the ball would exit. (Assume the ball won't get stuck in a loop)
  Example,

  board = [ . . . \ . ]
          [ . \ . / . ]
  ball_pos = (0,0), ball_dir = (0,1)
  exit_pos = (0,1), exit_dir = (-1,0) 

  I think I was mainly asked how I would approach this problem, and how would I refactor my code so it can be tested in an easier way.

• 5th round(over Hangouts)

  • Validate if a given graph is a binary tree or not.

    I was asked to write test cases. Questions about testing like:

    • at what point do you stop writing tests
    • how would you say that your code is completely tested
    • what kinds of tests would you do in this case
    • how large should your test cases be
    • on what would your tests cases depend
    • etc.