Linkedin Interview Question for Software Engineer / Developers






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

It's a simple one
Use newton-raphson's method for finding square root.
import java.util.*;
class SQRT
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter a positive no. to find sqrt");
float n=sc.nextFloat();
if(n<0)
{
System.out.println("negative don't have square roots");
System.exit(0);
}
float y=sqrt(n);
System.out.println("sqrt is "+y);
}
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.00001)
{

if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;
}
return mid;
}
}

- gulusworld1989 October 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The general strategy is to use binary halving tacnic. Start with 1 and n/2.

Complexity will be o(logn) in general since it will converge pretty fast.

- fydango March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just putting gulus' code into format for visibility...

import java.util.*; 
class SQRT 
{ 
public static void main(String args[]) 
{ 
Scanner sc=new Scanner(System.in); 
System.out.println("Enter a positive no. to find sqrt"); 
float n=sc.nextFloat(); 
if(n<0) 
{ 
System.out.println("negative don't have square roots"); 
System.exit(0); 
} 
float y=sqrt(n); 
System.out.println("sqrt is "+y); 
} 
static float sqrt(float n) 
{ 
float low=0,high=n; 
float mid=(low+high)/2; 
while(Math.abs(mid*mid-n)>0.00001) 
{ 

if(mid*mid<n) 
low=mid; 
else if(mid*mid>n) 
high=mid; 
mid=(low+high)/2; 
} 
return mid; 
} 
}

- Anonymous June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't you be using abs( mid*mid - n) > some threshold inside the if condition as well just you do for while loop ?

- harish October 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually the high variable can be set to n/2 + 1 since the sqrt of a number will be no more than n/2 + 1

- ysyyork November 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implement babylonian square root calculation method.
Complexity is O(log2(n)) but if the closest 2^k number is found in constant time then complexity is O(log2log2(n))
The code pasted below is fine but for some reason careercup's editor adds extra random semi colons. So I've pasted the code at
http://ideone.com/8nHLeH
Also, even though I used 0.000001 for stopping. the algorithm is already converged by then

/*! Implementation of Babylonian method for square root
    Algorithm:
		Find closest 2^k number to n
		initialize xprev = 2^k
		Iteratively compute 0.5*(xprev + (n/xprev) until the difference from previous is < 0.000001
		//Refer to Babylonian square root calculation

 * Approximated Complexity : O(1.5*log2(n) + log2log2(n)) => O(log2(n)). If the closest 2^k number is found in constant time then complexity is O(log2log2(n))
 * Disclaimer: This code is ONLY implemented for understanding and demonstrating algorithm on valid inputs.
 */
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	long S = 22811111;
	long tempS = S;
	long X0 = 1;
	float Xcurr, Xprev, diff;
	int numIterations = 0;
	int numBits = 0;
	//Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
	//shift bits to find the closest 2^k to the given number

	while(tempS > 0){
		tempS=tempS>>1;
		++numBits;
                ++numIterations;
	}
	numBits = floor(numBits/2)+1;
	while(numBits > 0){
		X0=X0<<1;
		--numBits;++numIterations;
	}
		
	Xcurr = X0;
	do{
		Xprev = Xcurr;
		Xcurr = .5*(Xprev + (S/Xprev));
		++numIterations;
	}while((Xprev-Xcurr)>0.000001);
	cout<< "Square Root of "<< S<< " is "<< Xcurr<<endl;
	cout<<endl<<"Complexity calculation: O(1.5*log2(n) + log2log2(n)): : "<<ceil(log2(S))+(ceil(log2(S))/2+1)+ceil(log2(log2(S)))+1<<endl;
	cout<< "Number of iterations :" <<numIterations;
	
}

- chennavarri October 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. Find the closest perfect square to the number.
2. Implement the Babylonian Approach to find the sqrt.

void squareRoot(long num){

long newGuess = 0;
double numDiv = 0;
long tempNum = 0;
long guess =1;
float fGuess, fNewGuess;

tempNum = num;
while(tempNum > 0){
tempNum = tempNum >> 1;
numDiv++;
}
numDiv = floor(numDiv/2);

while(numDiv > 0){
guess = guess << 1;
numDiv--;
}
fNewGuess = guess;

do{
fGuess = fNewGuess;
fNewGuess = (fGuess + num/fGuess) * 0.5;

}while(fGuess- fNewGuess > 0.00001);

cout << "Square root " << fNewGuess;
}

Complexity is Log(n)

- Richa Aggarwal October 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

was this phone or in office?

- Swati November 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

package linkedIn;

public class squareRoot {
public static void main(String[] args) {
System.out.println(calcSqrt(18));
}

private static float calcSqrt(int number) {
int k = 1;
while( k * k <= number) {
k++;
}
if (k != 1) {
k--;
}
if (k * k == number) {
return k;
}
float oldGuess = k;
float newGuess = k;
do {
oldGuess = newGuess;
newGuess = getNewGuess(oldGuess, number);
}while ( newGuess - oldGuess > 0.0001);
return newGuess;

}

private static float getNewGuess(float oldGuess , int number) {
float newGuess = number / oldGuess;
return (oldGuess + newGuess)/2;
}

}

