## Microsoft Interview Question for Applications Developers

Country: India
Interview Type: In-Person

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

``````public static int Power(int base, int expo){
if(expo == 1)
return base;
if(expo == 2)
return base*base;
if(expo%2==0)
return (Power(Power(base,expo/2),2));
else
return base*Power(base,expo-1);
}``````

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

@Ryan: Slight modification in your code and now it will run in O(logN) time....
see the changed code below

``````public static int Power(int base, int expo){
if(expo == 0) return 1;
if(expo == 1)
return base;
if(expo%2==0)
return (Power(base*base,expo/2);
else
return base*Power(base*base,(expo-1)/2);
}``````

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

doesnot cover negative case

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

@Ashupriya you mean O(n log n) right?
T(n) <= T(n/2) + O(1)
O(1) work to multiply the results from the recursive calls.

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

No I mean O(logN) and not O(NlogN)
if you see the logic carefully, we are doing less than n recurssive calls, each step tries to calculate 2 powers,
Moreover Recursion is generally not O(N Log N)....

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

oops. recurrence i mentioned is O(log n), not nlog.

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

I am a bit confused about the complexity.
We will be still doing 'exponent' number of product operations.
Since the multiplication is the costliest operation here, won't the complexity still be O(n) (Assuming a sequential execution algorithm) even though the loops/recursions run till O(log n)?
In that case why not just use a simple for loop with a product variable holding the final result?

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

I do not really prefer to solve this using recursion. This version will be better I think.

``````#include<iostream>

int power(int x, int n)
{
if (n < 0)
return 1 / power(x, -n);

int res = 1;
int base = x;

while (n > 0)
{
if (n & 1 == 1)
res *= base;

base *= base;
n >>= 1;
}

return res;
};

int main()
{
int res = power(3, 3);

return 0;

}``````

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

here is a none recursive way:

``````unsigned int calc(unsigned int a, unsigned int b)
{
unsigned int tmp = a;
unsigned int ret = 1;
while(b)
{
if(b & 1)
{
ret *= tmp;
}
tmp *= tmp;
b >>= 1;
}
return ret;
}``````

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

``````#include<stdio.h>
int power(int a,int b)
{

int val=0;
if(b==1)
return a;
if(b==0)
return 1;
if(b%2==0)
{
val=power(a,b>>1);
return val*val;
}
else
{
b=b-1;
val=power(a,b>>1);
return a*val*val;
}
}

int main()
{
printf("%d",power(2,5));
}``````

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

``````long int expo(long int base,int power)
{
if(power==1)
return base;
else if(power%2==0)
return expo(base*base,power/2);
else
return base*expo(base,power-1);
}``````

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

int call(int a,int b)
{
if(b==0)
return 1;
a=a*call(a,b-1);
return a;
}

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

Base cases:
if p = 0, then return 1
if p = 1, then return base
0^p = 0
1^p=1
2^p = 2<<(p-1), p>=2

If Base % 2 == 0 then
(2*n)^p => 2^p * n^p => O(logp)

Else if Base % 2 > 0 then
B^p = B * B^(p-1) O(p)

Overall running time: O(p*logp)

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

If the overall running time is nlogn, then it would be worse than the simple order n solution which just multiplies base p times.

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

Use divide and conquer guys.

divide 'b' by 2 recursively so that u have computed a^(b/2) once and u can multiply the same thing again to get the final value... if 'b' is a odd value subtract 1 from 'b' and do the same thing and multiply 'a' again to get the final value

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

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

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

please solve this logic expression (a pow b+b pow a)=1234 then what the values of a,b with code

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.