Linkedin Interview Question
Software Engineer / DevelopersTeam: NA
Country: United States
Interview Type: Phone Interview
refer this:
en.wikipedia.org/wiki/Exponentiation_by_squaring
code based on this idea:
public static double pow (double base, int exponent)
{
boolean NegExp=false;
double result=1;
if (exponent==0)
return 1;
if (exponent<0)
{
NegExp=true;
exponent*=-1;
}
while (exponent>0)
{
if ((exponent&1)==1)
result*=base;
base*=base;
exponent=exponent>>1;
}
if (NegExp)
result=1/result;
return result;
}
if base = 0 and exponential = -3
exponential = exponential* (-1) = 3
result = 0
since exp was negative, result = 1/result = 1/0
Can you explain plz ?
if you have a linkedIn phone interview, mostly this question will be asked to you.
provide the simple solution first
while loop (b times)
{
result = result*a
}
Then note that it might be possible to divide this into smaller recursive problem.
we can use the property that a^b = (a^2)^(b/2)
here we square a, and divide b by 2. In doing this we divide the problem space into half.
so essentially,
when b i s even
pow(a,b) = pow(a^2, b/2);
when b is odd
pow(a, b) = a*pow(a^2, b/2);
Based on above, provide a recursive solution.
Then note that recursion uses stack - which is essentially extra memory.
To save on memory usage, we can convert this implementation into an iterative one.
and then provide the solution with while loop.
If you still have time, then note that
for odd and even b, right shifting the bits by one is equivalent to dividing b by 2.so use b=b>>1, instead of division.
also note that one can check if b is even or odd by this bit operation: if(b&01 === 1) implies that b is odd.
f(n) = a^n that can be written as
assume h(n) = GreatestIntegerFuntion(n)
then
a^n = a^h(n/2) * a^(n - h(n/2))
package com.problems;
public class PowerRecuresion
{
public static void main(String[] args)
{
testPower();
}
public static void testPower()
{
double a = -3;
int n = 6;
System.out.println("Power of " + a + " to the power " + n + " = " + power(a, n));
}
/**
* Time complexity of this is log(n) n = power;
*
* @param a
* - number
* @param n
* - power
* @return return a^n;
*/
public static double power(double a, int n)
{
if (n < 0)
{
return 0;
}
if (n == 0)
{
return 1;
}
else if (n == 1)
{
return a;
}
else
{
return power(a, n / 2) * power(a, n - n / 2);
}
}
}
This is actually O(N), because you have the recurrence relation:
T(n) = 2*T(n/2) + O(1)
For O(log N) you should do only one recursive call, i.e:
T(n) = T(n/2) + O(1)
You can obtain that be reusing the result of "power(a, n / 2)" to compute "power(a, n - n / 2)", and avoid the second recursive call.
double pow(double a,int b)
{
if(b==0) return 1;
if(b==1) return a;
double temp=pow(a,b/2);
temp=temp*temp;
return ((b%2==0)? temp : temp*a);
}
Is my code correct? does it have any performance issues?
public int pow(int base, int power){
int result = 1;
if(base == 0 || power == 0){
return 0;
}
if(power == 0){
return base;
}
if(base > 0 && power > 0){
for(int i = 1; i <= power; i++){
result = result * base;
}
}
return result;
}
@pinky884...
There is a typo in ur solution, the 2nd if should be
//if(power == 1)
Now, with regard to efficiency, ur code runs in O(power) time, but if u look at my implementation what u will see is, u can easily break the problems by half each time and multiply the result recursively to get an efficiency of O(log(power))...hope that helps
O(logb) time complexity
double pow(double A, int B)
{
if (i == 0 ) return 1;
if (i == 1) return A;
if (i == 2) return A * A;
Map<Integer, Double> exponentialPowersOfA = new HashMap<Integer, Double>();
exponentialPowersOfA.put(1, a);
int i = 2; previousPower = a;
while ( i < b){
exponentialPowersOfA.put(i, previousPower * previousPower);
previousPower = exponentialPowersOfA.get(i);
i = i * i;
}
if (i == b) return exponentialPowersOfA.get(i);
else {
int temp = 1;
int j = 1;
double retval = 1d;
while ( b > 0){
if ((b & 1) == 1){
retval *= exponentialPowersOfA.get(j);
}
j++; b >> 1;
return retval;
}
double powOlogN(double a, int b)
{
if (b == 0)
return 1;
else
if (b == 1)
return a;
else
if (b == 2)
return a * a;
else
{
return powOlogN(a, b/2) * powOlogN(a, b - b/2);
}
return 0;
}
"When asked to implement an efficient algorithm, don't use recursion. Use a loop."
is it a joke ?
Czylabsonasa,
Using a loop instead of a recursive algorithm prevents the overhead costs incurred by function invocations.
For the sake of completeness:
public static double pow(double base, int power)
{
if(base == 0 || power == 0){
return 1;
} else if (power == 1) {
return base;
} else {
double value = 1;
int powerVal = Math.abs(power);
while(powerVal > 0){
value *= base;
powerVal--;
}
return (power > 0) ? value : 1 / value;
}
}
Forgot to check for power = -1:
public static double pow(double base, int power)
{
if(base == 0 || power == 0){
return 1;
} else if (power == 1 || power == -1) {
return (power > 0) ? base : 1 / base;
} else {
double value = 1;
int powerVal = Math.abs(power);
while(powerVal > 0){
value *= base;
powerVal--;
}
return (power > 0) ? value : 1 / value;
}
}
#include<iostream>
double power(double a, int b)
{
if(b == 0) return 1;
if(b == 1) return a;
if(b == 2) return a*a;
double temp = 0;
temp = power(a,b-1) * a;
return temp;
}
void main()
{
while(1)
{
double a;
std::cout<<"input a: ";
std::cin>>a;
int b;
std::cout<<"input b: ";
std::cin>>b;
double result = power(a,b);
std::cout<<"result = "<<result<<std::endl;
}
system("pause");
}
double power(double a, int b)
{
if(a==0)
return 0;
if(b==0)
return 1;
if(b==1)
return a;
if(b%2==0)
return power(a, b/2)*power(a, b/2);
else
return power(a, b-1)*a;
}
public class PowerDouble{
public static void main(String[] args){
double aNeg = -3.5;
double aZero = 0.0;
double aPos = 5.8;
int bNeg = -3;
int bZero = 0;
int bPos = 5;
System.out.println( pow(aNeg, bNeg) );
System.out.println( pow(aNeg, bPos) );
System.out.println( pow(aPos, bNeg) );
System.out.println( pow(aPos, bPos) );
System.out.println( pow(aZero, bPos) );
System.out.println( pow(aNeg, bZero) );
System.out.println( pow(aZero, bZero) );
}
public static double pow(double a, int b){
double powValue = 1.0;
if ( a == 0.0 )
return a;
else if ( b == 0 )
return 1;
else if( b > 0 ){
while ( b-- > 0)
powValue *= a;
return powValue;
}
else { // b is negative
int negativeIndex = -b;
while ( negativeIndex-- > 0)
powValue *= a;
return (1/powValue);
}
}
}
static double[] pp = new double[100];
static int cnt = 0;
public static double pow(double a, int b) {
if (b == 0) {
return 1;
}
if (b == 1) {
return a;
}
if (b < 0) {
return 1 / pow(a, -b);
}
return pow(a, b);
}
public static double evaluateExpressionPow(double a, int p) {
cnt++;
if (p == 1) {
return a;
}
if (p == 0) {
return 1;
}
if (pp[p / 2] > 0) {
double r = a;
if (p % 2 == 0) {
r = 1;
}
return pp[p / 2] * pp[p / 2] * r;
}
pp[p / 2] = evaluateExpressionPow(a, p / 2);
double r = a;
if (p % 2 == 0) {
r = 1;
}
return pp[p / 2] * pp[p / 2] * r;
}
Hi Folks,
I have 80% of this working. If I have the base to the power of fraction, there there is problem. Else this program takes number of inputs mentioned in java.lang.math.pow doc..
import java.lang.Math;
public class PowClass {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
double a = 3;
int b =(int) 2;
System.out.println("computed value is: " + powFunc(a, b));
System.out.println(java.lang.Math.pow(a, b));
}
public static double powFunc(double a, int b) {
double value = 1;
if ((a == 0) && (b < 0)) {
value = Double.POSITIVE_INFINITY;
return value;
}
if (a == Double.POSITIVE_INFINITY && b == Double.POSITIVE_INFINITY) {
value = Double.POSITIVE_INFINITY;
return value;
}
if (a == 1 && b == Double.POSITIVE_INFINITY) {
value = Double.NaN;
return value;
}
if (a == 0)
return a;
if (b == 0)
return 1;
if ((a < 0) && (b % 1 != 0)) {
value = Double.NaN;
return value;
}
if (b % 1 != 0) {
double var = Math.round(b);
b=(int)(b-var);
while (var-- > 0)
value *= a;
a = a * b;
System.out.println(a);
value *= a;
return value;
} else if (b < 0) {
double negIndx = -b;
while (negIndx-- > 0)
value *= a;
return 1 / value;
} else {
while (b-- > 0)
value *= a;
return value;
}
}
}
package org.interview;
public class CalculatePowerMtoN {
public static void main(String[] args) {
System.out.println(ipow(10,2));
}
private static int ipow(int base, int exp) {
int result = 1;
while (exp != 0) {
if ((exp & 1) == 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
}
public static double pow (double base, int exp){
if (base == 0 && exp != 0)
return 0;
if (base ==0 && exp ==0)
return Double.NaN; //pow(0, 0) is undefined.
if (exp == 0)
return 1;
boolean baseIsNegative = (base<0);
boolean expIsNegative = (exp<0);
double baseAbs = baseIsNegative? base *(-1) : base;
int expAbs = expIsNegative? exp*(-1) : exp;
boolean expIsOdd = ((expAbs & 1) == 1);
double result = easyPow (baseAbs, expAbs);
if (expIsNegative){
result = 1 / result;
}
if (baseIsNegative && expIsOdd){
result *= -1;
}
return result;
}
/*helper function with both base and exponent positive. instead of multiplying the base exp times,
* we can easily get pow (base, pow (2, k)) in k steps
* for instance, if exp = 100, we can get a, a^2, a^4, a^8, ..a^32, a^64 by 6 calculation.
* Then a^100 = a^64 * a^32 * a^4. note that 100 = (1100100)2 -----complexity O(logN) -------*/
private static double easyPow(double base, int exp) {
if (base < 0 || exp < 0)
return Double.MIN_VALUE;
double result = 1;
int bit;
double basePow = base;
while (exp > 0){
bit = exp & 1; //right-most bit
if (bit==1){
result *= basePow;
}
basePow *= basePow;
exp = exp >>> 1; //get the next right-most bit for the next round.
}
return result;
}
- Shu February 03, 2013