## Google Interview Question for SDE1s

• 4

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]=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];
}``````

Comment hidden because of low score. Click to expand.
2
of 2 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 = 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];
}``````

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.
*/
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) )``````

Comment hidden because of low score. Click to expand.
1
of 1 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 = true;
for( auto num : nums ){
for( int i = num ; i <= target ; ++i )
dp[i] = dp[i] | dp[i-num];
}
return dp.back();
}``````

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*nums + f*nums + f*nums ... 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*target/nums*..*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
if factorSumRecursion(nums, target, i - 1): return True
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``````

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])``````

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{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 { 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);
}

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]}*{j + 1} + {mults[ii]}*{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

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

``````def combinationSum(nums,target):
dp=[False]*(target+1)
dp=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]``````

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;
}

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()
{
cin>>ch;
while(ch[i])
{
if(ch[i]=='A')
{
}
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;
}

{
return 0;
}
i++;
}
return 1;

}

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] = 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];
}``````

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

``````#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

bool CanBeComposed(const vector<int>& a, int target, unordered_map<uint64_t, bool>& memo, int idx = 0)
{
if (idx < 0 || idx > a.size() || target < 0)
{
return false;
}
if (target == 0)
{
return true;
}
if (idx == a.size())
{
return false;
}
if (a[idx] == 1)
{
return true;
}

uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | target;
auto it = memo.find(memo_key);
if (it != memo.end())
{
return it->second;
}

bool res = false;
if (a[idx] == 0)
{
res = CanBeComposed(a, target, memo, idx + 1);
}
else
{
for (int i = 0; i * a[idx] <= target && !res; ++i)
{
res = CanBeComposed(a, target - i * a[idx], memo, idx + 1);
}
}
memo[memo_key] = res;
return res;
}

bool CanBeComposed2(const vector<int>& a, int target)
{
vector<bool> dp;
dp.resize(target + 1, false);
dp = true;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] == 1)
{
return true;
}
for (int j = 0; j + a[i] < dp.size(); ++j)
{
int k = j + a[i];
dp[k] = dp[k] | dp[j];
}
}
return dp[target];
}

int main()
{
vector<int> a = {6, 9, 20};
int target  = 47;
unordered_map<uint64_t, bool> memo;
cout << CanBeComposed(a, target, memo) << "\n";
cout << CanBeComposed2(a, target) << "\n";
return 0;
}``````

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);

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;
}``````

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);

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;``````

}

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);

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;
}``````

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++;
}
}
}``````

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.