Google Interview Question for Software Developers

Country: United States
Interview Type: In-Person

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

leetcode 494.
take a look on the 282 - similar

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

This problem can be proven to be NP-complete. There is a pseudo-polynomial algorithm (subset sum) that can solve it.

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

The optimal solution should be the one using pseudo-polynomial algorithm for the partition problem. Hope this is correct:

``````def is_magic(seq, magic_number):
# sum(seq) = sum_pos + sum_neg
# if there is a solution:
# sum_positive - sum_negative = magic_namber
# Therefore, the task can be formulated as looking for a subset of seq such that:
# sum_neg = (sum(seq) - magic_number)/2

check_list = seq[1:]  # The first element of seq cannot be negative
tmp = sum(seq) - magic_number
if tmp % 2 != 0 or tmp < 0:
return False

# pseudo-polynomial algorithm for the partition problem
target = tmp // 2
n = len(check_list)
table = np.zeros((target + 1, n + 1), dtype=bool)
table[0, :] = True
for i in range(1, target + 1):  # O(target)
for j in range(1, n + 1):  # O(N)
if i - check_list[j - 1] >= 0:
table[i, j] = table[i, j - 1] or table[i - check_list[j - 1], j - 1]
else:
table[i, j] = table[i, j - 1]

return table[target, n]``````

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

Java code ?

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

I would suggest doing something like this...
1 send the ans, arr, index and current ans recursively
2 the good thing about using recursion is it reduces complexity of the idea
3 using OR '|' operator ensures that the program does not compute
through all combinations since it greedily returns true if it encounters a true
midway without processing the rest of the code

``````private static boolean isMgic(int ans, int[] arr)
{
return isMgic(ans, arr, 0, 0);
}

private static boolean isMgic(int ans, int[] arr, int index, int tmp)
{
if (arr.length > index)
return (isMgic(ans, arr, index + 1, tmp + arr[index])
| isMgic(ans, arr, index + 1, tmp - arr[index]));
if (ans == tmp)
return true;
return false;
}``````

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

Can you please explain me how the OR operator works in this code.

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

I came up with this:

``````def is_magic(seq, magic_number):
# sum(seq) = sum_pos + sum_neg
# if there is a solution:
# sum_positive - sum_negative = magic_namber
# Therefore, the task can be formulated as looking for a subset of seq such that:
# sum_neg = (sum(seq) - magic_number)/2

check_list = seq[1:]  # The first element of seq cannot be negative
tmp = sum(seq) - magic_number
if tmp % 2 != 0 or tmp < 0:
return False

# pseudo-polynomial algorithm see wikipedia Partition_problem
target = tmp // 2
n = len(check_list)
table = np.zeros((target + 1, n + 1), dtype=bool)
table[0, :] = True
for i in range(1, target + 1):  # O(target)
for j in range(n):  # O(N)
if i - check_list[j] >= 0:
table[i, j + 1] = table[i, j] or table[i - check_list[j], j]
else:
table[i, j + 1] = table[i, j]

return table[target, n]``````

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

I came up with this using Python

``````def is_magic(seq, magic_number):
# sum(seq) = sum_pos + sum_neg
# if there is a solution:
# sum_positive - sum_negative = magic_namber
# Therefore, the task can be formulated as looking for a subset of seq such that:
# sum_neg = (sum(seq) - magic_number)/2

check_list = seq[1:]  # The first element of seq cannot be negative
tmp = sum(seq) - magic_number
if tmp % 2 != 0 or tmp < 0:
return False

# pseudo-polynomial algorithm for Partition_problem
target = tmp // 2
n = len(check_list)
table = np.zeros((target + 1, n + 1), dtype=bool)
table[0, :] = True
for i in range(1, target + 1):  # O(target)
for j in range(n):  # O(N)
if i - check_list[j] >= 0:
table[i, j + 1] = table[i, j] or table[i - check_list[j], j]
else:
table[i, j + 1] = table[i, j]

return table[target, n]``````

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

