Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

Unfortunately, I haven't seen the "expected" solutions here, so I'll put them.

1) L=3486784401 is the largest power of 3 that fits into 32 bits, so if L mod x == 0, then x is a power of 3.

int is_power_of_3(uint32_t x) return x ? ((3486784401 % x) == 0): 0

2) We can see that if we take all powers of 3 and take mod 255, all numbers will be unique, so we can use lookup table of size 256 and check "x & 0xFF" in it.

- emb August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

mod 256

- Dave September 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I can't figure out why 1) is always true. Why is it the case that there doesn't exist some number x such that L % x == 0 and x is not a power of 3? Is this solution unique to finding powers of 3, or would it work if we were checking for powers of any such number x?

- Kyle September 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, kyle. Because if L % x == 0, then x's factors must be L's factors, but the only factor of L is 3, so x is a power of 3

- malinbupt September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

int is_power_of_3(UInt32 n)
        {
            double y = Math.Log10(n) / Math.Log10(3);

            if ((y - (int)y) == 0.0)
            {
                return 1;
            }
            else
                return 0;
        }

- Machbah August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, this code works..is it efficient ?

- vish August 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the best solution. a little more elegant:

int is_power_of_3(UInt32 n)
{
double y = Math.Log10(n) / Math.Log10(3);
return (y - (int)y) == 0.0 ? 1 : 0;
}

- David September 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one of the best solution and neat too.

- Geek September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There may be bit hacks, but can't we just pre populate a set with all the powers of 3? and then is_power_of will just return if the number contains in set or not O(1)?

- Amit August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you want to check for: let's say 3^1000000000 ?

- Anonymous August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Then it can't be passed as uint32_t.

- Anonymous August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

look up the size of an unsigned int.. 2^32.

- Anonymous August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

my point was since the number is unsigned int, that means 32 bit. here we have a finite set of numbers.

- Amit August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ok, what if you have limited memory then? This might be one solution but it's not the most optimal one.

- Anonymous August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we just store all the powers of 3 in a set and return set contains from is_power_of_3?

- Amit August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"all the powers of 3" is an infinite set

- jyim August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, but the question says that the given number would be unsigned int. Int is 32 bit, therefore the set of power of 3 within 32 bit is finite.

- Amit August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Add all the digits of the number until it becomes a single digit
2. If result is 9, it is a power of 3 else not

- hanish wadhawan August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you're thinking of a divisibility rule. First of all, the digit sum doesn't have to equal 9, it just have to be divisible by 9.

However, there are a bunch of other problems. First of all, you're not checking for a power of three, you're checking for a multiple of 9. For example, 18 is not a power of 3 but 1+8 = 9, and will therefore return true with your way.

In addition, even if this worked, it would miss the initial ones since the first power it can detect is 9. It will miss 3^0 (=1) and 3^1 (=3)

- Siretu August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are only a few dozen 32-bit integers that are a power of 3.
Stores these in some sort of hash set.
This becomes a direct lookup.

OR tail recursively (convert it to a loop the usual way if you care):

bool isPowerOf3(int x)   
{
	if(x==1) return true;
	if(x%3) return false;
	return isPowerOf3(x/3);
}

Or combine BOTH ideas above: use the recursion and the hashSet as the memo of the recursion calls (this prevents you from preprocessing the hashSet elements).

- Q August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are many ways to solve this, a few examples are: while loop, recursive function, or hash map.

Hash map will have the fastest execution time but will require lots of memory and some setup to build the map in the beginning. Here is an example of the other 2:
While Loop:

int is_power_of_3 (int n){
    int result =0;
    int i = 1;
    if (n == 1) return 1; // base condition: 3^0
    if ((n%3)!=0) return 0; // pow3 must be divisible by 3 (no remainder)
    while (i < n){
        i*=3;
        if (i==n)
         result = 1;
    }
    return result;
}

And recursively:

int is_power_of_3 (int n){
    if ((n%3)!=0) return 0; // pow3 must be divisible by 3 (no remainder)
    if (n<=3){  // base condition to stop recursion
        if (n == 3 || n == 1)
            return 1;
        else 
            return 0;
    }
    else 
     return isPow3(n/3);
}

For recursion it is imperative that you check modulo 3 first since you are working with integers and it will truncate any fraction when you do the n/3 recursive call. For the while loop it's just a quick check to save some execution time, but it's not necessary. I'll leave the hash map solution for you to try on your own.

- Steve August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something faster that log(N) ? the straightforward loop is log in base 3 of N iterations

- Vladimir August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is_power_of_3(int i)
{
long a = 3;//make sure a won't overflow

do {
if(a == i)
{
return true;
}
a *= 3;

} while (a <= i);

return false;
}

- cdhsiung August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is_pow(v,3);

int is_pow(unsigned int v, int n) {
	if (n<2) return 0;
	if (v==0) return 0;
	while(v%n==0) {
		v/=n;
	}
	if (v==1) return 1;
	return 0;
}

- drmay August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Number should be end with 1 or 3 or 7 or 9 and sum off all digits should be 9
then the number is power of 3.
ex: 243, 6561

- xxxx August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

63

- gerula August 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

