Google Interview Question Software Developers
Country: United States
Interview Type: In-Person
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]
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;
}
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]
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]
/** 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]);
/** 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]);
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]
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;
}
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;
}
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;
}
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)
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]
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
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.
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
#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;
}
leetcode 494.
- tyler_ua July 11, 2018take a look on the 282 - similar