``````/** Given a magic number x and a list of numbers, attempt to use addition and subtraction
* to determine if the magic number can be found from the list
**/
function magicNumberSolver(x, list, total: number = 0, process: string = "") {
if (list.length === 0 && total === x) {
console.log("TRUE for x: ", x, " using: ", process);
return true;
} else if (list.length !== 0) {
let num = list.shift();
magicNumberSolver(x, list, total ? total + num : num, process.length? process + "+" + num : num.toString());
magicNumberSolver(x, list, total ? total - num : num, process.length? process + "-" + num  : num.toString());
} else {
// console.log("There is no way to get " + x + " from " + process);
return false;
}
}

//test magicNumberSovler()
magicNumberSolver(10, [1,2]);
magicNumberSolver(2, [1,2,3,4]);
magicNumberSolver(0, []);
magicNumberSolver(1, []);
magicNumberSolver(1, [1]);
magicNumberSolver(0, [1]);``````

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

``````/** Given a magic number x and a list of numbers, attempt to use addition and subtraction
* to determine if the magic number can be found from the list
**/
function magicNumberSolver(x, list, total: number = 0, process: string = "") {
if (list.length === 0 && total === x) {
console.log("TRUE for x: ", x, " using: ", process);
return true;
} else if (list.length !== 0) {
let num = list.shift();
magicNumberSolver(x, list, total ? total + num : num, process.length? process + "+" + num : num.toString());
magicNumberSolver(x, list, total ? total - num : num, process.length? process + "-" + num  : num.toString());
} else {
// console.log("There is no way to get " + x + " from " + process);
return false;
}
}

//test magicNumberSovler()
magicNumberSolver(10, [1,2]);
magicNumberSolver(2, [1,2,3,4]);
magicNumberSolver(0, []);
magicNumberSolver(1, []);
magicNumberSolver(1, [1]);
magicNumberSolver(0, [1]);``````

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

Similar to @Flint solution but a bit shorter, O(len(seq) * (sum(seq) - magic_number)):

``````def is_magic(seq, magic_number):
if not seq:
return False
magic_number -= seq[0] # The first element must be positive
seq = seq[1:]
target = sum(seq) - magic_number
if (target % 2) or (target < 0):
return False
target /= 2
return reduce(lambda w, i: [w[m] or (w[m-seq[i]] if seq[i]<= m else False) for m in xrange(target+1)],
xrange(1, len(seq)),
[True]+[False if i+1 != seq[0] else True for i in xrange(target)])[-1]``````

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

``````boolean isMagicNumberPossible(int[] arr, int magicNumber) {
boolean flag = true;

for(int i=0; i<arr.length; i++) {
int requiredVal = magicNumber - arr[i];
for(int j=1; j < arr.length; j++) {
if(requiredVal == arr[j]) return true;
else if(requiredVal < arr[j]) requiredVal = requiredVal + arr[j];
else requiredVal = requiredVal - arr[j];
}
flag = false;
}

return flag;``````

}

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

``````boolean isMagicNumberPossible(int[] arr, int magicNumber) {
boolean flag = true;

for(int i=0; i<arr.length; i++) {
int requiredVal = magicNumber - arr[i];
for(int j=1; j < arr.length; j++) {
if(requiredVal == arr[j]) return true;
else if(requiredVal < arr[j]) requiredVal = requiredVal + arr[j];
else requiredVal = requiredVal - arr[j];
}
flag = false;
}

return flag;
}``````

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

Here is java code:

``````boolean isMagicNumberPossible(int[] arr, int magicNumber) {
boolean flag = true;

for(int i=0; i<arr.length; i++) {
int requiredVal = magicNumber - arr[i];
for(int j=1; j < arr.length; j++) {
if(requiredVal == arr[j]) return true;
else if(requiredVal < arr[j]) requiredVal = requiredVal + arr[j];
else requiredVal = requiredVal - arr[j];
}
flag = false;
}

return flag;``````

}

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

