Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public double findSquareRoot(double val){
double DELTA_GAP=0.00001;
double start = 0, end = val, root=val;
while(end-start>DELTA_GAP){
root = (end-start)/2 +start;
if(root * root > val){
end = root;
}else{
start = root;
}
System.out.println(root+" ("+start+","+end+")");
}
return root;
}
after read sandeep's generic implementation, add a else{} to above square solution.
...
double pow = root * root;
if(pow > val){
end = root;
}else if(pow < val){
start = root;
}else{//this branch should be caught, otherwise you cannot get "exact" root, like findSquareRoot(2), you cannot get 2 as result
System.out.println(root+" ("+start+","+end+")");
return root;
}
Generalizing the above solution further:
//Given a value (in double) return its nth root.
public class FindNthRoot {
public static double nthRoot(double number, int n, double tolerance) {
double start = 0;
double end = number;
double root = start + (end - start) / n;
int iterations = 1;
//invariant: (end - start) > tolerance
while ((end - start) > tolerance) {
double pow = nthPower(root, n);
if (pow > number) { // 12 is the number then initial root would be 6 and pow is 36 for n = 2 in which case pow > number
end = root; // reduce end to root i.e. 6
} else if (pow < number) { // 9 < 12
start = root; // reset start
} else {
return root;
}
root = start + (end - start) / n;
iterations++;
}
System.out.println("start:" + start + ", " + "end: " + end + ", " + "iterations:" + iterations);
return root;
}
private static double nthPower(double num, int n) {
double result = 1;
for (int i = 0; i < n; i++) {
result = result * num;
}
return result;
}
public static void main(String[] args) {
System.out.println(FindNthRoot.nthRoot(36.4345, 2, 0.000010));
System.out.println(FindNthRoot.nthRoot(27.4345, 3, 0.000010));
System.out.println(FindNthRoot.nthRoot(256.4345, 4, 0.000010));
}
}
below are the results that I got
start:6.0360919429063795, end: 6.0361006295681, iterations:23
6.03609628623724
start:3.0160069149974285, end: 3.0160132810008373, iterations:25
3.0160090369985646
start:4.00169557736413, end: 4.001703962607476, iterations:38
4.0016976736749665
import java.lang.*;
public class MathDemo {
public static void main(String[] args) {
// get two double numbers numbers
double x = 9;
double y = 25;
// print the square root of these doubles
System.out.println("Math.sqrt(" + x + ")=" + Math.sqrt(x));
System.out.println("Math.sqrt(" + y + ")=" + Math.sqrt(y));
}
}
Please use Newtons method to find the square root... It's relatively easy to code it...
- Rahul Arakeri June 14, 2014PS: I really don't get why people write all this code in the forum. The followers of this blog can easily code the solution. Let's just discuss solutions and time/space complexities...