Google interview questions
I was interviewed for a Software Reliability Engineer position.

A recruiter from Google contacted and asked if I want to have an interview with a Google engineer,
It is hard to say no to Google; after all, in terms of benefits, working for Google is the second best thing after having your own business.

Two weeks have passed and no word from Goggle.
Well, I thought, they have so many candidates that have probably forgotten about me.
But in another week, I received an e-mail from the same recruiter asking to select your top three areas of my developmental expertise.
1) Web applications and multi-tiered systems
2) Database internals
3) Windows development
And she also asked me if I know someone who already works for Google. I found two references (in retrospective should have said no).
In a week another recruiter contacted me and asked to rate myself:
   0 – Indicates you have NO EXPERIENCE – that is fine but please indicate
1-3 – Indicates you can read / understand the subject area, but would not be comfortable implementing anything in it.
4-6 – Indicates you are comfortable with the subject area and all normal / routine work in it.
   7 – Indicates that you are extremely proficient and have deep technical expertise in the subject.  You would be comfortable with personally designing and implementing any project in that area.
   8 – Indicates that you are almost an expert from fundamentals to advanced concepts.
   9 – Indicates you are an expert and could have written a book on the subject, but didn’t.
 10 – Reserved for those who are recognized industry experts in a field (i.e. wrote a book on the subject).

3 TCP/IP Networking (OSI stack, DNS etc)
3 Unix/Linux internals
6 Unix/Linux Systems administration
6 Algorithms & Data Structures
5 C
8 C++
0 Python
4 Java
4 Perl
6 Shell Scripting (sh, Bash, ksh, csh)
8 SQL and/or Database Admin
4 Management

In a couple of days the second recruiter scheduled a phone interview with him for the following week.
Five minutes before the scheduled interview I received and e-mail from the recruiter saying that he has an emergency meeting and would like to reschedule the interview for the next week.
Next week he called and asked some questions:

  1. Convert a number from decimal to binary.
  2. Describe some basic data structures.
  3. Describe some basic search algorithms.
And then he continued talking on the importance of Software Reliability Engineers.
In two weeks he scheduled a phone interview for me with a Google engineer.
The interview was conducted using Google online documents so that the interviewer could see me type the code.
She asked just one question:

1)    We have two bishops on a chess board. The board has 64 squares and each square is numbered 1 through 64.The bishop has no restrictions in distance for each move, but is limited to diagonal movement.
a.    Write a function that given position of the two bishops (a number between 1 and 64) returns minimum number of turns required for the bishops to meet. Return -1 if no solution found. For example, for bishops located at postions 10 and 26 the function should return 2.
The problem is really hard to solve if we stick with 1 through 64 numbering but ones we switch to x and y coordinates the solution is trivial.
The interviewer was very nice and helpful.

Next day I received an e-mail for the recruiter saying that they were “impressed with my problem solving skills” and would like to schedule a second phone interview.
This time the subject would be Linux. The interview was scheduled for the next week.
My Linux skills are a little bit rusty so the next weekend I ended up reading Linux books,
The second engineer who called me was not as nice as the first, and just by talking to him for the first two minutes put me in a panic mode.
He asked me two questions and none of them was related to Linux:

1)    Explain Insertion, Heap, and Quick sort.
2)    Given two words that contain the same number of characters find the fastest way to transform word one into word two by changing one letter a time. All the transitional words must be valid words from a dictionary.
a.    For instance transform cat to bet: cat-bat-bet

With some help for the interviewer I figured out that a graph that connects each word to all the words from the dictionary that differ by one letter must be built, and then Dijkstra can be run on it to determine the shortest path.
And then he asked me, what is the complexity of Dijkstra algorithm? To my surprise I completely forgot its complexity, after all the last time I used it was ten years ago.
The next thirty minutes I was deducing the complexity of Dijkstra algorithm and with some help from the guy I solved the problem O(EN).
I could have easily checked the complexity online but I was curious to solve it by myself, and I also wanted to be fair.
The guy thanked me and in three weeks I received a rejection letter from Google.

Leave a Reply

nine − 1 =