## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

a basic O(log(b)) solution, assuming the result shall fit in a long long. Otherwise we have to implement a method for string multiplication.

``````#include <iostream>

using namespace std;

computeApowB(long long a, long long b) {
long long ret = 1;
while(b) {
if (b & 1) {
ret *= a;
}
a = a * a;
b /= 2;
}
}``````

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

nice, b/= 2 can change to b >> 1;

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

The first parameter should be long long &a, and one initial condition checking:
if (b == 0) {
a = 1;
return;
}

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

Good algorithm, but note this implementation sucks for 0^0 and 2^-2.

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

This can be done in o(log b) time

divide the prob into a^b/2 * a^b/2
and further divide a^b/2 into a^b/4*a^b/4 and so

it forms a recurrence tree

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

How is it better than multiplying a b times. Your leaf nodes a^1 will still be called b times.

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

``````int apowerb::power(int x, int y)
{
if(y==1)
return x;
if(y%2==0)
return power(x,y/2)*power(x,y/2);
else
return power(x,(y-1)/2)*power(x,(y-1)/2)*x;
}``````

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

This is still not Optimized. Memoize it

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

``````package com.google.practice;

public class PowerOf2 {

public static void main(String[] arg){
int a=2,b=30;

int[] memo = new int[b+1];
for(int i=2;i<memo.length;i++){
memo[i] = -1;
}
memo[0] = 1;
memo[1] = a;
long t1,t2;

//Memoized
t1=System.currentTimeMillis();
for(int i=0;i<1000;i++)
pow(a,b,memo);
t2=System.currentTimeMillis();
System.out.println("Memo 		"+(t2-t1)+" millisecond(s)");

//without memoized - (not better than linear time)
t1=System.currentTimeMillis();
for(int i=0;i<1000;i++)
pow1(a,b);
t2=System.currentTimeMillis();
System.out.println("Divide only	"+(t2-t1)+" millisecond(s)");

// Brute in linear time
t1=System.currentTimeMillis();
for(int i=0;i<1000;i++)
pow1(a,b);
t2=System.currentTimeMillis();
System.out.println("Brute 		"+(t2-t1)+" millisecond(s)");
}

public static int pow(int a, int b,int[] memo) {
if(b==0)
return 1;
if(b==1)
return a;
if(memo[b]!=-1)
return memo[b];

if(b%2!=0){
memo[b] = pow(a,(b-1)/2,memo) *a* pow(a,(b-1)/2,memo);
}
else
memo[b] = pow(a,b/2,memo) * pow(a,b/2,memo);

return memo[b];
}

public static int pow1(int a, int b) {
if(b==0)
return 1;
if(b==1)
return a;

if(b%2!=0){
return pow1(a,(b-1)/2) *a* pow1(a,(b-1)/2);
}
else
return pow1(a,b/2) * pow1(a,b/2);
}

public static int pow2(int a, int b) {
int product = 1;
for(int i=1;i<=b;i++)
product = product * a;
return product;
}

}``````

Result :
Memo 0 millisecond(s)
Divide only 10 millisecond(s)
Brute 10 millisecond(s)

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

Sorry, mistake in above code. Brute section wasn't calling brute method. After making that correction here is the result :

Memo 1 millisecond(s)
Divide only 9 millisecond(s)
Brute 4 millisecond(s)

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

``````int powab(int a, int b)
{
static int val = 0;
if (b == 1)
{
return a;
}
else
{
val = powab(a, b / 2);
if (b % 2 == 0)
return  val * val;
else
return val * val * a;
}
}``````

you only need to memory with an array for the problem that you will need almost all previous result, such as calculating the prime number. for this case, you only need to memory one number, just do it with a static var.

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

Recursion may be avoided in order to make it memory efficient.

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

``````Map<Long,ConcurrentHashMap<Long,Long>> memorize =
Collections.synchronizedMap(new HashMap<Long, ConcurrentHashMap<Long,Long>>());

public static void main(String[] args) {
Example1 example=new Example1();
long start=System.nanoTime();
System.out.println(example.powerSimple(3,46));
long end=System.nanoTime();
System.out.println("simple done in "+ (end-start) );

start=System.nanoTime();
System.out.println(example.power(3,46));
end=System.nanoTime();
System.out.println("memorize done in "+ (end-start) );

}

public long power(long a, long b){
if(a==0 )
return 0;
if(b==0)
return 1;
if(b==1)
return a;

ConcurrentHashMap<Long, Long> values=memorize.get(a);
if(values==null){
memorize.put(a, new ConcurrentHashMap<Long, Long>() );
}

Long value=memorize.get(a).get(b);
if(value!=null)
return value;
if(b%2==0){
value=power(a,b/2) * power(a,b/2);
}else{
value=power(a,(b-1)/2) * power(a,(b-1)/2)*a;
}

memorize.get(a).put(b, value);

return value;
}

