Problem of the week - Power

Google has positioned itself as a dream company for almost all software engineers for quite some time now. With one of the lowest interview success rates and some of the hardest coding interview questions, getting a job at Google as a software engineer is hard, BUT, it's not a moonshot. This week, we will practice a problem that is an interview favorite with many current and ex Googlers - Power.

Function to calculate x^n - power(x,n)
x: base value
n: power value

Approach 1 :

Hint: Divide and Conquer

Divide the problem into sub-problems with an exponent n/2 and recursively get to the final answer.

Implementation:

int power(int x, int n)
    {
        if( n == 0)
            return 1;
        else if (n%2 == 0)
            return power(x, n/2)*power(x, n/2);
        else
            return x*power(x, n/2)*power(x, n/2);    
    }

Neat, isn’t it? let's check the space and time complexities.
Time Complexity: O(n)
Space Complexity: O(1)

That's a smart answer, and you should give yourself a high-five if you got this far. But this being a Google interview - you're asked to optimize the solution and bring down the time complexity to O(log n).

Approach 2 :

Hint: Calculate power(x, n/2) only once and store it.

Implementation:

int power(int x,  int n)
    {
        int tempAnswer;
        if( n == 0)
            return 1;
        tempAnswer = power(x, n/2); // Calculate once and store.
        if (n%2 == 0)
            return tempAnswer*tempAnswer;
        else
            return x*tempAnswer*tempAnswer;
    }

Ok, that's much better. But did we consider negative inputs? This answer cannot be complete without that - and you'll probably be put on the spot if you skipped on those. Always consider the edge cases - null, 0, negative - they're all fair game!

Hint: x^-n = i/xⁿ

Implementation:

float power(float x, int n)
    {
        float tempAnswer;
        if( n == 0)
           return 1;
        tempAnswer = power(x, n/2);       
        if (n%2 == 0)
            return tempAnswer*tempAnswer;
        else
        {
            if(n > 0)
                return x*tempAnswer*tempAnswer;
            else  // Below part handles the negative exponent
                return (tempAnswer*tempAnswer)/x;
        }
    } 

Time Complexity : O(logn)

Phew - so there you have it. A relatively tough yet small coding problem that is an interview favorite at Google and a lot of other technology companies. Of course, it is very hard to think up the solution to such problems on the spot, especially if you're given only 15 - 20 minutes to explain, code and improve your solution! Your best bet is smart practice - almost all coding interview questions are subtle variations applied to a 'Motherload' of ~ 1000 problems. Of course, no one expects you to practice all 1000 coding problems. But with smart practice, you can practice the questions you NEED to practice, and skip the ones you don't.

To solve such problems and prepare for coding interviews the SMART way - sign up for firecode.io

Also, if you have a better solution - share it in the comments!