Google Interview Question for Software Engineers


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<>();
        path.add(0);
        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);
            path.add(sum);
            powerOf2PathsHelper(N, sum, path);
            path.remove(path.size() - 1);
        }
    }

- aonecoding August 09, 2017 | Flag Reply
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

- Fernando August 09, 2017 | Flag Reply
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] = 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

- Chris August 09, 2017 | Flag Reply
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] = 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

- Chris August 09, 2017 | Flag Reply
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;
}

- sheva August 10, 2017 | Flag Reply
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,[0])
}
print_paths(4)

- NoOne August 10, 2017 | Flag Reply
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){
      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();
  }
}

- Anwar August 10, 2017 | Flag Reply
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);
  }
}

- Anwar August 10, 2017 | Flag Reply
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 [[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

- LP August 11, 2017 | Flag Reply
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.

- Anonymous August 12, 2017 | Flag Reply
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) {
		
		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;
	}
}

- cemaivaz August 17, 2017 | Flag Reply
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();
	}
}

- Alex August 26, 2017 | Flag Reply
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>();
        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++;
        }
    }

- sudip.innovates October 06, 2017 | Flag Reply
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, [0]);

- koustav.adorable August 10, 2017 | 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