Google Interview Question for SDE1s


Country: United States




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

dp optimal solution in java
 public static boolean combinationSum(int[] nums, int target) { 
      if(target==0)
          return true;
     if(nums.length==0)
         return false;
     boolean[][] dp= new boolean[nums.length+1][target+1];
     for(int i=0;i<=nums.length;i++)
         dp[i][0]=true;
     for(int i=1;i<=nums.length;i++){
         for(int j=nums[i-1];j<=target;j++){
             if(dp[i-1][j]==true){
                 dp[i][j]=true;
                 continue;
             }
              for(int k=1;k<=j/nums[i-1];k++){
                  if(dp[i][j-nums[i-1]*k]==true){
                      dp[i][j]=true;
                  break;
                  }
              }
         }
     }
     return dp[nums.length][target];
}

- deep March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* 
A better way to look it using sequences
Define a Sequence S, such that it is strictly increasing 
and generated by the rule of sum of non-negative multiples of the numbers in the array.
Thus, S(0) = 0 and we go in a = [6,9,20]
   S(1) = 6 
   S(2) = 9 
   S(3) = 12 = 6 * 2  
   S(4) = 15 = 6 + 9 
   S(5) = 18 = ( 3 * 6 , 9*2 ) 
We use ZoomBA to solve it and show a nice pattern.
This is solvable by adding 6,9,20 to each item encountered before in the sequence, 
and check if the current item is minimum of the larger item than the current max 
Then the next item is generated. Thus, the problem is solved when we have 
   Target n is such that 
   S(k) < n <= S(k+1)
To generate the this array a from bases is easy, and can be left as an exercise to the reader.
Hint: use the same algorithm and start with 0,min_of_base 
*/
bases = [6,9,20]
// first few items of the sequence from the bases till 20 
a = [ 0, 6, 9, 12 , 15 , 18, 20 ] 
s = seq( a ) -> {
  cached = $.p // previous items 
  last_no = cached[-1] // last item 
  maxes = list ( bases ) -> {
    item = $.o // store the individual base items 
    ix = index ( cached ) :: { $.o + item > last_no }
    cached[ix] + item  // we find where we max - so store it 
  }
  #(min,Max) = minmax( maxes ) // find min of the maxes 
  min // return min as the next item in the sequence 
}
// now call 
def find_some( n ){
   if ( n <= s.history[-1] ) return n @ s.history // obvious 
   while ( s.history[-1] <= n ){ s.next } // iterate over 
   return n @ s.history // and then is trivial 
}
println( find_some(47) )
println( find_some(23) )

- NoOne March 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is essentially the same as the coin change problem. Below is a little different approach which works if the required number 'n' is reasonably small. Time Complexity is O(n)

public static boolean combinationSum(int[] items, int sum) {
    boolean[] possible = new boolean[sum+1];
    possible[0] = true;
    for (int i=0; i<=sum; i++) {
      if (possible[i]) {
        for (int j=0; j<items.length; j++) {
          if (i+items[j] <= sum) {
            possible[i+items[j]] = true;
          }
        }
      }
    }
    return possible[sum];
  }

- challapallirahul March 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''
Introduction:
- The sum can be made up of multiple terms
  e.g. f[0]*nums[0] + f[1]*nums[1] + f[2]*nums[2] ... f[n-1]*nums[n-1]
  note: 0 <= f[i] <= floor(target/nums[i])
- Find a solution that works for big numbers efficiently as well
  
Solution Brute Force:
try all f[i] and check if any combination would
lead to target. Of course one can stop trying if target is exceeded
runtime: O(target/nums[0]*target/nums[1]*..*target/nums[n-1]) 

Optimization Idea: keep calculated sums
Idea: keep intermediary sums and check every time if the value needed to 
reach target has already been calculcated
--> this can accellerate to find a solution if one exists, but if none exists 
    it doesn't help

Optimization Idea: try to avoid double work
If we checked target - 14 and know it doesn work, we shouldn't retry if we get to "14" in an other way