public long powerSimple(long a, long 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)/2) * power(a,(b-1)/2)*a;
}

}``````

Return:
8500964271916320249
simple power calc done in 679916 nanos
8500964271916320249
memorize power calc done in 46696 nanos

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

``````public static int pow(int a, int b) {
if (b == 0)
return 0;
if (b == 1)
return a;

// odd exponents?
Boolean isOddExponent = b % 2 == 1;
int orginalBase = a;

// iteratively square the base (a)
// and reduce the exponent (b) by half
// until the exponent is less than 2;
while (b >= 2) {
a *= a;
b /= 2;
}

// one exponent left?
if (isOddExponent )
a *= orginalBase;

return a;
}``````

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

Small error there.

If b == 0, it should return 1, not 0.

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

///
import java.util.HashMap;

public class Snippet {
public static HashMap map = new HashMap();

public static int func(int a, int b) {
if (b == 0)
return -1;
int r = 0;
if (b >= 1) {
if (map.containsKey(a + "" + b)) {
return (int) map.get(a + "" + b);
} else {
if (b % 2 == 0) {
r = func(a, b / 2) * func(a, b / 2);
} else {
r = func(a, b / 2) * func(a, b / 2) * a;
}

}

map.put(a + "" + b, (int)r);
return r;
}

return 1;
}
}
///

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

``````def power(a,b):
if a==0 and n==0:
return "Math Error!!"
exponent=b
number=a
product=1
while(exponent>0):
if exponent%2==0:
number*=number
exponent=exponent/2
else:
product*= number
exponent-=1
return product

def main():
print power(10,10)
if __name__ == '__main__':
main()``````

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

Basically while raising an integer to the power of the number. You are only multiplying the number by itself at the places where the binary equivalent has a "1".

``````public static int pow(int x,int y)
{
int temp2=x;
int result=1;
int temp;
while((temp=bitcal(y))!=-1)
{
if(temp==1)
result*=temp2;
temp2*=temp2;y=y/2;
}
return result;
}
public static int bitcal(int y)
{
if(y>=1)
{
y=y%2;
}
else return -1;
return y;
}``````

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

The below one goes in one direction (increasing order of power)

``````/**
* Created by priganesh on 4/29/14.
*/
public class Memoization {

int[] previousResult = new int[2];
public int power(int base, int power) {
if(power < 0) throw new IllegalArgumentException();
if(power == 0) return 1;
if(power == 1) return base;
System.out.println("Given base : "+base+" Given power : "+power);

//power is odd
int result;
if(power %2 == 1) {
result = power(base,power/2) * base * power(base,power/2);
} else {
result = power(base,power/2) * power(base,power/2);
}

return result;
}

public int computeFromMemoization(int base, int power) {
if(power < previousResult[1]) throw new IllegalArgumentException();
int remainingPower = power - previousResult[1];

if(previousResult[0] == 0) {
previousResult[0] = power(base,remainingPower);
} else {
//computed from memoized result
previousResult[0] = previousResult[0] * power(base, remainingPower);
}

previousResult[1] = power;

return previousResult[0];
}

public static void main(String[] args) {
Memoization m = new Memoization();
int result = m.computeFromMemoization(2,4);
System.out.println("Result 1 : "+result);

result = m.computeFromMemoization(2,7);
System.out.println("Result 2 : "+result);
}
}``````

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

here are we accounting for the fact that a and b has no limitation. Some here are taking a and b as int and also considering all of them as positive.

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

Iterative O(log(b)) solution. Iterates over bits of b and multiples the result by the amount that corresponds to that bit. Relies on the fact that k^(p+q) = k^p * k^q.

``````public static long power(int a, int b){ // assumes b is non-negative
long ret = 1; // result
long curMult = a; // current multiple
while( b > 0 ){
if( (0x1 & b) != 0) ret*=curMult;
curMult *=curMult;
b>>>=1;
}
return ret;
}``````

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

``````// Olog(b)
int power(int a, int b)
{
if(b==0)
return 1;
if(a==0)
return 0;
int temp= power(a,b/2);
if(b%2==0)
return temp*temp;
else
return a*temp*temp;
}``````

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

Use bit shift to avoid floating point unit for multiplication. Divide the a in a^b such that a is (2^x + y). 2^x is optimized multiplication

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