``````bool isMagic( IEnumerable<int> ints, int goal ) {

if( !ints.Any() )
return goal == 0;

var first = ints.First();

return isMagic( ints.Skip(1), goal + first)
|| isMagic( ints.Skip(1), goal - first );
}``````

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

Here is one I wrote that you can run in your javascript console and mess with locally (it doesn't return a boolean but thats trivial):

``````function genCombinations(arr, sum) {
let memo = {};
if (!arr || !arr.length) {
return 0;
}

// can't do inner loop over memo if its empty, so initialize it with first value from array
const first = arr[0];
memo['+' + first] = first;
memo['-' + first] = 0 - first;

for (n of arr.slice(1)) {
let tempMemo = {};
for (key in memo) {
tempMemo[(key || '') + '+' + n] = memo[key] + n;
tempMemo[(key || '') + '-' + n] = memo[key] - n;
}
memo = tempMemo;
}

// delete all keys that don't equal the sum
for (k in memo) {
if (memo[k] !== sum) {
console.log('  deleting:', k, memo[k]);
delete memo[k];
} else {
console.log('**MATCH:', k, memo[k]);
}
}
}

// Examples:
genCombinations([1, 2, 3, 4, 5], 10)
genCombinations([1, 1, 1, 1, 1], 3)``````

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

A modified version of pseudo-polynomial algorithm for the partition problem with a one dimension array to save space:

``````def table(arr, k):
p_arr = []
# Just safe guard to ensure all numbers are positive
for i in arr:
p_arr.append(abs(i))
arr_sum = sum(p_arr)
# we can't split one number so can't support fractions
if (arr_sum - k) % 2 != 0: return False
first = ((arr_sum - k) / 2)
second = arr_sum - first
if first < 0: return False
if second < 0 : return False
# save operations by processing smaller number
if second < first:
first, second = second, first
# any found sum should end up having with True value
table = [False] * (first + 1)
table[0] = True

for num in p_arr:
for i in range(first+1):
if table[i] and i + num <= first:
table[i+num] = True
return table[first]``````

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

Here is a solution. It involves to prove that this is equivalent to say:
Find a sub array in a list of numbers where the sum of this subset equals to (S + M) / 2. Where S is the sum of all numbers and M is the magic number we are looking for. For example finding the magic number 2 by subtracting or adding numbers from [1, 2, 3, 4] is the same as finding 6 = [(S + M) / 2] by adding 1 or more numbers from the list.

You can the mathematical proof and the java code in GitHub mloukili/math

Good luck

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

Check GitHub mloukili/math for mathematical proof and java code.

The trick is to prove that this is equivalent to:
Find a sub array in a list of numbers where the sum of this subset equals to (S + M) / 2. Where S is the sum of all numbers and M is the magic number we are looking for. For example finding the magic number 2 by subtracting or adding numbers from [1, 2, 3, 4] is the same as finding 6 = [(S + M) / 2] by adding 1 or more numbers from the list.

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

I think I have a "clever" solution by first sorting the list in descending order then that then completes in linear order - however, there's the sorting that needs to take place first as a draw back:

``````def get_magic_number(n, list_of_nums):

#sort in place in descending order
list_of_nums.sort(reverse=True)

total = 0

for num in list_of_nums:
if abs(total + num) > n:
total = abs(total - num)
elif abs(total - num) <= n:
total = abs(total + num)
if total == n:
return True

return False``````

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_sum, unordered_map<uint64_t, bool>& memo, int idx = 0)
{
if (idx < 0 ||
idx > a.size())
{
return false;
}
if (idx == a.size())
{
return target_sum == 0;
}

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

bool res = CanBeComposed(a, target_sum - a[idx], memo, idx + 1);
if (!res &&
idx != 0)
{
res = CanBeComposed(a, target_sum + a[idx], memo, idx + 1);
}

memo[memo_key] = res;
return res;
}

int main()
{
unordered_map<uint64_t, bool> memo;
cout << CanBeComposed({1, 2, 3, 4}, 2, memo) << "\n";
return 0;
}``````

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.