Blog # 78 : Google Interview Question 2012
Interview questions asked by Google Recruitment team after qualifying the first on-campus round comprising a written exam:
Round 1:
1) Given a database, a query returns correct output 99% of the time, however 1% of the time, it returns wrong output. What could be the possible reasons?
2) On a 2-D grid, the positions (x,y) of 3 persons are given. Find the meeting point such that sum of distances of each person from meeting point is minimized.
Now generalize this to N persons and solve.
3) A very long question related to hashing. I don't remember it.
Round 2:
1) Given a string of parantheses, check if the string is valid. ex: [[]] is valid, ][][ is not valid. How would you solve if the parantheses could be of different types like {,[,(
2) Given a layout like
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z
Your initial point is a. You want to form a string like "movie". WAP to find the sequence of moves consisting of letters 'U','D','L','R'
( normal conventions) that would form the movie. for example: for string "afg" sequence would be DR.
Round 3:
1) Given a number N, form all possible paranthesizations. like for N=3, there would be 5 possible parathesizations ( catalan numbers ).
Kept on asking to optimize time and space.
2) Given a 8X8 chess-board, there is a bishop placed on a square (i,j). You have to move to any square (x,y). In how many moves you could do it ?
Find the intemediate point.
3) Given an array of integers, where each element of array represents height of a building. Width of each building is 1. [ Think of it as histogram].
It starts raining, so water will get accumulated between some buildings. Find the amount of water that will be accumulated.
Round 4:
1) Given a rod of length L, there are some positions marked on rod at which the rod can be cut. The cost of cutting at any position is the current length of rod you are cutting. Like if the rod length is 10 and you can cut it at 4,9, cost of cutting at any position would be 10.
Find the minimum cost of cutting the rod.
2) What features would you suggest that should be added in Google+ to attract more users.
What signals would you use to determine any particular interest of a user.
More on similar topics, like suppose you have to design a page where top 100 posts by random users on Google+. What signals would you use to determine that. How would you rank the posts on that page.
Round 5:
1) Questions on final year project.
2) Design an interface on cache. Then I was asked incremental questions of the code that I have written. Pointed some issues and I was asked to correct them.
Round 1:
1) Given a database, a query returns correct output 99% of the time, however 1% of the time, it returns wrong output. What could be the possible reasons?
2) On a 2-D grid, the positions (x,y) of 3 persons are given. Find the meeting point such that sum of distances of each person from meeting point is minimized.
Now generalize this to N persons and solve.
3) A very long question related to hashing. I don't remember it.
Round 2:
1) Given a string of parantheses, check if the string is valid. ex: [[]] is valid, ][][ is not valid. How would you solve if the parantheses could be of different types like {,[,(
2) Given a layout like
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z
Your initial point is a. You want to form a string like "movie". WAP to find the sequence of moves consisting of letters 'U','D','L','R'
( normal conventions) that would form the movie. for example: for string "afg" sequence would be DR.
Round 3:
1) Given a number N, form all possible paranthesizations. like for N=3, there would be 5 possible parathesizations ( catalan numbers ).
Kept on asking to optimize time and space.
2) Given a 8X8 chess-board, there is a bishop placed on a square (i,j). You have to move to any square (x,y). In how many moves you could do it ?
Find the intemediate point.
3) Given an array of integers, where each element of array represents height of a building. Width of each building is 1. [ Think of it as histogram].
It starts raining, so water will get accumulated between some buildings. Find the amount of water that will be accumulated.
Round 4:
1) Given a rod of length L, there are some positions marked on rod at which the rod can be cut. The cost of cutting at any position is the current length of rod you are cutting. Like if the rod length is 10 and you can cut it at 4,9, cost of cutting at any position would be 10.
Find the minimum cost of cutting the rod.
2) What features would you suggest that should be added in Google+ to attract more users.
What signals would you use to determine any particular interest of a user.
More on similar topics, like suppose you have to design a page where top 100 posts by random users on Google+. What signals would you use to determine that. How would you rank the posts on that page.
Round 5:
1) Questions on final year project.
2) Design an interface on cache. Then I was asked incremental questions of the code that I have written. Pointed some issues and I was asked to correct them.
Posts
