- Asked about my project. Prepare well to answer any type of questions that may arise in your project.They will just ask to explain about any one of the projects listed in your resume.
- In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now
given these n points.Find the maximum number of collinear points. - Write the code for finding the min of n number.
- I gave:
for(i=0;i<n;i++)
{
if( a[i]<min )
{
min = a[i] ---- eq(i)
}
} - Given that n numbers are from random sampling how many times (probability) does
the line (i) be executed
- Google Interview Round 2:
- What is Bottom up parsing and what is top down parsing?
- What is a symbol table?
- There is a portal with two billion users registered. If you store all the 2 billion users in a conventional databases it will take more time to retrieve the data about a particular user when that user tries to login. How do you handle this situation to make sure that the user gets the response quickly.
- There are 8 identical balls. One of them is defective. It could be either heavier of lighter. Given a common balance how do you find the defective ball in least number of weighings.
- You have all the English words with you. you would like to manage a dictionary so that you can look up when ever you have doubt. Which data structure would you like to use and why?
- Asked me about all the details of hash table and heaps.
- Write code for finding number of zeros in n!
Google Interview Round 3 :
Write C++ class for the game Connect Four. [Connect Four (also known as Plot Four, Four In A Row, and Four In A Line) is a two-player board game in which the players take turns in dropping discs into a seven column grid with the objective
of getting four of one's own discs in a line.]
- Given a stack and an input string of 1234.At any point you can do anyone of
the follow
- i. take the next input symbol and Enque.
ii. you can pop as many as you can. When ever you
pop an element it will be printed
(you cannot pop from an empty stack)
- Give an example of one permutation that this data structure cannot generate.
For Example:
1234 is input.
First push all 1,2,3,4 on to stack and pop all.
output will be 4321.- It means that this data structure can generate 4321.
- Question 2 was pretty easy right? Now do again the same question but the
data structure and input are different
Input: 12345
Data Structure: Deque ( Doubly Que )
Note: Deque is a data structure into which you can do enque
and deque from both sides.Some thing like this
__________________________________
enque ---> <----enque dequeue <---- ----->dequeue
__________________________________ - Classic Egg Puzzle Problem
You are given 2 eggs.You have access to a 100-store building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-store building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
- Google Interview Round 4 :
- Given n non overlapping intervals and an element. Find the interval into which this element falls.
- Worst case is take all intervals one at a time and see whether the element lies in the interval or not.It will take O(n). So please give a solution that will do better than O(n).
- Now given that the n intervals are overlapping then how do you solve? The interviewer was concentrating more on the complexities (running, memory ..)
- Write code for Random Sort?
Algorithm is explained:
Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.
- Google Interview Round 5:
This is Manager Round - Tell me an achievement that you have done in your non academics
- Tell me about one of your project
- Take a feature of C++ and tell me how you have implemented it in one of your project
- By taking one of your project as example tell me how you have taken care of software engineering where you would have handled more data
- There is a routine already written to find the subtraction of two sets ( set A - set B) . Write test cases for testing it.Tell me how do you test the test cases you have written?
- There is a printed book. The page numbers are not printed. Now the printing of page numbers is being done separately. If the total number of digits printed is 1095 then how many pages does the book have?
