## Google Interview Question for Software Engineers

• 3

Country: United States
Interview Type: In-Person

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

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

``````public void powerOf2Paths(int N) {
List<Integer> path = new ArrayList<>();
powerOf2PathsHelper(4, 0, path);
}

public void powerOf2PathsHelper(int N, int num, List<Integer> path) {
if(num == N) {
System.out.println(path);
}

for(int i = 0; num + (1 << i) <= N; i++) {
int sum = num + (1 << i);
powerOf2PathsHelper(N, sum, path);
path.remove(path.size() - 1);
}
}``````

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

It took me a little while to understand how interpret the possible paths.
The difference of two consecutive numbers in the path must be a number that can be computed as a power of 2. Then to compute the values of i you have to start from the end of the path subtracting the previous number and computing the power of two that give us that value. It is a little bit cumbersome so it think some examples will help to understand it better

``````[0 4] 4 - 0 is 4. Which power of 2 gives 4? 2 so i = 2
[0 2 4] 4 - 2 = 2, 2 - 0 = 2 so 2^1 and 2^1
[0 1 3 4] 1 2 1, so 2^0, 2^1 and 2^0``````

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

I assume the question is:
print sequences s where sum(s[i]) = N and s[i-1] <= s[i], s = 0, s[i] = 2^k, for any 0 <= k

that would be:

``````def sum_paths(N):
def aux(path, sum, j):
if sum == N:
res.append(path)
elif sum < N:
for i in range(j, int.bit_length(N)):
aux(path + [1 << i], sum + (1 << i), i)
res = []
aux(, 0, 0)
return res``````

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

or looking at the samples, it prints the path lengths or node-sums, which then is:
sum(s[i]) = N and s[i-1] <= s[i], s = 0, s[i] = sum(s[j]) + 2^k, for any 0 <= k and 0 < j < i

``````def sum_paths(N):
def aux(path, sum, j):
if sum == N:
res.append(path)
if sum < N:
for i in range(j, int.bit_length(N)):
aux(path + [sum + (1 << i)], sum + (1 << i), i)
res = []
aux(, 0, 0)
return res``````

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

``````unordered_map<int, vector<string>> cache;

vector<string> doDFS(int n)
{
if (n == 0) return {"0"};

if (cache.find(n) != cache.end())
return cache[n];

vector<string> res;

for (int exp = 1; n >= exp; exp <<= 1)
{
vector<string> ret = doDFS(n - exp);

for (string path : ret)
res.push_back(path + "," +to_string(n));
}

cache[n] = res;
return res;
}``````

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

In pure declarative form, using recursion - which can easily be removed:

``````def _recurse_(target,path){
if ( target == path[-1] ){
println( path )
return
}
diff = target - path[-1]
power_options = list([0:diff]) as { break( 2 ** \$.o > diff) ; \$.o }
for ( pow_2 : power_options ){
new_cur = path[-1] + ( 2 ** pow_2 )
_recurse_ ( target, path + new_cur )
}
}

def print_paths(n){
_recurse_(n,)
}
print_paths(4)``````

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

Short and simple:

``````// The idea is to start from 0
// then add 1 & 2 (two function calls)
// until we reach the max

import java.util.*;
class Main{

// Print combi

public static void printCombi(ArrayList<Integer> ar, int curr, int max)
{
if(curr<max){
if(curr+1<=max){
printCombi(new ArrayList<>(ar), curr+1, max);// Adding 2^0
}
if(curr+2<=max){
printCombi(new ArrayList<>(ar), curr+2, max);// Adding 2^1
}
}
else if(curr>=max){
ar.add(max);      // **** If the current exceeds max, then insert max not current
print(ar);
return;
}
}

// Driver

public static void main(String...args){
printCombi(new ArrayList<Integer>(), 0, 6);
}

// Utility function

public static void print(ArrayList<Integer> ar){
for(int i : ar){
System.out.print(i+" ");
}
System.out.println();
}
}``````

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

Improved Slightly

``````// The idea is to start from 0
// then add 1 & 2 (two function calls)
// until we reach the max

import java.util.*;
class Main{

// Print combi

public static void printCombi(String str, int curr, int max)
{
if(curr>=max){
System.out.print(str+max+"]\n");
}
else{
if(curr+2<=max)
printCombi(str+curr+",",curr+2, max);
if(curr+1<=max)
printCombi(str+curr+",",curr+1, max);
}
}

// Driver

public static void main(String...args){
printCombi("[0,",1, 4);
printCombi("[0,",2, 4);
}
}``````

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

``````def find_max_exp(N):
for i in range(N):
if 2**i <= N and 2**(i+1) > N:
return i
paths_dict= {}

def find_paths(N):
if N in paths_dict.keys():
return paths_dict[N]
if N < 0:
return None
if N == 0:
return []
max_exp = find_max_exp(N)
all_paths = []
for i in range(0, max_exp+1):
paths = find_paths(N - 2**i)
if paths == []:
continue
for path in paths:
all_paths.append(path + [N])
paths_dict[N] = all_paths
return all_paths``````

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

Skip lists ? form a linked list of 0,1,2,4,etc. and print all paths from head to tail.

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

``````import java.util.ArrayList;
import java.util.List;

public class PowerOf2s {

public static void main(String[] args) {
// TODO Auto-generated method stub

//You can change the number 4 below as you wish
pr(4);
}

public static void print(int no, int base, List<Integer> l, int noAdd) {

int sum = sum(l);
if (sum == no) {
int sum_ = 0;
String res = "[";
for (Integer i: l) {
sum_ += i;
res += sum_ + ",";
}
res = res.substring(0, res.length() - 1) + "]";
System.out.println(res);
return;
} else if (sum > no) {
return;
}

for (int i = 0; i <= base; i++) {
int add = (int) Math.pow(2, i);
}

return;
}
public static void pr(int no) {
int base = (int) (Math.log(no) / Math.log(2));
print(no, base, new ArrayList<Integer>(), 0);
}

public static int sum(List<Integer> l) {
int sum = 0;
for (int n: l) {
sum += n;
}
return sum;
}
}``````

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

``````void PrintPaths(int n, vector<int> &comb, int sum = 0)
{
if (n == 0) {
cout << 0 << (comb.empty() ? "" : ", ");
for (int v : comb) {
cout << v << ", ";
}
cout << "\n";
return;
}
if (n < 0) {
return;
}
for (int v = 1; n - v >= 0; v <<= 1) {
comb.push_back(sum + v);
PrintPaths(n - v, comb, sum + v);
comb.pop_back();
}
}``````

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

``````public static void main(String args[]) {
int N = 4;
List<Integer> list = new ArrayList<Integer>();
print(N, 0, list);
}

/**
Starting from num = 0, add 2^i (where i can be any non-negative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0
*/

public static void print(int N, int sum, List<Integer> list){
if(sum > N)
return;
if(sum == N){
System.out.println(list);
return;
}

int i = 0;
while(((int)Math.pow(2, i) + sum) <= N){
int n = (int)Math.pow(2, i) + sum;
print(N, n, list);
list.remove(new Integer(n));
i++;
}
}``````

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

``````import math

def printPaths(N, path):
if path[-1] == N:
print(path);
if path[-1] > N:
return;
for idx in xrange(int(math.log(N,2))+1):
path.append(int(path[-1] + math.pow(2, idx)));
printPaths(N, path);
path.pop();

printPaths(6, );``````

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.