Sunday, May 18, 2008

Recent Google Interview Questions Papers

Total there are five Technical Interviews followed by Management round.

So here are the questions.

Google Interview Round 1 ::

What is the Space complexity of quick sort algorithm? how do find it?

What are dangling pointers?

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

You are given biased coin. Find unbiased decision out of it?

On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.

Google Interview Round 2 ::

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

Questions on my project please be prepare well about your project

How do you search for a word in a large database.

How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.

Google Interview Round 3 ::

You have given an array. Find the maximum and minimum numbers in less number of comparisons.

You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).

Google Interview Round 4 ::

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.

Ex: A="abcd" B="xyz" C="axybczd". answer is yes.

Given two sorted arrays A and B.

Find the intersection of these arrays A and B.

If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?

Google Interview Round 5 ::

If you get into Google, which products are you going to work on?

What is TCP, UDP. what is reliability, unreliability, give examples of these?

What is http protocol?

How does Google search engine works?

What is indexing, what is the input and output to it. how Google does that?