- sk October 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can USE newton's method :-

We have to find square root of A then
we define two functions

f(x) = x^2 - A;
and f'(x) = 2*x;

Now

temp = 1;
k=1;
while( temp <= A  )
     temp = k*k;
     k++;

if( k!= 1)
    k--;
    if( k*k == A ) return k;


X = k;
Y = INT_MAX;

while( (X - Y)> 0.00001 )  
       Y = X;
       X = X - f(X)/f'(X);

return X;

- Aditya October 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream.h>

void main()
{
  std::cout<<"this is test code"<<(5+10)<<"\n";
return;
}

- testing October 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

srry previous code was messy . here is the clear code

static float sqrt(float n)
	{
		float low=0,high=n;
		float mid=(low+high)/2;
		while(Math.abs(mid*mid-n)>0.00001)
		{
			if(mid*mid<n)
				low=mid;
			else if(mid*mid>n)
				high=mid;
			mid=(low+high)/2;
		}
		return mid;
	}

- gulusworld1989 October 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code will not work for the n less than 0.

- Anonymous February 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It should not work for n < 0. It's impossible to find the square root of a negative number.

- venividivamos August 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Newton's method

- pansophism December 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just in case, if someone needs to read this code in ruby using Newton's Raphson Method:

def sqrt(n)
  low = 0
  high = n
  mid = ((low+high)/2).to_f
  while (mid*mid-n).abs.to_f > 0.00001
    if ((mid*mid).to_f < n)
      low = mid
    elsif (mid*mid>n) 
      high = mid
    end
    mid = ((low + high)/2).to_f
  end
  return mid
end

- Ali Ibrahim November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package interv.eBay;

public class CheckPerfectSquare {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CheckPerfectSquare cPS = new CheckPerfectSquare();
		int input = 64;
		System.out.println("Solution: Binary Search Version 1");
		if (cPS.binarySearchCheck(input))
			System.out.println("Yes the number is perfect square");
		else
			System.out.println("No the number is not a perfect square");

		System.out.println("Solution: Binary Search Version 2");
		if (cPS.binarySearchCheck2(input, 0, input))
			System.out.println("Yes the number is perfect square");
		else
			System.out.println("No the number is not a perfect square");
		System.out.println("Solution: Odd number Addition");
		if (cPS.oddNumberAddition(input))
			System.out.println("Yes the number is perfect square");
		else
			System.out.println("No the number is not a perfect square");

	}

	private boolean binarySearchCheck(int n) {
		// TODO Auto-generated method stub
		if (n == 1)
			return true;
		if (n < 4)
			return false;
		int min = 2;
		int max = n / 2;
		int div, res;
		do {
			div = (min + max) / 2;
			res = n / div;
			if (res * res == n)
				return true;
			else {
				if (res < div) {
					min = res;
					max = div;
				} else {
					min = div;
					max = res;
				}
			}
		} while (max > (min + 1));
		return false;
	}

	private boolean binarySearchCheck2(int n, int low, int high) {
		// TODO Auto-generated method stub
		if (low > high)
			return false;
		int mid = (low + high) / 2;
		if (mid * mid == n)
			return true;
		else {
			if ((mid * mid) > n)
				return binarySearchCheck2(n, low, mid - 1);
			else
				return binarySearchCheck2(n, mid + 1, high);
		}
	}

	private boolean oddNumberAddition(int n) {
		// TODO Auto-generated method stub
		int oddInteger = 1;
		int squareValue = 1;
		while(squareValue<=n){
			if(squareValue==n)
				return true;
			else{
				oddInteger=oddInteger+2;
				squareValue = squareValue+oddInteger;
			}
		}
		return false;

	}
}

- sLion September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

double cmp(double l, double r)
 {
     double e = 1e-5;
     if (l < r - e)return -1;
     if (l > r + e)return 1;
     return 0;
 }
 /*
  * square root of a number
  * use binary search, predicate is, if m * m >= x, for all n >= m, n * n >= x
  * l = 1, r = x >> 1
  * stopping criteria: l >= r
  * case: x = 0 , return 0
  *     : x = 1, return 1
  *     : x = 4, return 2
  *     : x = 9, return 3
  */
 #define MAX_ITERATIONS 1000
 double square_root(double x)
 {
     assert(x >= 0);
     if (cmp(x, 1.0) <= 0)return x;
     double l, r;
     l = 1;r=(cmp(x, 4.0) >= 0 ? x>>1: x);
     int iteration = 0; 
     double alpha = 1.0;
     double search_space = (r - l);
     double prev_search_space = (r - l) * 2;
     while(cmp(l, r) < 0 && (iteration++ < MAX_ITERATIONS || (prev_search_space - search_space) * 100/prev_search_space < alpha))
     {
         prev_search_space = search_space;
         double m = l + (r - l ) >> 1;
         if (cmp(m * m, x) == 0)return m;
         if (cmp(m * m , x) > 0)r = m;
         else l = m;
         search_space = r - l;
     }
     //cmp(l, r) > =0
     return l; 
 }

- wjian@yahoo-inc.com September 17, 2014 | 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