How to find square root of a number in Java - Algorithm Interview question

Write a program to calculate the square root of a number in Java or C++ is one of the popular coding interview questions from Programming job interviews both on tech companies like Facebook, Amazon, and investment banks like Citibank and Bank Of America etc. The problem may look easy because you might know how to find the square root of a number but it's not. In fact, it's one of the tricky questions you would encounter in programming job interviews. The first hurdle is do you really remember how to calculate square root by hand? Many programmers don't. I know they have learned it past but when you ask them to calculate square root by hand, many won't remember the algorithm they have learned in school or college.

Some of them will answer that they will use the Math.sqrt() function to calculate the square root in Java,  as shown here, which is also right but the interviewer is not asking about that. he is asking you to develop your own method using algorithms to calculate the square root.

Some of the more intelligent programmers will then come up with something like they will use Newton's method to calculate the square root. Well, go on, if you remember how Newton's method works and you can explain that to Interviewer, who might not have a good idea about it.


So what leaves? Well, when this question was asked to me long back I had no clue about it. Like many others, I had also forgotten the algorithm to calculate square root by hand, but suddenly it strike me that x = sqrt(y) and x^2 = y i.e. here X is the square root and you can possibly find the square root by computing square of x and checking it is less than or equal to Y. Once it greater than Y, you can stop the loop. This looked possible to me and I started coding.

I wrote something like that
public static float root(int number) {
    float root = 0.0f;
    float square = root;
    while (square < number) {
      root++;
      square = root * root;
    }
    return root;
  }

Output
4
square root: 2.0
9
square root: 3.0
16
square root: 4.0
25
square root: 5.0
26
square root: 6.0

Even though it's not efficient and works only for a perfect square, I was happy to move forward on a problem I have not prepared. The Interviewer was then asked that for non-perfect number square root is off by 1, how can you correct that? I said we can reduce the gap by using a custom precision. Since we are keep increasing the next possible square root by 1, we are getting an answer which is far from approximate, if we use 0.5 or 0.1, we'll get a more approximate answer as shown below.


public static float root(int number) {
    if (number < 0)
      return -1;
    if (number == 0 || number == 1)
      return number;
    float root = 0.0f;
    float precision = 0.1f;
    float square = root;
    while (square < number) {
      root = root + precision;
      square = root * root;
    }
    return root;
  }

Output
4
square root: 2.0000002
5
square root: 2.3
6
square root: 2.4999998
7
square root: 2.6999996
8
square root: 2.8999994
9
square root: 3.0999992

Though the answer was not perfect and the result was not very approximate, he gets the idea that by using lower precision we can make the square root more approximate and correct, but he was looking at something else as well. He asks me about the time complexity of the solution and I said it is linear because we are inching towards right answer one step at a time.

Can we make it better? Well, I knew that logarithmic time is better than linear i.e. O(logN) is better than O(N) and when I think logN, the algorithm which comes in my mind was a binary search. Why not use binary search to find the square root? That was another small step in right direction and the following solution emerges from that:

public static float sqrt(int number) {
    if (number < 0)
      return -1;
    if (number == 0 || number == 1)
      return number;

    float start = 0.0f;
    float end = number;
    float precision = 0.001f;
    float middle = start;
    float difference = (float) Math.abs(Math.pow(middle, 2) - number);

    while (difference >= precision) {
      middle = (start + end) / 2.0f;

      if (Math.pow(middle, 2) > number) {
        end = middle;
      } else {
        start = middle;
      }

      difference = (float) Math.abs(Math.pow(middle, 2) - number);
    }
    return middle;
  }

Output
4
square root: 2.0
5
square root: 2.236023
6
square root: 2.449585
7
square root: 2.645935
8
square root: 2.8283691
9
square root: 3.0000916

Now, the algorithm is better in terms of runtime but it still has one critical problem which could lead to program running forever, depending upon precision and square root of a number. For example, if you change the precision to 0.00000001f and try to calculate the square root of 5, the program will go into an infinite loop because the condition difference >= precision will never become false.

Here, instead of greater than operator (>), we need to use the Float.compareTo() method to compare floating point values. I have also explained that right way to compare float values in Java is by using Float.compareTo() method on my earlier article Why you shouldn't use == with float and double in Java?

This is one more reason why you should alway use library methods for doing such primitive task as advised by Joshua Bloch in Effective Java. I leave it to you how you can avoid infinite loop while comparing float in Java here. It's a good topic to research and learns.

Btw, this solution might help you to land a job in Java's application development role but not in a game programming domain or quant domain where they put a lot of emphasis on the fast and accurate algorithm. You might get some points here by coming up with a solution and improving it a bit which signifies that you have good learning ability, but video games are different bits. They are quite math intensive especially 3D games which do a lot of vector maths and put a lot of emphasis on performance even with modern hardware like NVIDIA graphics card and fast CPU like intel i7. Don't you want your MineCraft and Quack fast and accurate?


As I said in the first paragraph, this problem might look easy but it is not and require a good understanding of floating point arithmetic in the programming language you solve. You also need to know approximation algorithms like Newton-Raphson algorithm which starts with a guess and refines it with iteration.

Here is a sample flowchart of calculating square root using Newton-Raphson algorithm:

How to find square root of a number in Java - Algorithm Interview question


Other Algorithmic Interview Questions you may like to explore
  • How to swap two numbers without using the third variable? (answer)
  • How to check if two rectangles intersect with each other in Java? (solution)
  • How to implement sieve of Eratosthenes algorithm in Java? (solution)
  • How to add two numbers without using plus operator in Java? (answer)
  • How to implement binary search tree in Java? (solution)
  • How to implement pre-order traversal of a binary tree in Java? (solution)
  • How to implement binary search algorithm in Java? (solution)
  • How to implement in-order traversal in Java? (solution)
  • How to print all leaf nodes of a binary tree in Java? (solution)
  • How to implement iterative quicksort in Java? (solution)
  • Write a program to implement bubble sort in Java? (solution)
  • How to implement insertion sort algorithm in Java? (answer)


Further Reading
Introduction to Algorithms by Thomas H. Cormen
Algorithm Design Manual by Steven Skiena
Khan Academy Course of Algorithms


2 comments :

Anonymous said...

square root of 6 is 36

Javin Paul said...

@Anonymous, should be other way around, square root of 36 is 6, do you see that in article?

Post a Comment