CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Microsoft Interview Question for Applications Developers


Country: India
Interview Type: In-Person
More Questions from This Interview



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

- Ryan August 25, 2012 | Flag Reply
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);
    }

- Ashupriya August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesnot cover negative case

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

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

- dc360 September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashupriya September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dc360 September 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- nik November 07, 2012 | Flag
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;

}

- hao.liu0708 August 27, 2012 | Flag Reply
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;
}

- wangxuyang September 25, 2012 | Flag Reply
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));
}

- samrat August 26, 2012 | Flag Reply
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);
}

- maverick August 26, 2012 | Flag Reply
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;
}

- anurag August 26, 2012 | Flag Reply
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)

- Yev August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dc360 September 04, 2012 | Flag
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

- abilash.s.90 September 02, 2012 | Flag Reply
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;
}

- Anonymous June 19, 2013 | Flag Reply
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

- vasanth November 05, 2014 | 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