## 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
if( (b & 1) != 0){
tempAnswer = pow(aAbs, bAbs - 1) * aAbs;
}
else{
tempAnswer = pow(aAbs * aAbs, bAbs / 2);
}

if(bMinus)
if(aMinus && (b&1)!= 0)

}

public static void main(String[] args){

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

Comment hidden because of low score. Click to expand.
0

Good..but can we directly compare double numbers?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
7

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.

Comment hidden because of low score. Click to expand.
0

snoqualmieseattle : Post this as an answer! :)

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

}

}``````

Comment hidden because of low score. Click to expand.
0

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.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

you are not dealing with negative powers.

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Czylabsonasa,

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

Comment hidden because of low score. Click to expand.
0

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.

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

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

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

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;

}

Comment hidden because of low score. Click to expand.
0

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

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).

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

}

}

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

Comment hidden because of low score. Click to expand.
0

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).

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 ???!!!

Comment hidden because of low score. Click to expand.
0

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

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

}
}

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).

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

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

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

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

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

}

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

dd

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.

### 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.