Tuesday 4 December 2012

Google Interview Experience

I was shortlisted by Google for final rounds of interviews. Here are the questions asked to me during my face-to-face interviews. Each interview was for about 45 minutes.

Round1:

The interviewer started by asking me about myself and then about my projects. He asked questions like "Why Google", "Why not some other company like Eg. Microsoft", "How would you design a Self-controlling car", which I had to answer within 30 seconds.

1) Write code to multiply 2 matrices, check for corner cases, erroneous inputs etc.

2) Given a matrix M, check whether 2 rows are exactly equal in the matrix. Optimize time complexity.

Eg. M  =     1 2 3, then rows 1 and 3 are same.
                3 4 5
                1 2 3


Round2:

1) Given a N*N grid of characters, find all the words that can be made using by traversing in the eight possible directions in the grid. (similar to Boggle)

2) Find some local minima in an array of integers, assume that all the integers are distinct.

Local minima definition :
Given an array a[1], a[2], ... , a[n-1]

 if a[0] < a[1], then a[0] is a local minima
 if a[n-1] < a[n-2], then a[n-1] is a local minima
 if a[i] > a[i-1] && a[i] < a[i+1], then a[i] is a local minima

8 comments:

  1. This is 2D version of same problem, I was asked during interview by company x.

    Given 2D array, find local minima. An element is local minima, iff none of horizontally/vertically adjacent neighbors is smaller than it. e.g. most of elements will have 4 neighbors.

    ReplyDelete
  2. if a[i] > a[i-1] && a[i] < a[i+1], then a[i] is a local minima

    shouldnt a[i-1] be local minima ?

    ReplyDelete
  3. Ya, case 3 should be : If a[i] < a[i-1] and a[i] < a[i+1], then a[i] is a local minimum. Right?

    ReplyDelete
  4. @Tikna please relook the definition. Local minima definition is slight different only for the first and last elements in the array.

    @xyon Correct!

    ReplyDelete
  5. @ chinmay did you post your questions at careercup ??

    ReplyDelete
  6. @purushottam I haven't yet, but I think the above questions are rather commonly asked questions and they would be already present on careercup

    ReplyDelete
  7. Any idea abt how good is this book : "Top 10 coding interview problems asked in Google with solutions: Algorithmic Approach"
    (http://www.amazon.com/gp/product/1482799014/)

    ReplyDelete
  8. @Chandrashekar No, I am hearing about this book for the first time.

    ReplyDelete