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).
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
