Amazon Interview Question
Software EngineersCountry: India
Interview Type: In-Person
C++ recursive approach just for fun
double powHelper(int x, int y)
{
return y == 1 ? x : x * powHelper(x, y - 1);
}
double pow(int x, int y)
{
// Corner cases and edge cases
if (y == 0 && x < 0) return -1;
if (x == 0 && y < 0) return -1u >> 1; // MAX_INT
if (y == 0) return 1;
if (x == 0) return 0;
// Use separate helper function to avoid
// duplicating corner/edge case tests
if (y > 0)
return powHelper(x, y);
else
return 1.0 / powHelper(x, -y);
}
public class Power {
public static int power(int n, int k) throws Exception
{
if(n < 0 || k < 0) throw new Exception("Cannot calculate the power");
if(k == 0) return 1;
if(k == 1) return n;
int result = 1;
for(int i = 1; i <= k; i++ )
{
result *= n;
}
return result;
}
public static int powerRecursive(int n, int k) throws Exception
{
if(n < 0 || k < 0) throw new Exception("Cannot calculate the power");
if(k == 0) return 1;
if(k == 1) return n;
return n * powerRecursive(n, k - 1);
}
public static void main(String[] args) throws Exception{
int n = 4, k = 3;
System.out.println(power(n,k));
System.out.println(powerRecursive(n,k));
}
}
Seems like the site is buggy, I am not able to reply to individual comments, so replying inline
Fernando, can you improve the tie complexity
Josh , have you considered overflow. Time complexity as also be improved
Chris, [let's assume it's all integers so we can ignore negative exponents (e.g. 2^-1 = 1/2...) and there are no roots involved either]. This is nota good assumption since you are taking integer as input
1) let's assume it's all integers so we can ignore negative exponents (e.g. 2^-1 = 1/2...) and there are no roots involved either
2) actually a negative exponent would be easy to do, just return a double and build the reciprocal 1/pow(base, -exp)
then it's about corner cases and overflow, try to be clean here
- Chris May 23, 2017