Linkedin Interview Question for Software Engineer / Developers


Team: NA
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
4
of 4 vote

public class Power{
    

    public static double pow(double a, int b){
        //check the validity of a and b
        if(a == 0 && b == 0)
            return Integer.MIN_VALUE;
        
        if(a == 0)
            return 0;

        if(b == 0)
            return 1;
        
        if(b == 1)
            return a;

        boolean aMinus = a < 0? true: false;
        boolean bMinus = b < 0? true : false;

        int bAbs = Math.abs(b);
        double aAbs = Math.abs(a);
        
        //check if b is odd
        double tempAnswer;
        if( (b & 1) != 0){
            tempAnswer = pow(aAbs, bAbs - 1) * aAbs;
        }
        else{
            tempAnswer = pow(aAbs * aAbs, bAbs / 2);
        }

        if(bMinus)
            tempAnswer = 1.0 / tempAnswer;
        if(aMinus && (b&1)!= 0)
            tempAnswer *= -1;

        return tempAnswer;

    }

    public static void main(String[] args){

        System.out.println(Power.pow(-2,9));
        return ;
    }
}

- Shu February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good..but can we directly compare double numbers?

- Anonymous October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check for pow(-0.5, -7). The above code outputs incorrect number.

- abc May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above code seems correct except if(aMinus && (b&;1)!= 0) .. here ; seems a mistake

- Anonymous October 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

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;
}

- Anonymous October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if base = -3 and exponential = 0
1/0 ?? divide by 0 ?

- Mahmoud November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ohhh sorry, please ignore my reply, it will return 1 directly

- Mahmoud November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- Mahmoud November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
7
of 7 votes

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.

- snoqualmieseattle December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

snoqualmieseattle : Post this as an answer! :)

- Vishal February 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
		}

	}

}

- aviundefined August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- cristian.botau August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- XYZ May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- XYZ May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are not dealing with negative powers.

- Second Attempt March 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- IHaveArrived May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When asked to implement an efficient algorithm, don't use recursion. Use a loop.

- Orr May 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"When asked to implement an efficient algorithm, don't use recursion. Use a loop."
is it a joke ?

- czylabsonasa June 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Czylabsonasa,

Using a loop instead of a recursive algorithm prevents the overhead costs incurred by function invocations.

- Anonymous April 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea, should be a joke. If the code is tail recursive some languages will unwind it into a loop. But, the inefficiency is so low that it shouldn't be in the discussion unless we are talking about a particular language and aren't primarily concerned with asymptotic complexity.

- Anonymous September 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}
	}

- Orr May 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}
	}

- Orr May 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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");
}

- matt.oy1985 June 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

instead of return power(a, b/2) * pow(a, b/2) cache the result, then result*result. avoids extra work .

- Ryan July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if T(n)=2T(n/2), it is still a O(n).

- Anonymous May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}


}

- Rothschild October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Anonymous November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

evaluateExpressionPow has side effects. After a call of pow(a, b), if I call pow(c, d) where c != a it will use the pp computed for a (which is obviously wrong).

- cristian.botau November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if(b==0) return 1
what if b=0 and exponential is 0 as well. Should return 1 ???!!!

- Md November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

should be like below
If(b == 0)
{
if(a==0) return 0;
else return 1;
}

- Md November 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}
}

- Anil January 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
a^b
1. Take log a
2. multiply b * (log a)
3. calculate anti-log.

I think this would be in o(1).

- Vikram Patil September 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static long exp(int a , int n)
	{
		boolean is_N_Odd = false;
		if ( n % 2 > 0 )
		{
			n++;
			is_N_Odd =true;
		}

		if ( n == 2 )
			return a * a;
		else if (n == 1 )
			return a;
		else
		{
			long calc = exp (a , n/2) ;  
			if ( is_N_Odd )
				return calc * calc /a;
			else			
				return calc * calc ;
		}
	}

- sanmeetshikh September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- a April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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; 
	}

- Yu July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int power(int x,int y)
{
if(y==0)
{
return 1;
}
else
{
return (x*power(x,y-1));
}
}

- Ankur Saxena December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int power(int x,int y)
{
	if(y==0)
	{
		return 1;
	}
	else
	{
		return (x*power(x,y-1));
	}

}

- Ankur Saxena December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dd

- Anonymous October 20, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More