## Google Interview Question for Interns

Team: Software Engineering
Country: Brazil
Interview Type: In-Person

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

``````function f (x, n) {
if (n < 0) {
return f(1 / x, -n)
} else if(n === 0) {
return 1
} else if(n === 1) {
return x
} else if(n % 2 === 0) {
return f(x * x, n / 2)
}
return x * f(x * x, (n - 1) / 2)
}

module.exports = f
// O((n log(x))^k)``````

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

My version of solution is:

``````static double fastExponent(double value, int power) {
// For all cases any number at power 0 is 1
if (power == 0) {
return 1;
}
// Any number at power 1 is the same number
if (power == 1) {
return value;
}
// If value equals to 0, than at any power (except 0, but this case has been checked above) is 0
if (value == 0) {
return 0;
}
// Negative power is equals to 1/(value^power)
if (power < 0) {
return 1 / fastExponent(value, -power);
}

// Check if power is even number
if ((power >> 1) << 1 == power) {
double preCalculatedValue = fastExponent(value, power >> 1);
return preCalculatedValue * preCalculatedValue;
}

return value * fastExponent(value, power - 1);
}``````

List of tests in format {<value>, <power>, <expected result>

``````{1000, 0, 1},
{3, 1, 3},
{0, 0, 1},
{0, 1000, 0},
{-2, 3, -8},
{-2, 4, 16},
{-2, -4, 0.0625},
{-2, -3, -0.125},
{1.01, 1000, 20959.155637813660064},
{2, 10, 1024.0},
{10, 13, 10000000000000.0}``````

Since in worst case we will have following sequence of powers:
odd -> even -> odd -> even and so on.
Ex: if power = 15 the function will be called with following value as a power:
15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
So, amount of sequences (odd -> even) is ~log(n) since every time we dividing by 2; Considering that number of operations in the pair is 2, result will be ~2*log(n) or just O(log(n)).

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

``````// A slightly improved version of Mike L's solution
static double fastExponent(double value, int power) {
// For all cases any number at power 0 is 1
if (power == 0) {
return 1;
}
// Any number at power 1 is the same number
if (power == 1) {
return value;
}
// If value equals to 0, than at any power (except 0, but this case has been checked above) is 0
if (value == 0) {
return 0;
}
// Negative power is equals to 1/(value^power)
if (power < 0) {
return 1 / fastExponent(value, -power);
}

// Check if power is even number
if ((power >> 1) << 1 == power) {
double preCalculatedValue = fastExponent(value, power >> 1);
return preCalculatedValue * preCalculatedValue;
}
// The below two lines slightly improves the performance compared to Mike L's original solution
double preCalculatedValue = fastExponent(value, power >> 1);
return value * preCalculatedValue * preCalculatedValue;
}``````

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

``````#include <stdio.h>

int fe(int a, int b) {
if (b <= 0) {
return 1;
} else if (b == 1) {
return a;
} else if (b == 2) {
return a*a;
} else if (b%2 == 0) {
return fe(fe(a,b/2),2);
} else {
return a*fe(fe(a,(b-1)/2),2);
}
}

int main() {
printf("%d\n", fe(2,4));
}``````

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

``````double myPow(double x, int n) {
if( n < 0 )
return dfs( 1.0 / x , -(long long)n );
return dfs( x , n );
}

double dfs( double x , long long n ){
if( n == 0 )
return 1.0;

double t = ( n % 2 ) ? x : 1.0;
return t * dfs( x * x , n / 2 );
}``````

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

int exponentiation(int base, int power)
{
if (power ==0)
{
return 0;
}

else if (power == 1)
{
return base;
}

power--;
base *= exponentiation(base,power);

return base;
}

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

``````int exponentiation(int base, int power)
{
if (power ==0)
{
return 0;
}

else if (power == 1)
{
return base;
}

power--;
base *= exponentiation(base,power);

return base;
}``````

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.