Interview Question
Senior Software Engineer InterviewPalo Alto, CA
FacebookWrite some pseudo code to raise a number to a power.
Interview Answers
11 Answers
int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); }
small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; }
double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; }
# Solution for x ^ n with negative values of n as well. def square(x): return x * x def power(x, n): if x in (0, 1): return x if n == 0: return 1 if n < 0: x = 1.0 / x n = abs(n) # Even number if n % 2 == 0: return square(power(x, n/2)) # Odd number else: return x * power(x, n - 1) print ("0 ^ 0 = " + str(power(0, 0))) print ("0 ^ 1 = " + str(power(0, 1))) print ("10 ^ 0 = " + str(power(10, 0))) print ("2 ^ 2 = " + str(power(2, 2))) print ("2 ^ 3 = " + str(power(2, 3))) print ("3 ^ 3 = " + str(power(3, 3))) print ("2 ^ 8 = " + str(power(2, 8))) print ("2 ^ -1 = " + str(power(2, -1))) print ("2 ^ -2 = " + str(power(2, -2))) print ("2 ^ -8 = " + str(power(2, -8)))
If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations.
Because it uses dynamic programming and is lots more efficient than your algorithm.
If the power is not integer, use ln and Taylor series
If I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1.
There is a way to do this in a logN way rather than N. function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1); } This is from Programming pearls.. interesting way.
In Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}"
pretty trivial...