Facebook Interview Question: Implement a power function to... | Glassdoor

Interview Question

Software Engineering Intern Interview(Student Candidate) Seattle, WA

Implement a power function to raise a double to an int

  power, including negative powers.
Tags:
technical, recursive algorithm, math
Answer

Interview Answer

11 Answers

1

Could be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills.

Interview Candidate on Feb 7, 2011
9

#include
#include

#define MAX_ARRAY_LENGTH 256

double power(double, unsigned int);

int main(int argc, char** argv) {
    double a = atof(argv[1]);
    int b = atoi(argv[2]);
    double result = power(a, b >> 31 == 0 ? b : -b);
    if ((unsigned int) b >> 31 == 1) {
        result = 1 / result;
    }
    printf("%f\n", result);
    return 0;
}

double power(double a, unsigned int b) {
    switch (b) {
    case 0:
        return 1.0;
    case 1:
        return a;
    default:
        return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a;
    }
}

Anonymous on May 20, 2011
5

c implementation of the above (no recursion):
int ipow(int base, int exp){
    int result = 1;
    while(exp){
        if(exp & 1) { result *= exp; }
        exp >>= 1;
        base *= base;
    }
    return result;
}

sathish on Jun 11, 2011
1

int power(double n, int exp)
{
    bool npower = (exp < 0) ? true : false;
    double result = 1;

    exp = abs(exp); // get the absolute value

    for (int i = 0; i < exp; i++)
    {
        if (npower)
        {
            result = result/n;
        }
        else
        {
            result = result*n;
        }
     }

    return result;
}

HWY* on Sep 10, 2011
0

C# code verified:

        static double Power(double d, int exp)
        {
            if (d == 0 || exp == 0)
            {
                if (exp >= 0)
                {
                    return 1;
                }
                else
                {
                    return double.PositiveInfinity;
                }
            }

            int expAbs = Math.Abs(exp);
            double res = d;
            for (int i = 1; i 0) ? (res) : (1 / res);
        }

Luiz on Sep 16, 2011
0

double power(double x, int y) {
    if(y == 0) return 1;

    int sign = 1;
    if(y < 0) sign = -1;
    y = abs(y);

    double d = power(x, y/2);

    if(y%2 == 0) d = d*d;
    else d = x*d*d;

    if(sign == -1) return 1.0/d;
    else return d;
}

Hussein on Apr 6, 2012
14

I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power.

Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations.

This is basic stuff, every university teaches that to its students... floating numbers representation...

TD on Aug 15, 2012
2

I believe interviewer is expecting for this

        public static double Power(double x, int y)
        {
            double result = 1;

            bool isNegative = y 0)
            {
                if ((y & 1) > 0)
                {
                    result *= x;
                }
                y = (y >> 1);
                x *= x;
            }

            if (isNegative)
                result = 1 / result;

            return result;
        }

Jay on Sep 16, 2012
0

Verified C#
        static double Pow(double b, double exp)
        {
            if (exp == 0) return 1;
            else if (exp > 0) return b * Pow(b, exp - 1);
            else return 1 / Pow(b, -exp);
        }
Does it get more compact?

Daniel on Nov 3, 2012
7

TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution.

Not Zoidberg on Jan 27, 2013
1

public double power(double num, int exp) {
        if(exp == 0)
            return 1;
        double res = 1;
        for(int e=Math.abs(exp);e>0;num*=num,e>>=1) {
            if( (e&1) == 1)
                res *= num;
        }
        return (exp>0)?res:1.0/res;
    }

pLasma on May 18, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.