Google Interview Question for Software Engineer / Developers


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




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

the question here is how we can reduce the complexity... if we compute the x^y by normal method the complexity is O(y)... to reduce the complexity we can use binary weighted power computation method in which complexity is O(logy)..

ans=1;
square=x;
if(y==0)
    return 1;
while(y!=0)
{
    if(y%2)
        ans=ans*square;
    square=(square*square)%z;
    y=y/2;
    if(ans>z)
        ans=ans%z;
}
return ans;

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

here in each step mod z is used just to prevent overflow for large x or y...

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

People are missing the point that this is modular exponentiation and you got it right my friend +1. Your program works fine, but I suggest you use the code formatter next time, I think that's why people don't understand the code.

This is a nice implementation from the book Applied Cryptography by Bruce Schneier.

- oOZz July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks oOZz...

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

Could somebody please format the code and explain?

- Jack July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here complexity is O(log y) not O(y); because we are reducing y to half in every iteration

- Anonymous September 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Nicely explained here: ht p://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers
C Version

int NoPowMod( int x, int y, int z )
{
	int a = x % z;
	int t = 1;
	while( y > 0 )
	{
		// Y is odd
		if( y & 1 )
		{
			t = (t * a) % z;
		}
		y >>= 1;
		a = (a * a) % z;
	}
	return(t);
}

- TheNutto July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if y equals to zero

- Anushree July 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 9 vote

int calcp(int x,int y,int z)
{ 
   int t = 1;
   for(int j = 0;j< y;j++)
      {
          t = (t*x)%z;
       }
      return t;
}

- Engineer1111 July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just as a brief explanation, the part of (t*x) that gets thrown away by the % operator value is divisible by the % operator value, so multiplying that value further will always give evenly divisible multiples, so you can just remove it.

- Anonymous July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Since the modulo operation is distributive, we can reduce the overflow chances further as below

int calp(int x,int y,int z)
{ 
   int t = 1;
   x = x % z;
   for(int j = 0;j< y;j++)
      {
          t = (t*x)%z;
       }
      return t;
}

Hint : (ab) mod n = ((a mod n) (b mod n)) mod n.

- Vin July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need z

- Anonymous September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

The following is a O(logn) based algorithm to compute the power. We can just do:

power(x,y)%z

public static int power(int x, int n) {
     if(n == 0)
         return 1;
    else if(n==1)
          return x;
    else if(n%2==0) {
          int y = power(x,n/2);
          return y*y;
    }else {
          int y = power(x,n-1/2);
          return y*y*x;
    }
}

- Chander July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question clearly mentions not to use pow()

- Murali Mohan July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Akbar-The-Slave, The emperor has written his own power method.

- loveCoding July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

See the code below its much more simpler.

- CodeLuver July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The line:
int y = power(x,n-1/2);

is incorrect "/" takes precedence before "-", so the expression n-1/2 will actually evaluate to n. Btw, since n is odd you could just write n/2 (it will truncate the result, and it is equivalent to (n-1)/2).

Also, your solution will likely overflow since x^y can easily get over 2^31-1. You need to apply "% z" to each multiplication inside the power() function.

What if x and z are very large, like 2^31-10? Even if you use "% z" for each multiplication it is not ok, for example x*x will overflow. So, when performing a multiplication you need to use long long ints (which can hold numbers up to 2^63-1). For example, line "return y*y" should be "return ((long long)y * y) % z"

For a correct implementation, which also works for large int values for x, y, z check my answer.

- cristian.botau July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@loveCoding

See cristian.botau comment. The idea of computing a % implies handling of overflows. Computing an exponential first and then taking modulus later will not give correct results for large x and y,

- Murali Mohan July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what you have done is definitely log(n) solution but it will make integer overflow very easily as x^n will easily cross integer max limit.
It could be safely done in below steps, not crossing integer overflow limit.
using the formula (ab) mod n = ((a mod n)*(b mod n)) mod n

 public int getMod(int x, int y, int z){
        if(y == 1)
            return x%z;
        int halfMod = ((getMod(x, y/2, z)%z) * getMod(x, y/2,z))%z;
        if (y%2 == 0){
            return halfMod;
        }else {
            return ((halfMod%z)*(x%z))%z;
        }
    }

It is O(logY) complexity and will never cross integer max limit.

- m3th0d.itbhu July 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is an O(log(y)) algorithm. It is the classical fast exponential algorithm. I won't get into details into it because it is a simple algorithm and can be found easily by googling it.

However, the trick to this problem is to watch out for arithmetical overflows:
- since x^y can grow really big, you can't just compute x^y and then apply % z, since it will likely overflow; so you need to apply modulo z operation on each multiplication;
- furthermore for high values of z even one multiplication can overflow (take for instance x = 2 billions - 1, y = 2, z = 2 billions), so you need to use the long long type for each multiplication;

In order to make sure there is no arithmetic overflow happening, I've defined the modMul(x, y, z) operation which performs the operation "(x * y) % z" and guarantees there is no overflow.

inline int modMul(int x, int y, int z) {
    int result = ((long long)x * y) % z;
    return result;
}

int power(int x, int y, int z) {
    if (y == 0)
        return 1;

    int sqrt = power(x, y / 2, z);
    int result = modMul(sqrt, sqrt, z);

    if (y % 2 == 1)
        result = modMul(result, x, z);

    return result;
}

- cristian.botau July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public static int theCode(int x, int y, int z)
{
int temp = x;
for (int i = 1; i <= y; i++)
{
x = x * temp;
}
return x % z;
}