Optimization Idea: Recursion with memoization could look like:
It's not neat, but I couldn't come up with something better within 30 Minutes:
- f(t, i) = f(t-k*nums[i], i - 1), as long as i >= 0 for each k between 0 and t >= k*nums[i]
Memoization I would use to avoid rechecking the same sub-problems again and again meaning, with nums in 
the range from [0..k] I mark the values i can't construct with
'''

def factorSumRecursion(nums, target, i):
    global memo
    if target < 0 or i < 0 or target in memo[i]: return False
    if target == 0: return True
    if target >= nums[i] 0:
        if factorSumRecursion(nums, target - nums[i], i): return True
        else: memo[i].add(target - nums[i])
    if factorSumRecursion(nums, target, i - 1): return True
    else: memo[i-1].add(target)
    return False

def factorSum(nums, target):
    global memo
    memo = [set() for i in range(len(nums))]
    if len(nums) == 0: return target == 0
    return factorSumRecursion(nums, target, len(nums)-1)

print(factorSum([6,9,20], 47)) #3*9 + 20
print(factorSum([6,9,20], 48)) #8*6
print(factorSum([6,9,20], 49)) #2*20 + 9
print(factorSum([6,9,20], 50)) #1*20 + 5*6
print(factorSum([6,9,20], 12)) #2*6
print(factorSum([6,9,20], 13)) #False
print(factorSum([6,9,20], 9)) #9

- ChrisK March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def Combinations(num,deduct=0,combs=[]):
    num = num - deduct
    if num == 0:
        combs.append(deduct)
        return True
    elif num < deduct:
        return False
    else:
        if deduct != 0:
            combs.append(deduct)
        if Combinations(num,20,combs) or Combinations(num,9,combs) or Combinations(num,6,combs):
            return True,combs
        else:
            if len(combs)> 0 :
                combs.pop()
            return False
print Combinations(24,0,[]) #returns (True, [9, 6, 9])
print Combinations(13,0,[]) #returns False
print Combinations(47,0,[]) #returns (True, [20, 9, 9, 9])

- ankitpatel2100 March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I found 2 solutions, a simple for multiples of 2 elements and recursive approach involving multiples of all elements.
The first and the simplest approach is to build a table of all possible multiplies and sum them with each other, this would work with A={6,9,20} and T=47 but is limited to only multiples of 2 elements. This method will fail with A={7411, 9461, 20161, 1901, 1531, 281} and T=27751.
The second approach would recursively go through all multiples of all elements (without using multiples of the same elements) and so it may engage a multiple element in A. This approach will work if the target T comprises of multiples of 3 and more elements of A.

static void Main(string[] args)
        {
            int[] arr = new int[6]{7411, 9461, 20161, 1901, 1531, 281};
            var target = 27751;
            Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
            // testing with big primes
            Console.WriteLine("Simple:");
            FindComboSimple(arr, target); // 2 primes can not produce 27751
            Console.WriteLine("Recursive:");
            FindComboRec(arr, target); // 3 or more primes can prodice 27751
            //testing given example
            arr = new int[3] { 6,9,20 };
            target = 47;
            Console.WriteLine($"Values: {string.Join(", ", arr)}; Target = {target}");
            Console.WriteLine("Simple:");
            FindComboSimple(arr, 47);
            Console.WriteLine("Recursive:");
            FindComboRec(arr, 47);
            Console.ReadLine();
        }

        public static void FindComboSimple(int[] ar, int target)
        {
            var mults = new int[ar.Length][];
            // calculating all possible multiplies which are less then target
            for (int i =0; i < ar.Length; i++)
            {
                if (ar[i] == 0)
                    continue;
                var maxKoef = target / ar[i];
                mults[i] = new int[maxKoef - 1];
                for (var k = 0; k < maxKoef - 1; k ++)
                    mults[i][k] = ar[i] * (k + 1);
            }
            // adding every possible mults with each other to find target
            for(var i = 0; i < mults.Length; i++)
            {
                for (var j = 0; j < mults[i].Length; j++)
                {
                    for (var ii = i; ii < mults.Length; ii ++)
                    {
                        if (ii == i)
                            continue;
                        for (var jj = 0; jj < mults[ii].Length; jj ++)
                        {
                            if (mults[i][j] + mults[ii][jj] == target)
                            {
                                Console.WriteLine($"{target} = {mults[i][0]}*{j + 1} + {mults[ii][0]}*{jj + 1}");
                                return; 
                            }
                        }
                    }
                }
            }
        }

        public static bool FindComboRec(int[] arr, int target, int ipos = -1, int val = 0, string currentExpr = "")
        {
            for(var i = ipos + 1; i < arr.Length; i++)
            {
                if (arr[i] == 0)
                    continue;
                for(var j = 0; j < target / arr[i] ; j ++)
                {
                    var currentValue = arr[i] * j + val;
                    if (currentValue == target)
                    {
                        Console.WriteLine($"{target} = {arr[i]}*{j}{currentExpr}");
                        return true;
                    }
                    else
                    {
                        var expr = (j != 0 ? (currentExpr + $" + {arr[i]}*{j}" ):currentExpr);
                        if (FindComboRec(arr, target, i, currentValue, expr))
                            return true;
                    }
                }
            }
            return false;
        }

Output:

Values: 7411, 9461, 20161, 1901, 1531, 281; Target = 27751
Simple:
Recursive:
27751 = 281*5 + 1901*5 + 1531*11
Values: 6, 9, 20; Target = 47
Simple:
47 = 9*3 + 20*1
Recursive:
47 = 20*1 + 9*3

- goabove1970 March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def combinationSum(nums,target):
    dp=[False]*(target+1)
    dp[0]=True
    nums.sort()
    for i in xrange(1,target+1):
        for n in nums:
            if i-n>=0 and dp[i-n]:
                dp[i]=True
    
    return dp[target]

- zyjdxtc March 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

By recursively checking a number multiple times if it contributes to target and going to next numeber in the array recursively


public static boolean isumOfmultiplier(int[] in, int sum) {
return auxIsSumOfmultiplier(in,in.length,sum);

}

public static boolean auxIsSumOfmultiplier(int[] in, int position, int sum) {
if (sum == 0)
return true;
if (position == 0)
return false;
boolean finalResult = false;
int multiplier = 0; // to use number multiple times for the sum
if (in[position - 1] == 0) { // if zero is in the array, skip and goto next
// level i.e position-1 recursively
return auxIsSumOfmultiplier(in, position - 1, sum);
}
while (sum - multiplier * in[position - 1] >= 0) {
finalResult = auxIsSumOfmultiplier(in, position - 1, sum - multiplier * in[position - 1]);
if (finalResult)
break;
multiplier++;
}
return finalResult;
}

- Prahlad March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool combinationSum( const vector<int>& nums , int target ){
	const int n = nums.size();
	if( n == 0 )
		return false;

	vector<bool> dp( n + 1 , false );
	dp[0] = true;
	for( auto num : nums ){
		for( int i = num ; i <= target ; ++i )
			dp[i] = dp[i] | dp[i-num];
	}
	return dp.back();
}

- anonymous March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
char ch[20],mask1=0,mask2=0,i=0;
cin>>ch;
while(ch[i])
{
if(ch[i]=='A')
{
mask1++;
}
if(strlen(ch)>(i+2)){
if((ch[i]=='A'||ch[i]=='L')&&(ch[i+1]=='A'||ch[i+1]=='L')&&(ch[i+2]=='A'||ch[i+2]=='L'))
return 0;
}

if(mask1==2)
{
return 0;
}
i++;
}
return 1;

}

- Tanvir March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there are other people like me who got confused what the problem actually states, this is what is being asked: given a number like 47 and array A = [6, 9, 20] determine whether the given number can be decomposed as:

47 = 6*a + 9*b + 20*c where a, b, c >= 0.

This is basically a variation of coin changing problem.

C++

bool checkSum(const vector<int>& A, int Sum){
    vector <vector<bool>> D(A.size() + 1, vector<bool>(Sum + 1, false);
    
    for(int i = 0; i <= A.size(); i++){
        D[i][0] = true;
    }

    for(int i = 1; i <= Sum; i++){
        for(int j = 1; j <= A.size(); j++){
            D[i][j] = D[i-1][j];
            if(j - A[i - 1] >=0){
                D[i][j] = D[i][j] || D[i][j - A[i - 1]];
            }
        }
    }

    return D[A.size()][Sum];
}

- wanderMan April 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int main()
{
    int nums[] = { 6, 9, 20};

    int size = sizeof(nums)/sizeof(nums[0]);

    int target = 47;

    if (combinationSum(nums, size, target)) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}

bool combinationSum(int a[], int size, int target)
{
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) {
                continue;
            }

            if (target < a[i]) {
                return false;
            }

            int k = 1;
            while ((a[i] * k) < target) {

                int diff = target - (a[i] * k);

                if (diff % a[j] == 0) {
                    return true;
                }
                k++;
            }
        }
    }

    return false;
}

- vino28 March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int main()
{
    int nums[] = { 6, 9, 20};

    int size = sizeof(nums)/sizeof(nums[0]);

    int target = 47;

    if (combinationSum(nums, size, target)) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}

bool combinationSum(int a[], int size, int target)
{
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) {
                continue;
            }

            if (target < a[i]) {
                return false;
            }

            int k = 1;
            while ((a[i] * k) < target) {

                int diff = target - (a[i] * k);

                if (diff % a[j] == 0) {
                    return true;
                }
                k++;
            }
        }
    }

    return false;

}

- vino28 March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int main()
{
    int nums[] = { 6, 9, 20};

    int size = sizeof(nums)/sizeof(nums[0]);

    int target = 47;

    if (combinationSum(nums, size, target)) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}

bool combinationSum(int a[], int size, int target)
{
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) {
                continue;
            }

            if (target < a[i]) {
                return false;
            }

            int k = 1;
            while ((a[i] * k) < target) {

                int diff = target - (a[i] * k);

                if (diff % a[j] == 0) {
                    return true;
                }
                k++;
            }
        }
    }

    return false;
}

- vino28 March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

for(int i = 0; i < size - 1; i++)
{
	for(int j = 0; j < size; j++)
	{
		if(((target - a[i+j]) % i ) == 0)
		{
			count++;
		}
	}
}

- saz March 17, 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