Interview Question

Software Engineer Interview Menlo Park, CA

Write a function that finds the square root of a decimal

  number.
Tags:
technical, algorithm
Answer

Interview Answer

4 Answers

1

A binary search with a constraint for precision. We should also take care of the interval (0.00, 1.00).

Interview Candidate on Sep 2, 2012
0

// iterative

(function(n){
    var lo=0;
    var hi=n;
    var tries=500;
    var prev;
    while(tries--){
        var curr=hi-((hi-lo)/2);
        var prd=curr*curr;
        if(prd===n || prev==curr){
            break;
        }
        prd>n ? hi=curr : lo=curr;
        prev=curr;
    }
    console.log(curr, curr*curr, 500-tries)
})(64)

grim face on Sep 7, 2012
0

// recursive with closure use

(function(n){
    var lo=0;
    var hi=n;
    var tries=500;
    var prev;
    function rec(){
        var curr=hi-((hi-lo)/2);
        var prd=curr*curr;
        if(prd===n || prev==curr || !tries--){
            return curr;
        }
        prd>n ? hi=curr : lo=curr;
        prev=curr;
        return rec()
    }
    var result = rec();
    console.log(result, result*result, 500-tries)
})(25)

grim face on Sep 7, 2012
2

For the above, I would set my high to be the max(x, 1), Let say's one call any of your functions with 1/4, or with any 0 < x < 1 both implementation will fail

My approach would be the Newton implementation of it

(function(n, epsilon){
    If (x < 0)
        return;

    if(precision <=0)
        return;

    var guess = x/2;
    var diff = guess^2 - x; //guess^2 I mean here guess square
    var counter = 1;
    while((diff -x > epsilon) && (epsilon <=100)){
        guess = guess^2 - (diff)/2*guess;
        diff = guess*guess - x;
        counter++;
    }

    if(counter > 100)
        return;

    return guess;

})

Anonymous on Sep 16, 2012

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up