Google Fresher Interview Questions – round 1
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.
Solution:
The duality algorithm would work. Find the point of intersection with maximum no of lines incident on it in the dual plane. It works in O(n^2).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
Solution:
min=a[0];
for(i=1;i<n;i++)
{
if( a[i]<min )
{
min = a[i]; -------eq(i)
}
}Once the variable min is initialized,the probability of a[i] < min is 1/2. So the expected number of occurances of equation i is (n-1)/2 .
Tags: google, Interview, Question
This entry was posted
on Monday, May 11th, 2009 at 7:46 pm and is filed under Articles.
You can follow any responses to this entry through the RSS 2.0 feed.You can leave a response, or trackback from your own site.
Subscribe to our blog through our RSS feed or email to receive updates on more posts like this. post on your favourite social networking or media site to let others know about this post. Help us generate more buzz by submitting/voting for this post with the following buttons.
