Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
c#, Newton approximation.
private static double GetRootCubeNewton( double num ) {
double accuracy = 0.0000000000001;
double x = 1;
int n = 10;
while ( true ) {
for ( int i = 0; i < n; i++ ) {
x = ( 2 * x + num / ( x * x ) ) / 3;
}
if ( Math.Abs( x*x*x - num ) < accuracy ) {
break;
}
}
return x;
}
c++, implementation
double cubeRoot(double n) {
double cube, left, right, mid;
int cnt, sign;
sign = 1;
if (n < 0.0) sign = -1;
n *= sign;
left = 0.0;
right = n;
if (n < 1.0) right = 1.0;
cnt = 100;
while (cnt--) {
mid = (left + right) * 0.5;
cube = mid * mid * mid;
if (cube > n) {
right = mid;
} else {
left = mid;
}
}
return left * sign;
}
/**
*
*/
package careercup.google;
/**
*
* Fastest way to compute cube root of a number
*/
public class CubeRoot {
/**
* @param args
*/
double num = 81;
public static void main(String[] args) {
CubeRoot cr = new CubeRoot();
System.out.println("Number is "+cr.num);
System.out.println("Cube Root (via binary search algo) is "+cr.cubeRoot_binarySearch());
}
private double cubeRoot_binarySearch()
{
double tolerance = 0.000001; //say
double low = 0;
double high = this.num;
double mid = 0.0;
double cube = 0.0;
while(true)
{
mid = (low+high)/2;
cube = mid*mid*mid;
if(Math.abs(cube-this.num) <= tolerance)
break;
else if(cube > this.num)
high = mid;
else
low = mid;
}
return mid;
}
}
I don't know if it's the fastest way a round but it's quite fast (usually below 10 steps)
I think it's called the Newton Raphson method.
/*
* File: main.cpp
* Author: Leon
*
* Created on November 17, 2015, 9:39 PM
*/
#include <cstdlib>
#include <iostream>
using namespace std;
double fCube(double x) {
return x*x*x;
}
double derivativeFCube(double x) {
return 3*x*x;
}
double cube_root(double (*f)(double) , double (*df)(double),
double n, double guess) {
double eps = 0.0001;
double curr = guess;
while (f(curr)- n > 0 ? f(curr) - n > eps : f(curr) - n < eps) {
double fc = f(curr) - n;
double dfc = df(curr);
curr = (curr*dfc - fc) / (dfc);
double y = f(curr);
cout << "x = " << curr << "\n";
}
}
/*
*
*/
int main(int argc, char** argv) {
cube_root(fCube, derivativeFCube, 27, 4);
return 0;
}
double mod(double x){
if(x > 0)
return x;
else
return -1*x;
}
double cubeRoot(double x1, double x2, int x) {
double epsilon = 0.0001;
double root = (x1 + x2) / 2;
double numEstimate = pow(root,3);
if(mod(numEstimate - x) < epsilon)
return root;
else if(numEstimate > x)
return cubeRoot(x1, root, x);
else
return cubeRoot(root, x2, x);
}
double computeCubeRoot(int x){
return cubeRoot(0, x, x);
}
double mod(double x){
if(x > 0)
return x;
else
return -1*x;
}
double cubeRoot(double x1, double x2, int x) {
double epsilon = 0.0001;
double root = (x1 + x2) / 2;
double numEstimate = pow(root,3);
if(mod(numEstimate - x) < epsilon)
return root;
else if(numEstimate > x)
return cubeRoot(x1, root, x);
else
return cubeRoot(root, x2, x);
}
double computeCubeRoot(int x){
return cubeRoot(0, x, x);
}
iosrjen.org/Papers/vol4_issue4%20(part-1)/A04410107.pdf
- ankushbindlish November 15, 2015Secant Method over other methods