- CodeLuver July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will not work when y = 1

- alice.vich July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

(int) exp(y * log(x)) % z

#include <iostream>
#include <cmath>

static int pow_exp_log(int x, int y) {
	return ((int) exp(y * log(x)));
}

int main() {
	int x = 3, y = 4, z = 5;
	std::cout << "exp(y * log(x)) % z = " << pow_exp_log(x, y) % z << std::endl;
	std::cout << "pow(x, y) % z = " << (int) pow(x, y) % z << std::endl;
}

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So far no one has handled the case where y is a negative integer.

float func(int x, int y, int z) {
	float temp = 1;
	for(int i = y; i > 0; i--) {
		temp *= x;
	}

	if(y < 0) {
		temp = 1 / x;
	}
	return temp % z;
}

- alice.vich July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's because it doesn't make sense in modular arithmetic (floating point numbers don't make much sense in modular arithmetic).

Actually, it would make sense if you would compute the modular multiplicative inverse of x^abs(y) if y is negative, but that can be computed only if x^abs(y) and z are coprimes (so the problem might not always have an answer).

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

it means u cannot first use pow(x,y) and then mod it by z . i guess.

- Anonymous July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count(int x, int y, int z)
{
	int temp_x = x;
	int temp_y = 1;
	while(temp_y<y)
	{
		++temp_y;
		x *= temp_x;
	}
	return x %= z;
}

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

We can eliminate % by doing:

int result=1;
	int i;

	for(i=0;i<y;i++)
		result=result*x;
	while(result>=z)
		result-=z;

	printf("\n%d\n",result);

- Anonymous July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
     * Computes (x^y) % z, without using power function in O(log y) time.
     * Uses distributive property of modulo function: (a*b) % c = ((a%c) * (b%c)) % c
     * To compute (x^y) % z, first recursively calls itself compute to (x ^ (y/2)) % z,
     * then uses this value to compute (x ^ y) % z, by appropriately squaring, etc.
     * @param x
     * @param y
     * @param z
     * @return
     */
    public static int CalculatePowerModulo(int x, int y, int z)
    {
        int factor = x % z;
        if (y == 1)
        {
            return factor;
        }

        int value1 = CalculatePowerModulo(x, y/2, z);
        int value2;

        if (y % 2 == 0)
        {
            value2 = value1;
        }
        else
        {
            value2 = (factor * value1) % z;
        }

        return (value1 * value2) % z;
    }

- abhishekprateek July 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
long int power(long int x,long int y,long int z);
int main()
{  long int x=2;
   long int y=10;
    long int z=200000;
 printf("%ld",power(x,y,z));
 return 0;
}
long int power(long int x,long int y,long int z)
{ long int k;
if(y==0)
	return 1;
	if(y==1)
		return x%z;
	if(y%2==0)
	{ k=power(x,y/2,z);
	 k=k%z;
	 return((k*k)%z);
	}
 else
 {k=power(x,y/2,z);
	 k=k%z;
     k=(k)%z;
     x=x%z;
	 return((k*k*x)%z);
 }
	
#include<stdio.h>
#include<stdlib.h>
long int power(long int x,long int y,long int z);
int main()
{  long int x=2;
   long int y=10;
    long int z=200000;
 printf("%ld",power(x,y,z));
 return 0;
}
long int power(long int x,long int y,long int z)
{ long int k;
if(y==0)
	return 1;
	if(y==1)
		return x%z;
	if(y%2==0)
	{ k=power(x,y/2,z);
	 k=k%z;
	 return((k*k)%z);
	}
 else
 {k=power(x,y/2,z);
	 k=k%z;
     k=(k)%z;
     x=x%z;
	 return((k*k*x)%z);
 }
	


}
	

}

Hint : (ab) mod n = ((a mod n) (b mod n)) mod n.
Time Complexity: O(logb) for a^b;

- SC July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

principle: (a*b)mod n = ((a mod n)*(b mod n)) mod n
Apply: (a*a*a*a*a*a*)mod n = (((a*a)mod n)((a*a)mod n)((a*a)mod n)*(x mod n))mod n
SO, Code is;
int pow(int x, int y, int mod)
{
int res = 1;
while(y)
{
if(y & 1) res = res * x % mod;
x = x * x % mod;
y = y / 2;
}
return res;
}

- Anonymous July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int compute(int x, int y, int z) {
	int r = x % z;
	for (int i=0; i< y-1; i++) {
		r = r * x;
		r = r % z;
	}
	return r;
}

- rkt August 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ans = 1;
while(y>0)
{
  while(y%2==0)
  {p = ((p%z)*(p%z))%z;
  y/=2;
  }
  ans = (ans*p)%z; y--;
}

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

long long int pw(long long int a, long long int b,long long int ma)
{

long long int ans=1;
while(b)
{
if(b&1)ans=ans*a%ma;
b>>=1;
a=a*a%ma;
}
return (ans+ma)%ma;
}

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

long long int pw(long long int a, long long int b,long long int ma)
{
    
    long long int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%ma;
        b>>=1;
        a=a*a%ma;
    }
    return (ans+ma)%ma;
}

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

long long int pw(long long int a, long long int b,long long int ma)
{
    
    long long int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%ma;
        b>>=1;
        a=a*a%ma;
    }
    return (ans+ma)%ma;
}

- Jangwa May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any better solution that O(log(n)) ?

- amuchand47 July 27, 2018 | 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