Facebook Interview Question
InternsCountry: India
Interview Type: Phone Interview
Thanks for the answer..... Certainly very helpful. Is there any specific math principle behind this?
Yes. We can apply Binary Search only in a monotonic function (increasing, decreasing, non-increasing or non-decreasing function).
We're applying Binary Search to the function F(x) = x^2. This function is strictly increasing (for x >= 0), so we know that for any 3 values A, B, C, with A < B < C, F(A) < F(B) < F(C)
So if F(mid) is larger than the number, we need to go for values less then mid. Go for larger values otherwise.
Due to "while (left + EPS < right)"
if we find an interval [left, right] with range less than the epsilon, we reached that precision.
Another pretty elegant solution is to use the Newton's method.
Newton's method is a method for finding roots of a function, making use of a function's derivative. At each step, a value is calculated as: x(step) = x(step-1) - f(x(step-1))/f'(x(step-1))
This might be faster than binary search (because in this question, precision is quite high, 4 decimal places). My implementation in Java:
public static int NewtonMethod(double x) {
double epsilon = 0.0001;
double x0 = 10;
while (Math.abs(x-x0)>epsilon) {
double a = x0*x0-n;
double r = a/(2*x0);
x = x0 - r;
x0 = x;
}
return x;
}
OK, one small modification for the while-loop, since we are not allowed to used any built-in functions, except the arithmetic operations.
double difference = x-x0 > 0? (x-x0) : (x0-x);
while (difference>epsilon) {
double a = x0*x0-n;
double r = a/(2*x0);
x = x0 - r;
x0 = x;
difference = x-x0 > 0? (x-x0) : (x0-x)
}
The method where u check the midpoints successively is called the bisection method (it's kind of like binary search).
It doesn't converge that fast, but these are not problems where we can label the efficiency with a big O(f(n)).
Newton's method converges faster. But this solution requires one to remember calculus.
I'm a math nerd so I know a cool solution:
For these problems there is always an implicity range of floating point values that one intent to use.
Using the range of floating point numbers we intend to use , we can use Taylor's remainder theorem to figure out the number of terms in the taylor expansion of sqrt(1+x) we need to achieve that precision for our inputs.
Then we can get the taylor polynomial of whatever degree we need, say n, inside our function.
To evaluate a polynomial of degree n, it seems like we require O(n^2) arithmetic operations because there is an x^n term.
But we can use Horner's scheme to make it O(n). For example:
Horner's scheme on a random quartic:
-3x^4 + 2x^3 + 2x + 6 = 6 + x(2 + x(2 + (-3(x))))
So to evaluate a polynomial of degree n, we only need O(n) operations.
So a solution is:
Find the taylor polynomial with enough terms to guarantee that precision on all inputs, then put then evaluate that polynomial internally using Horner's scheme.
This is O(n).
"know a solution" should really say "thought of one"
Because I am pretty sure a real math expert would do it differently (i.e., I doubt our calculators using bisection method or newton's method or even taylor polynomials to find sqrt(x)).
And also, the solution I state above is the Taylor polynomial for sqrt(1+x) about x=0. You cannot do the Taylor polynomial for sqrt(x) at x=0 as it is not differentiable at x=0. Not a big deal, you just let x=(input)-1 inside the function.
using Newton Raphson Method, it will converge quadratically
#include<iostream>
using namespace std;
const int EPS=0.0001;
double root(double data) {
double a = data;
double b = 1.0;
while(a - b > EPS) {
cerr << a << " " << b << endl;
a = (a+b) / 2;
b = data / a;
}
return b;
}
int main() {
double i = 10;
double res = root(i);
cout << res << endl;
return 0;
}
public static double sqrt(double number, double precision = 0.0001)
{
if (number < 0)
{
throw new ArgumentException(_noSquareRootOfNegativeNumberForYou);
}
double candidate = number/2;
double previousCandidate = number;
double delta = 0;
while ((Math.Abs(delta = candidate*candidate - number)) > precision)
{
var candidateSavedTemporarily = candidate;
candidate = delta < 0 ? (previousCandidate + candidate)*.75 : candidate*.75;
previousCandidate = candidateSavedTemporarily;
}
return candidate;
}
An easy and reasonably fast approach is to use binary search to the required precision
I know there is a method to find the square root by hand but I don't know the details. That method might be more efficient, but I think binary search is probably the intended answer in an interview.
- Miguel Oliveira September 14, 2013