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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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;

}``````

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

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

}

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

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Newton's method

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``````

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");
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;

}
}``````

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

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.

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