public double pow(double x, int n) {
if(n == 0) return 1;
if(n == 1) return x;
if(n ==-1) return 1/x;

double result= x;
long pow = 1;

while(pow*2 < Math.abs(n)){
result = result * result;
pow = pow*2;
}
int remain = Math.abs(n) - (int)pow;
result = result*pow(x, remain);

if(n < 0) result = 1/result;
if( n%2 == 0) result = Math.abs(result);
if(n%2!=0 &&x<0) result = -1*Math.abs(result);
return result;
}

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

``````#include<iostream>
using namespace std;

int pow(int x, int y)
{
if(y  == 0)
return 1;
int temp = pow(x,y/2);
if(y %2 == 0)
return temp * temp;
else
{
if(y > 0)
return x * temp * temp;
else
return (temp * temp)/x;
}
}``````

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

Requires O(logn) time complexity and works for negative y too.

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

Use Dynamic programming approch.make a list of lower multiple and combine then to make the desire product.
Suppose ur b=6
then first we find a^2 then from a^2 * a^2 we can make a^4 then from a^4 * a^2 we can make a^6.
just u have to remember till now what you have computed and use those result to find the solution for bigger problem.thats DP.

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

Binary Exponentiation.

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

``````#include <stdio.h>
#define ll long long int

ll f(a,b) {
if (b == 0)
return 1;
if (b == 1)
return a;
ll ans = f(a,b/2) * f(a,b/2);
if (a%b == 1)
ans *= a;
return ans;
}``````

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

This a O(log(b)) algorithm... or O(k), where k is the number of bits necessary to represent b.

``````#include <stdio.h>
#define ll long long int

ll f(ll a, ll b) {
if (b == 0)
return 1;
if (b == 1)
return a;
ll ans = f(a,b/2) * f(a,b/2);
if (a%b == 1)
ans *= a;
return ans;
}``````

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

Iterative solution:

``````double pow(double x, int n) {
if(x==0) return 0;
if(n==0) return 1;
long long exp = abs(double(n));
double r=1;
while(exp){
if(exp&1)
r*=x;
exp>>=1;
x*=x;
}
if(n<0) return 1.0/r;
return r;
}``````

recursive solution:

``````double pow(double x, int n) {
if(x==0) return 0;
if(n==0) return 1;
double r = pow(x, n/2);
r*=r;
if(n%2==1)
r*=x;
if(n%2==-1)
r/=x;
return r;
}``````

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

``````public class ApowerB {
long table[]=new long[1000];
long findPower(int a, int b)
{
if(b==1)
return a;
if(b==2)
return a*a;
if(table[b/2]==0)
table[b/2]=findPower(a,b/2);
if(table[(b+1)/2]==0)
table[(b+1)/2]=findPower(a,(b+1)/2);

return table[b/2]*table[(b+1)/2];

}
public static void main(String[] args) {
ApowerB obj=new ApowerB();
System.out.println(obj.findPower(3,5));

}

}``````

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

``````Map<Integer,Integer> memoizationtable = new HashedMap<Integer, Integer>();

private int recursiveSplit(int a,int b)
{
if(b==1)
return a;
int leftsplit;
if(memoizationtable.get(new Integer(b/2))==null)
{
leftsplit = recursiveSplit(a, b/2);
memoizationtable.put(new Integer(b/2), leftsplit);
}
else
leftsplit = memoizationtable.get(new Integer(b/2));

int rightsplit;

if(memoizationtable.get(new Integer(b-b/2))==null)
{
rightsplit = recursiveSplit(a,b- b/2);
memoizationtable.put(new Integer(b-b/2), rightsplit);
}
else
rightsplit = memoizationtable.get(new Integer(b-b/2));

return leftsplit * rightsplit;
}``````

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

``````template <size_t a, size_t b>
struct power{
enum { value = a * power<a,b-1>::value };
};

template <size_t a>
struct power<a,0>{
enum { value = 1 };
};``````

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

exp(b*ln(a)) -- where a is positive, other cases apply, do your math

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

Version w/o recursion memory stack:

``````public static int getPow(int a, int b) {
int res = a;
int cache = 1;

while (b/2 > 0) {
if (b%2 == 1) cache *= res;
res *= res;
b/=2;
}
res *= cache;

return res;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Shifting is greatly less expensive than the multiplication operation, so if we could convert this into shifting for the most part, we've got ourselves a much cheaper version of the work. Besides, your solution up there don't solve for the power 0 :P

``````int Power(int a, int b) {
if (b == 0) {
return 1;
}
int Result = a;

int currentPower = 2;
while ( b-currentPower > 0) {
Result <<= 1;
currentPower <<=1;
}

return Result * Power(a, b-currentPower>>1);
}``````

}

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

When I provide input 4, 6 ( a == 4, b == 6), it returns 256, however, expected result is 4096.

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.