CareerCup

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.

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

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

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