Ashish Srivastava | @ashishsrtechie | 5 Oct, 2015
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
Divide the problem into sub-problems with an exponent n/2 and recursively get to the final answer.
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)
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!
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.