## Facebook Interview Question for Interns

• 1
of 1 vote

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 vote

An easy and reasonably fast approach is to use binary search to the required precision

const double EPS = 0.0001;
double sqrt(double number) {
double left = 0.0, right = max(1, number), mid;
while (left + EPS < right) {
mid = (left + right) / 2.0;
if (mid * mid > number)
right = mid;
else
left = mid;
}
return left;
}

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.

Comment hidden because of low score. Click to expand.
3

Need to take care of cases when number < 1
sqrt(0.5) = 0.7071

Comment hidden because of low score. Click to expand.
0

thanks for pointing it out

Comment hidden because of low score. Click to expand.
0

Thanks for the answer..... Certainly very helpful. Is there any specific math principle behind this?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

How does this return an ans with precision of 0.0001?

Comment hidden because of low score. Click to expand.
0

Due to "while (left + EPS < right)"

if we find an interval [left, right] with range less than the epsilon, we reached that precision.

Comment hidden because of low score. Click to expand.
0

I think it does not work in case of very large numbers, where the double can not represent up to EPS. In order to avoid that we could do a fixed number of operations. around 1100 is good.

Comment hidden because of low score. Click to expand.
2
of 4 vote

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;
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

What is the value of n in above formulation? thanks!

Comment hidden because of low score. Click to expand.
0

I think your code has a minor defect, try getting the square root of 10 and see how it fails :P

You may need to avoid using the variable x at all within the function and instead ask "abs(x-x0*x0) > epsilon".

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

That should say O(1).
n arithmetic operations, where n is fixed for any input.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.