Linkedin Interview Question
Software DevelopersCountry: United States
The solution I coded was the same as @liuben10 but there is a corner case that needs to be handled if n < 1.0, for instance sqrt(0.16) = 0.4 because the square root will be greater than the original number
public class Sqrt {
public static void main(String...args) {
System.out.println(findSquareRoot(0.16)); // 0.4
}
public static double findSquareRoot(double value) {
double low = 0;
double high = value;
double mid = value > 1.0 ? (low + high) / 2 : 1.0;
while (Math.abs(value - mid * mid) > 0.000001) {
if (mid * mid == value) {
return mid;
}
if (mid * mid > value) {
high = mid;
} else {
low = mid;
}
mid = (low + high) / 2;
}
return mid;
}
}
As per my opinion , there could be multiple ways of solving the same. Assuming the precision request is upto 4 decimal places. Out of the all options, 3rd approach is fastest but could not work in case number is <1
1. Naive Approach -
a. Identify the integer part
b. Identidy the fractional part
Here is the code in c#
public static double findsqrt(double num)
{
if(num < 0)
throw new Exception("Invalid Input");
double i =1, precision = 0.0001;
//identify the integer part
for(i =1; i * i <=num; i++);
//identify the fractional part
for(--i; i*i <= num; i+=precision)
return i-precision;
}
2. Better Approach
a. Use Binary Search using low , mid , high
b. if number < 1 then low = number , high = 1 as 0.16 will have sqrt = 0.4
c. other wise low =1 and high = num and keep iterating till difference is of precision
public static double findsqrt(double num)
{
if(num <0 )
throw new Exception(" Invalid input");
double low =1, high = num, precision=0.0001;
double mid;
if(num <1)
{
low=num;
high=1;
}
while(low <=high)
{
mid = (low+high)/2;
if(mid * mid == num)
return mid;
else if ( mid* mid > num)
high = mid-precision;
else
low = mid+precision;
}
return mid;
}
3. Newton Raphson's Algorithm - It does not works for number less than 1
a. Take a guess which is less than sqrt of a number
b. Therefore, sqrt will be less than number/guess.
c. Keep averaging between these two numbers till difference is of precision.
public static double findsqrt(double num)
{
if(num <1)
throw new Exception(" Invalid input);
double guess = 1, precision =0.0001;
while((num- guess* guess > precision)
|| ( guess* guess - num > precision))
{
guess = (guess + num/guess)/2;
}
return guess;
}
1. Keep maintaining sum of odd numbers until the sum is greater than the given numer. ex: if 10 is given (1+3+5+7 = 16) is just greater than 10. (1+3+5=9) is smaller than 10
2. As the count of odder numbers added is 4, we can assume the square root of number will be between 3 and 4.
3. To find decimal part we can extrapolate the number. ex: in above case, 4-3/16-10 = 1/6=0.16
4. so square root is approx 3.16
Good catch @joey.. here is another neat way to deal with this by creating a wrapper and still using @liuben10 method.
public static double wrapper(double value) {
if(value > 1.0 ) return findSquareRoot(value);
else return 1/findSquareRoot(1/value); // if value is <1 then compute 1/value first.
}
Here's the log(n) binary search solution. I chose 0.000001 as an arbitrary precision.
- liuben10 April 28, 2016