Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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
I assume the question is:
print sequences s where sum(s[i]) = N and s[i-1] <= s[i], s[0] = 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, 0)
return res
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] = 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, 0)
return res
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;
}
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,[0])
}
print_paths(4)
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){
ar.add(curr);
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();
}
}
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);
}
}
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 [[0]]
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
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) {
l.add(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);
print(no, base, new ArrayList<Integer>(l), add);
}
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;
}
}
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();
}
}
public static void main(String args[]) {
int N = 4;
List<Integer> list = new ArrayList<Integer>();
list.add(0);
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;
list.add(n);
print(N, n, list);
list.remove(new Integer(n));
i++;
}
}
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!
- aonecoding August 09, 2017