Google's Hiring Algorithm

Found this infographic on Jobvine, very interesting stuff. Gives a good insight on how complex and selective the process is!

How does one 'Get that job at Google'!

Following post is inspired from Steve Yegge's legendary post on prepping for Google Interviews.

Coding Knowledge C/C++ and Java are the preferred programming languages for Google Interviewers. You must know at least one of them really well. You will be expected to write code in the phone screen interviews and in the onsite interviews as well.

Recommended books for CS interviews: 

• Introduction To Algorithms - By Cormen
• Programming Interviews Exposed 
• Cracking the Coding Interviews
• Algorithms for Interviews

Recommended websites for coding practice: InterviewStreet, Topcoder

Big-O This should be the starting point in preparing for an algorithmic interview. You must not struggle with basic complexity analysis, as it will guarantee not being hired. You should be familiar and understand the O, Θ and Ω notations. I recommend reading section on complexity analysis from Data Structures and Algorithms book.

Sorting You should be able to write algorithms O(n*lgn) like QuickSort and MergeSort with ease. Compare and understand the best, worst and average case complexities. I found this table on wiki to be very handy; it lists important properties of all sorting algorithms. Don’t neglect the basic O(n^2) algorithms like Bubble sort or Insertion sort, since other algorithms improve over these. Interviews are more about improving a basic idea, sorting algorithms will help with this process.

Hash Tables When in doubt, think of hash tables. They are useful in most of the problems and frequently help us improve the time complexity of some problems by caching results.

Trees Go through basic tree construction, traversal and manipulation algorithms. You should be able to implement algorithms based on binary search trees. You should be familiar with balanced trees although you are not expected to write code for them in the interview: AVL trees, Red-Black trees, Trie, n-ary trees etc. Thorough knowledge about inorder, postorder and preorder traversals is necessary, because we can solve many tree problems by doing simple modifications to one of these traversals.

Graphs 

• Graphs are a very important concept in Computer Science. Practice the three basic representation of graphs (objects and pointers, matrix, and adjacency list) and familiarize yourself with their pros & cons. 
• There is not much time during the interview so you should not expect something very complex. However, basic graph traversal algorithms (DFS and BFS) are a must, you should implement them in all basic representations. 
• You should be able to implement the Dijkstra or Floyd-Warshall algorithms as well as minimum spanning tree algorithms (Kruskal and Prim). Learn about topological sorting, since it is surprisingly very useful in many ordering problems.

Dynamic Programming This is probably the most important subject as the implementations are small. You should be able to implement 2-3 dynamic algorithms during a 35-40 minutes time. As you’ll check the resources on this blog or on the web, you’ll find that you should expect at least one dynamic programming question per interview.

Operating Systems Learn about processes, threads and concurrency issues. Know about mutexes, semaphores, monitors and how they work. Understand what deadlock and livelock are and how to avoid them. Learn about context switching, scheduling etc.

Mathematics You should familiarize yourself with counting, combinatorics and probability.

Google's publications Read up Google's path-breaking publications listed below if you have time.

• Google File System
• Google Bigtable
• Google MapReduce

I hope you find the above article useful :) Enjoy!

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

Google Test

Google's test conducted at IIT-Bombay consisted of 20 objective questions, which were of moderate difficulty level. It also had a subjective question which goes as follows.

You are given a number of dices n, each with a number of faces m. You roll all the n dices and note the sum of all the throws you get from rolling each dice. If you get a sum >= x, you win, otherwise you lose. Find the probability that you win.

Google's shortlist for final rounds of interviews consisted of only those people who had done relatively well on the test, and fortunately I was one of them. So now you know how important it is to do well on the test.