For many technical interviews in big companies, one question might be asked frequently, which is how to compute a number's square root. Based on my experience, Yahoo and Linkedin interviewers like it in the first phone screen. It looks so simple that many people would neglect some nature behind its appearance. In my blog, I will focus on the analysis part and spend some time on testing because I believe that people can not give perfect coding solution without solid analysis and sound testing cases. Let's get into it.
Problem description
Given you a number, compute its square root.
Analysis
1) Before we start, we have to truly and totally understand what the meaning of the problem is. More importantly, in the interview process, we should know what method or technology the interviewers want us to show to them. So ask them conditions in the problem to clear ambiguities. In this case, what kind of number is as the input, integer or float? Is it a perfect square root problem? What time complexity do they want, linear, lg(n) or constant? etc. Since the integer is the special case, we consider the input to be double. And we would be given an error for the result. Btw, the perfect square root problem means if the input is an integer, like 9, how to find its square root 3 but there is no perfect root for 12.
2) There are two basic ways to solve this problem. One is to use binary search to narrow the searching space from 0 to n, the input. The other one is Babylonian method derived from Newton's method. The Binary search is lg(n) time while the other is constant. We talk about it later.
a) Binary search
I think the reason why many interviewers like asking it is to test how good you understand and apply the binary search technique. Basically, computing sqrt of a number is a searching process because we already know the result must be in the range from 0.0 to n. Also, of course, all the numbers between them are sorted. Therefore, binary search is the first way we can think of. Here, there are two things we should keep in mind. One is that the number is double not integer or index of an array so we can not use the classic binary search to increase middle or decrease middle. Instead, we let middle=begin to keep searching on the right and middle=end on the left. The second is we should use error checking to keep the loop running. More details can be seen in the following code:
double Sqrt(double n, double error) {
if (n < 0.0) {
return -1.0; // indicate there is no sqrt for negative number
}
if (n == 0.0) {
return 0.0;
}
int begin = 0.0;
int end = n;
int mid;
do {
mid = begin + (end-begin)/2.0;
if (mid * mid < n) {
begin = mid;
} else if (mid * mid > n) {
end = mid;
}
//int next_mid = begin + (end-begin)/2.0;
} while (fabs(mid*mid - n) > error);
//} while (fabs(mid - next_mid) > error);
return mid;
}
b) Babylonian method (Newton's method)
As we know, Newton's method is used to compute the approximation of one root of a real value function. Here, we just touch a little bit about how to derive the approximation equation for computing sqrt. Let f(x) = x^2 - n, where the f(x) is defined in the interval [0.0, n]. Suppose we have an approximation xn so the equation of the tangent line to the curve y = f(x) at the point x=xn is:
y=f'(xn)(x-xn)+f(xn).
Then the x-intercept of this line is used as the next approximation to the root x(n+1). So we can get:
0=f'(xn)(x(n+1)-xn)+f(xn).
After some manipulations, we can get:
x(n+1) = xn-f(xn)/f'(xn).
Since f(xn)=xn^2-n and f'(xn)=2xn, the final approximation equation for sqrt is:
x(n+1)=(xn+n/xn)/2.
More details can be seen in the following code:
double Sqrt(double n, double error) {
if (n < 0.0) {
return -1.0; // indicate there is no sqrt for negative number
}
if (n == 0.0) {
return 0.0;
}
double x = n;
double y = 1.0; // y = n/x=n/n=1.0
while(x - y > error) {
x = (x + y)/2;
y = n/x;
}
return x;
}
3) Complexity
a) Binary search method:
It is clearly lg(n) but why? First we choose mid=n/2, which is the first iteration. At this time, we bisect the whole range and the difference between mid and the exact square root is less than and equal to n/2. Then we pick a 1/4 part of the original range n and so on until the difference is less than and equal to the error. So in mathematical form, it should be:
n/2^k >= error.
Then we can get:
k <= lgn-lg(error), which means k = O(lgn).
b) Newton's method:
It is constant time. Based on experiment, it can get convergence after less than 10 times. More details are available on Babylonian method page of Wikipedia.
Test
-1, 0, 0.25, 1, 100000000000
Remember we should consider more to guarantee our program more robust. For example, what about negative input number? Or the number is out of range of double? So we should add the some constraints before we start computing.
Reference
1. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
2. http://en.wikipedia.org/wiki/Newton%27s_method
3. Introduction to Algorithms
Problem description
Given you a number, compute its square root.
Analysis
1) Before we start, we have to truly and totally understand what the meaning of the problem is. More importantly, in the interview process, we should know what method or technology the interviewers want us to show to them. So ask them conditions in the problem to clear ambiguities. In this case, what kind of number is as the input, integer or float? Is it a perfect square root problem? What time complexity do they want, linear, lg(n) or constant? etc. Since the integer is the special case, we consider the input to be double. And we would be given an error for the result. Btw, the perfect square root problem means if the input is an integer, like 9, how to find its square root 3 but there is no perfect root for 12.
2) There are two basic ways to solve this problem. One is to use binary search to narrow the searching space from 0 to n, the input. The other one is Babylonian method derived from Newton's method. The Binary search is lg(n) time while the other is constant. We talk about it later.
a) Binary search
I think the reason why many interviewers like asking it is to test how good you understand and apply the binary search technique. Basically, computing sqrt of a number is a searching process because we already know the result must be in the range from 0.0 to n. Also, of course, all the numbers between them are sorted. Therefore, binary search is the first way we can think of. Here, there are two things we should keep in mind. One is that the number is double not integer or index of an array so we can not use the classic binary search to increase middle or decrease middle. Instead, we let middle=begin to keep searching on the right and middle=end on the left. The second is we should use error checking to keep the loop running. More details can be seen in the following code:
double Sqrt(double n, double error) {
if (n < 0.0) {
return -1.0; // indicate there is no sqrt for negative number
}
if (n == 0.0) {
return 0.0;
}
int begin = 0.0;
int end = n;
int mid;
do {
mid = begin + (end-begin)/2.0;
if (mid * mid < n) {
begin = mid;
} else if (mid * mid > n) {
end = mid;
}
//int next_mid = begin + (end-begin)/2.0;
} while (fabs(mid*mid - n) > error);
//} while (fabs(mid - next_mid) > error);
return mid;
}
b) Babylonian method (Newton's method)
As we know, Newton's method is used to compute the approximation of one root of a real value function. Here, we just touch a little bit about how to derive the approximation equation for computing sqrt. Let f(x) = x^2 - n, where the f(x) is defined in the interval [0.0, n]. Suppose we have an approximation xn so the equation of the tangent line to the curve y = f(x) at the point x=xn is:
y=f'(xn)(x-xn)+f(xn).
Then the x-intercept of this line is used as the next approximation to the root x(n+1). So we can get:
0=f'(xn)(x(n+1)-xn)+f(xn).
After some manipulations, we can get:
x(n+1) = xn-f(xn)/f'(xn).
Since f(xn)=xn^2-n and f'(xn)=2xn, the final approximation equation for sqrt is:
x(n+1)=(xn+n/xn)/2.
More details can be seen in the following code:
double Sqrt(double n, double error) {
if (n < 0.0) {
return -1.0; // indicate there is no sqrt for negative number
}
if (n == 0.0) {
return 0.0;
}
double x = n;
double y = 1.0; // y = n/x=n/n=1.0
while(x - y > error) {
x = (x + y)/2;
y = n/x;
}
return x;
}
3) Complexity
a) Binary search method:
It is clearly lg(n) but why? First we choose mid=n/2, which is the first iteration. At this time, we bisect the whole range and the difference between mid and the exact square root is less than and equal to n/2. Then we pick a 1/4 part of the original range n and so on until the difference is less than and equal to the error. So in mathematical form, it should be:
n/2^k >= error.
Then we can get:
k <= lgn-lg(error), which means k = O(lgn).
b) Newton's method:
It is constant time. Based on experiment, it can get convergence after less than 10 times. More details are available on Babylonian method page of Wikipedia.
Test
-1, 0, 0.25, 1, 100000000000
Remember we should consider more to guarantee our program more robust. For example, what about negative input number? Or the number is out of range of double? So we should add the some constraints before we start computing.
Reference
1. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
2. http://en.wikipedia.org/wiki/Newton%27s_method
3. Introduction to Algorithms
评论
发表评论