Amazon Interview Question
SDETsCountry: India
Interview Type: In-Person
long pow(int a, int b) {
long x = pow(a, b/2);
if (b % 2 == 0) {
return x * x;
} else {
return x * x * b;
}
}
Sorry, but this i O(logN) memory, since you have the calls ont he function saved on the stack.
Java
public static float power(float x, int n){
if(n == 0) return 1;
float y = power(x,n/2);
if(n%2 == 0) return y*y;
else {
if(n > 0) return x*y*y;
else return (y*y)/n;
}
}
# In python.
def power(a, b):
# For an invocation where b = 7, this will get called 3 times.
print "Inside the power function \n"
# Default, return 'a'
# This will be done when b == 0 or b == 1
# (Also minimizing the number of return statements in the function).
retVal = a
# When b is a multiple of 2
if (b%2) == 0:
ret = power(a*a, b/2)
elif b > 2:
# When b is not a multiple of 2.
retVal = a * power(a*a, (b-1)/2)
return retVal
if __name__ == "__main__":
val = power(2, 7)
print "Output = "+str(val)
# In python.
def power(a, b):
# For an invocation where b = 7, this will get called 3 times.
print "Inside the power function \n"
# Default, return 'a'
# This will be done when b == 0 or b == 1
# (Also minimizing the number of return statements in the function).
retVal = a
# When b is a multiple of 2
if (b%2) == 0:
ret = power(a*a, b/2)
elif b > 2:
# When b is not a multiple of 2.
retVal = a * power(a*a, (b-1)/2)
return retVal
if __name__ == "__main__":
val = power(2, 7)
print "Output = "+str(val)
public int power(int base, int ext) {
int result = 1;
for(int head = 1, tail = ext;head <= tail; head++, tail--){
if(tail == head) {
result *= base;
} else {
result = base * base;
}
}
return result;
}
// Recursive, but O(logN) space
public int power(int base, int exp) {
if(exp == 0)
return 1;
if(exp == 1)
return base;
boolean isExpOdd = exp % 2 == 1;
exp = exp / 2;
return power(base, exp) * power(base, isExpOdd ? exp + 1 : exp);
}
I think you're missing the cases when you have 12343 and you have to append 21 or
123432 and have to append only 1.
My solution would be to find the middle and try to check left and right until there's a missmatch. If I find a missmatch, it means the middle is incorrect so I increment it with 1 till I find the correct middle (both to the left and right I have the same values) or I hit the end (when none of the values match).
Solution in java if any faults please let me know..
import java.io.*;
import java.util.*;
class power
{
public static void main(String args[])throws Exception
{
int base,exp;
long ans;
Scanner sc = new Scanner(System.in);
System.out.println("Enter value of base : ");
base = sc.nextInt();
System.out.println("Enter value of exponent : ");
exp = sc.nextInt();
if(exp%2==0)
ans = pow(base,exp);
else
ans = pow(base,--exp)*base;
System.out.println(" answer = "+ans);
}
public static long pow(int base, int exp)
{
if(exp==0)
return 1;
if(exp==1)
return base;
else
return pow(base,exp/2)*pow(base,exp/2);
}
}
I see a lot of bit shifting and recursive calls. The questions is pretty straight forward. They are asking for O(log n) performance, which means you code it in a way that should do half the work. Just loop half the size of the exponent and multiply the number through. Then take the result and multiply it by itself.
public static int GetPower(int num, int exp)
{
// Leave default as 1 when the exponent is 0
int answer = 1;
for (int i = exp % 2 == 0 ? exp / 2 : (exp - 1) / 2; i > 0; i--)
{
answer = answer * num;
}
answer = answer * answer * (exp % 2 == 0 ? 1 : num);
return answer;
}
c++
- sulzandrei December 23, 2015