Linkedin Interview Question for Software Developers


Country: United States




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

Here's the log(n) binary search solution. I chose 0.000001 as an arbitrary precision.

public class Sqrt {

	public static void main(String...args) {
		System.out.println(findSquareRoot(4));
	}
	
	public static double findSquareRoot(double value) {
		double low = 0;
		double high = value;
		double mid = (low + high) / 2;
		while (Math.abs(value - mid * mid) > 0.000001) {
			if (mid * mid == value) {
				return mid;
			}
			if (mid * mid > value) {
				high = mid;
			} else {
				low = mid;
			}
			mid = (low + high) / 2;
		}
		return mid;
	}
}

- liuben10 April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

The solution I coded was the same as @liuben10 but there is a corner case that needs to be handled if n < 1.0, for instance sqrt(0.16) = 0.4 because the square root will be greater than the original number

public class Sqrt {

    public static void main(String...args) {
        System.out.println(findSquareRoot(0.16)); // 0.4
    }

    public static double findSquareRoot(double value) {
        double low = 0;
        double high = value;
        double mid = value > 1.0 ? (low + high) / 2 : 1.0;
        while (Math.abs(value - mid * mid) > 0.000001) {
            if (mid * mid == value) {
                return mid;
            }
            if (mid * mid > value) {
                high = mid;
            } else {
                low = mid;
            }
            mid = (low + high) / 2;
        }
        return mid;
    }
}

- joey April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

As per my opinion , there could be multiple ways of solving the same. Assuming the precision request is upto 4 decimal places. Out of the all options, 3rd approach is fastest but could not work in case number is <1

1. Naive Approach -
a. Identify the integer part
b. Identidy the fractional part

Here is the code in c#

public static double findsqrt(double num)
		{
			if(num < 0)
				throw new Exception("Invalid Input");

			double i =1, precision = 0.0001;
			//identify the integer part 
			for(i =1; i * i <=num; i++);
			
			//identify the fractional part
			for(--i; i*i <= num; i+=precision)
			
			return i-precision;
		}

2. Better Approach
a. Use Binary Search using low , mid , high
b. if number < 1 then low = number , high = 1 as 0.16 will have sqrt = 0.4
c. other wise low =1 and high = num and keep iterating till difference is of precision

public static double findsqrt(double num)
		{
			if(num <0 )
				throw new Exception(" Invalid input");
			
			double low =1, high = num, precision=0.0001;
			double mid;
			
			if(num <1)
			{
				low=num;
			 	high=1;
			}
			
			while(low <=high)
			{
				mid = (low+high)/2;
				if(mid * mid == num)
					return mid;
				else if ( mid* mid > num)
					high = mid-precision;
				else
					low = mid+precision;
			}
			return mid;
		}

3. Newton Raphson's Algorithm - It does not works for number less than 1
a. Take a guess which is less than sqrt of a number
b. Therefore, sqrt will be less than number/guess.
c. Keep averaging between these two numbers till difference is of precision.

public static double findsqrt(double num)
		{
			if(num <1)
				throw new Exception(" Invalid input);
			double guess = 1, precision =0.0001;
			
			while((num- guess* guess > precision) 
				|| ( guess* guess - num > precision))
			{
				guess = (guess + num/guess)/2;
			}
			return guess;
		}

- agarwalanshul1987 May 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Keep maintaining sum of odd numbers until the sum is greater than the given numer. ex: if 10 is given (1+3+5+7 = 16) is just greater than 10. (1+3+5=9) is smaller than 10
2. As the count of odder numbers added is 4, we can assume the square root of number will be between 3 and 4.
3. To find decimal part we can extrapolate the number. ex: in above case, 4-3/16-10 = 1/6=0.16
4. so square root is approx 3.16

- jugaad April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use "Newton's Iteration"

- celicom May 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Good catch @joey.. here is another neat way to deal with this by creating a wrapper and still using @liuben10 method.

public static double wrapper(double value) {
	if(value > 1.0 ) return findSquareRoot(value); 
	else return  1/findSquareRoot(1/value); // if value is <1 then compute 1/value first.  
    }

- Mukul September 05, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More