{
if any number satisfies below condition then it was power of 3
Number should be end with 1,3,7,9
and sum of all digits should be 9(cumulative sum)
}

- xxxx August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

99

- audi October 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

number should be end with 1,3,7,9
and sum of all digits(cumulative sum) should be 9.
if any satisfies above properties then it will be power of 3.

- aaa August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution fails for 63.

- sid1505 August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

return n == power(3, round(log(n) / log(3)))

- Alistair August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For any n>1.

bool isPowerOf_N(int num,int n){
	if(num==1)
		return true;
	if(num<=0||num%n!=0)
		return false;
    return isPowerOf_N(num/n,n);
}

- jackdanielsparrow August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could we just precompute all 3^x for unsigned ints and store them in HashTable?
It shouldn't be too big and look up should be O(1)

- Je August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution

#include <iostream>
using namespace std;
bool powerOf3(int input)
{
  if (input == 1)
    return true;
  else if (input == 0 || (input % 3)!=0)
    return false;
  return powerOf3(input/3);
}

- hankm2004 August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int isPowerOfThree(int number) throws Exception {
		if (number < 2) throw new Exception("Invalid number!");
		return (Math.log(number)/Math.log(3) % 1 > 0) ? 0 : 1;
}

- samit.roy September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int is_power_of_3(uint32_t n){
	
	double a = (double)sqrt(n);
	
	if(n%3 != 0 && n!=0){
		return 0;
	}else if(n%3 == 0 && a-ceil(a) == 0.0 && n!=0){
		return 1;
	}else if(n%3 == 0 && a-ceil(a) != 0.0 && n!=0){
		double a = (double)sqrt(n/3);
		if(a-ceil(a) == 0.0){
			return 1;
		}
		return 0; 
	}
	
	
	return 0;
}

- rhenobudiasa September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

33 /*
 34  * logic : calculate the differene between count of odd and even count set bits
 35  * if it is multiple of 3 , then the number is a multiple of 3. function return 1 or 0
 36  */
 37 int checkMultipleOf3(int n){
 38 
 39     int even_c = 0, odd_c = 0;
 40 
 41     if(n<0)
 42         n = -n;
 43     if (n == 0)
 44         return 1;
 45     if(n == 1)
 46         return 0;
 47 
 48     while(n > 0){
 49 
 50         if(n&1)
 51             odd_c++;
 52         n = n>>1;
 53         if(n&1)
 54             even_c++;
 55 
 56         n = n>>1;
 57     }
 58     return(abs(odd_c - even_c));

- vivekh September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use power of binary search to get the answer. Lower bound will be 3 and higher bound will be UINT_MAX.
1. Multiply 3 by ONE times of itself.
2. Multiply 3 by TWO times of itself.
3. Multiply 3 by FOUR times of itself.
4. Multiply 3 by Eight times of itself.
5. Multiply 3 by SIXTEEN times of itself.

After some time you will know the range in which the given number falls. So suppose the number falls in the range between 8 and 16, we can change the lower bound to (8 times of 3) and higher bound to (16 times of 3). Again run the same algorithm. Stopping condition will be either you find the number or your number exists in the range when range only differs by 1 and in that case it is not multiple of 3.

- aka September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use power of binary search to get the answer. Lower bound will be 3 and higher bound will be UINT_MAX.
1. Multiply 3 by ONE times of itself.
2. Multiply 3 by TWO times of itself.
3. Multiply 3 by FOUR times of itself.
4. Multiply 3 by Eight times of itself.
5. Multiply 3 by SIXTEEN times of itself.

After some time you will know the range in which the given number falls. So suppose the number falls in the range between 8 and 16, we can change the lower bound to (8 times of 3) and higher bound to (16 times of 3). Again run the same algorithm. Stopping condition will be either you find the number or your number exists in the range when range only differs by 1 and in that case it is not multiple of 3.

- aka September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can convert the number from base 10 to base 3, then expect to find a single digit = 1.

- cristian September 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use binary search to get answer

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

- smalex September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use binary search to get answer.

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

- smalex September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use binary search to get answer.

#include <iostream>

using namespace std;

int main() {
  int number;
  cin >> number;

  int lo = 1;
  int hi = 1860;

  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int t = mid * mid * mid;
    if (t < number) {
      lo = mid + 1;
    } else if (t > number) {
      hi = mid - 1;
    } else {
      cout << "YES" << "\n";
      return 1;
    }
  }
  cout << "NO" << "\n";
  return 0;
}

- smalex September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another bit manipulation solution is to start from 1 and keep multiplying with 3 till the number is greater than or equal to the given number. For multiplying by 3, we left shift the bits by 1 and add the number. Not sure if this is a good solution:

public class IsPowerOfThree {
    public static void main(String[] args)
    {
        int num = 82;
        
        int x = 1;
        while(x < num)
        {
            int temp = x;
            int temp1 = x << 1;
            x = temp + temp1;
        }
        
        if (x == num)
        {
            System.out.println("Num is a multiple of 3");
        }
        else
        {
            System.out.println("Num is not a multiple of 3");
        }
    }
}

- Anon April 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Number will be power of 3 if their bits sum is divisible by 3.

- Pujan June 24, 2016 | 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