## Skyscanner Interview Question for Software Engineers

Country: United Kingdom
Interview Type: Written Test

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

``````void
sum_powers_of_two(int n)
{
int i=1;
long sum=0;
int cnt=0;

while (cnt < n) {
printf("2 power %d = %d\n", cnt, i);
sum += i;
i = i << 1;
cnt++;
}

printf("Sum of first n powers of two is: %ld\n", sum);
}``````

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

(2<<N)-2

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

As requested, here's explanation:
Let's see all the powers of 2 between 1 and 4 (N=4)

``````N = 1 -> 0000010  (2^1 or 1<<1)
N = 2 -> 0000100  (2^2 or 1<<2)
N = 3 -> 0001000  (2^3 or 1<<3)
N = 4 -> 0010000  (2^4 or 1<<4)

sum   -> 0011110``````

We can compute 0011110 as 0100000 - "2"
So the answer is (1<<(N+1))-2 or (2<<N)-2

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

Thanks for the explanation.
Is there misprint in the last row of explanation, so it should be (2<<N)-2 and not (2>>N)-2?

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

Thanks. You're correct. I updated it

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

( 2^(N+1) ) - 2

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

An implementation without Bit shift

``````public int  bruteForceIt(int x){

int j = 1;
int y = 0;
for (int i = 1; i <= x; i++) {
if(x > 0){

j = j*2;
y += j;
System.out.println(j);
}
}
if(x == 0){
System.out.println("The Sum of Powers is" +  1);
return 1;
}

System.out.println("The Sum of Powers is" +  y);
return j;
}``````

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

Using bit shift to find the powers

``````public static void bitShitForSumower(int j){

int x = 1;
int y = 0;
for (int i = 0; i < j; i++) {
//bit shift
x = x<<1;
y += x;
System.out.println("x = " + x );
}

if( j == 0) System.out.println("The Some is 1");
else { System.out.println("The some is " + y);}

}``````

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

Hi guys, thanks for all the answers. I was able to produce brute force solution by calculating and adding powers inside the loop without bit manipulation but my solution didn't pass timing tests, correctness tests were ok.
Is it something obvious that if i is some power of two and you do i << 1, then power gets increased by 1? It looks very elegant but I have no idea how you come up with this solution.

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

See my explanation under (2<<N)-2 solution

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

Hey, this is not expected to pass via BruteForce.

Sum(2ˆx, 1<x<=N) = 2^N - 2

If you want to prove it (which the exercise doesnt ask), just do Mathematical induction on the powers of 2.

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

This can run in O(log x). This can run for any power function.

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

}

public static int power(int x){
return power(2,x);
}``````

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

``````function sum_power2(\$power)
{
\$total= 0;\$i=0;
while(\$i<=\$power)
{
\$total = \$total+ power_2(\$i);
\$i++;
}
echo \$total;
}
function power_2(\$i)
{
//base case
if (\$i==0) return 1;
if(\$i==1) return 2;
return power_2(\$i-1)*2;
}

sum_power2(3);``````

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

``````function sum_power2(\$power)
{
\$total= 0;\$i=0;
while(\$i<=\$power)
{
\$total = \$total+ power_2(\$i);
\$i++;
}
echo \$total;
}
function power_2(\$i)
{
//base case
if (\$i==0) return 1;
if(\$i==1) return 2;
return power_2(\$i-1)*2;
}

sum_power2(3);``````

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

Here is the formula : 2^(n+1) - 2

C# Solution :

``````private static int powerOfTwo(int power)
{
int result = 1;

for (int i = 0; i < power; i++)
result = result * 2;

return result;
}

private static int sumOfPowersOfTwo(int n)
{
return powerOfTwo(n + 1) - 2;
}``````

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

If only I could understand the question..

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

``````int n = 10;
int sum = 0;
for (int i = 0; i <= n; i++) {
sum += power(i, 2);
}

private int power(int i, int p)  {
if(p == 0) {
return 1;
}

if (i == 0) {
return 0;
}
else {
return i * i;
}
}``````

Does this not work ?

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

``````unsigned long long sumP2(unsigned long long n) {

return (1 << n ) - 1;
}``````

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.