Linkedin Interview Question
Software Engineer / DevelopersThe 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.
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;
}
}
Shouldn't you be using abs( mid*mid - n) > some threshold inside the if condition as well just you do for while loop ?
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;
}
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)
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;
}
}
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;
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;
}
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
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;
}
}
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;
}
It's a simple one
- gulusworld1989 October 21, 2010Use 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;
}
}