Amazon Interview Question Software Engineers
Country: United States
public class FindEqualSumSubset {
public static void main(String[] args) {
ArrayList<Integer> input = new ArrayList<Integer>();
input.add(5);
input.add(5);
input.add(8);
input.add(2);
input.add(1);
//input.add(6);
//input.add(7);
System.out.println(doLogic(input)? "Yes":"No");
}
public static int getSum(ArrayList<Integer> inputList){
int sum = 0;
for(Integer temp: inputList)
sum += temp;
return sum;
}
public static boolean checkForEqualSumSubsets(ArrayList<Integer> superSet){
System.out.println("SuperSet : " + superSet);
if(superSet.size() %2 == 1)
return false; // superset contains odd number of elements
int sum = getSum(superSet);
if(sum %2 == 1)
return false; // sum is not even - so subsets cant have equal sum of integers
int subsetSize = superSet.size()/2;
int fixedStart = 0, fixedEnd = 0, varStart = 1;
sum = sum/2;
while( fixedStart < superSet.size()-subsetSize){
ArrayList<Integer> subset = createSubList(fixedStart, fixedEnd, varStart, subsetSize, superSet);
if(subset.size() == subsetSize && (sum == getSum(subset))){
return true;
}
varStart++;
if(varStart >= superSet.size()){
if(fixedEnd >= superSet.size()){
fixedStart++;
fixedEnd = fixedStart;
} else {
fixedEnd++;
varStart = fixedEnd+1;
}
}
}
return false;
}
public static ArrayList<Integer> createSubList(int fixedStart, int fixedEnd,
int varStart, int subListSize, ArrayList<Integer> origList){
System.out.println("FixedStart : " + fixedStart + ", FixedEnd : " + fixedEnd +
", VarStart : " + varStart);
ArrayList<Integer> result = new ArrayList<Integer>();
if (origList != null){
for(int i = fixedStart; i <= fixedEnd && i < origList.size(); i++){
result.add(origList.get(i));
}
for(int i = varStart; result.size() < subListSize && i < origList.size(); i++){
result.add(origList.get(i));
}
}
return result;
}
public static boolean doLogic(ArrayList<Integer> input){
if(input.size() %2 == 0)
return false; // got an even length array
for(int i = 0; i < input.size(); i++){
ArrayList<Integer> temp = new ArrayList<Integer>(input);
temp.remove(i);
if(checkForEqualSumSubsets(temp))
return true;
}
return false;
}
}
Say you pick out an arbitrary number k from the list and split the remaining numbers into 2 sets A and B of equal length with the same sum X. Now imagine that you pick out a number a from set A instead of k. Now assume that a != k. Since a != k the only way the two sets can sum to the same amount with the same number of elements is to move an element b from B to A and move k to B. Doing the math, we find X - a + b = X - b + k, or b = (a + k) / 2. b is essentially the midpoint of a and k. Now suppose instead of a we picked b to substitute. Since b cannot be equal to k (if it was, then a would be equal to k, and we already assumed it wasn't) we must choose an element c from A to replace b. Do the math again and you find that an element c must be in A and c is the mid point of b and k. Rinse and repeat and you find a contradiction where eventually there is no integer remaining between the last midpoint and k. So the assumption that k != a must be false. That means that k = a so all elements of the set are the same number (by symmetry). So to solve this question just see if all elements are the set are the same number.
All the numbers in the list must be the same number. You can prove this by contradiction. Say you have removed an arbitrary element k and partitioned the remaining set into subsets A and B of the same length and sum x. Now suppose you want to remove an arbitrary element a from A. Assume k != a. Since k != a, the only way to balance A and B is to move an element b from B to A and replace b with k. So x - a + b = x - b + k, or b = (a + k) / 2, aka the midpoint between a and k. Now suppose you want to remove b instead of a, and use a number c from A to replace b and k to replace c. Do the math again and you find that c is the midpoint between b and k. Keep going and eventually you find that it's impossible b/c you finally get to a point where there is no integer in between the last midpoint and k. So our assumption k != a must be wrong and k must equal a. Since a was an arbitrary element of A that means that all elements of A and B must be = k.
Assume that by removing an element A_k from [ A_1, A_2,......A_n] it is possible to have two sets S_1 and S_2 such that len(S_1) = len(S_2) && ( Sum(S_1) - Sum(S_2)) == 0.Now lets assume that we next remove A_r [ r != k ]. Then (Sum(S_1) - Sum(S_2)) + (A_k - A_r) should also be equal to zero which is only possible if (A_k - A_r) == 0. Since k is arbitrary and r can be any other elements, so all the elements of the array must be equal for it to hold for removing any elements.
So the code follows as
bool check(vector<int>& v) {
for(int i = 0; i < v.size() - 1; i++){
if(v[i] != v[i + 1]) return false;
}
return true;
}
int sum1=0,sum2=0;
Set<Integer> set=new HashSet<Integer>();
int p=arr.length;
boolean result=false;
for(int i=0;i<=p/2;i++)
{
sum1=sum1+arr[i];
}
for(int i=(p/2)+1;i<arr.length;i++)
{
sum2=sum2+arr[i];
set.add(arr[i]);
}
result=set.contains(sum2-sum1);
if(!result)
{
int sum1=0,sum2=0;
set.clear();
for(int i=(p-1);i>(p/2);i--)
{
sum1=sum1+arr[i];
}
for(int i=(p/2);i>=0;i--)
{
sum2=sum2+arr[i];
set.add(arr[i]);
}
return set.contains(sum2-sum1);
}
else
{
return true;
}
from random import randint
def go(input_array) :
if len(input_array) <= 1 or len(input_array)%2== 0 :
print('Invalid input')
st = int((len(input_array)-1)/2)
i = 0
while(i < len(input_array)) :
temporary = input_array.copy()
temporary.pop(i) # remove element with index i
if ( sum(temporary[:st]) - sum( temporary[st :] ) == 0) : #divide array in 2 halves and
# check if sum is the same
return {True :[temporary [ : st], temporary[st : ]]} # in case return
i += 1
return False
# returns an array of length (2*arrays_length + 1)
# such that, once a particular element is removed from
# the array, both the sum of the first arrays_length elements
# and the sum of the last arrays_length equal input_sum
def create_test(input_sum, arrays_length) :
right = input_sum
left = input_sum
array = [0]*(2*arrays_length + 1)
for i in range(0, arrays_length-1) :
array[i] = randint(0, right)
right = right - array[i]
array[len(array)-1-i] = randint(0,left)
left = left - array[len(array)-1-i]
array[arrays_length-1] = right
array[arrays_length+1] =left
array[arrays_length] = randint(0,10000)
pos = randint(0,len(array)-1)
array[pos], array[arrays_length]= array[arrays_length] , array[pos]
return array
#test
for i in range(0,10) :
test = create_test(100, 3+i)
print('step %s and array= %s' % (i, test))
print(go(test))
Assuming you mean 'any number of elements could be removed excluding the first and last elements'
boolean canBeSplitEqually(int[] array)
{
int start = 0;
int end = array.length() - 1;
int sumLeft = 0;
int sumRight = 0;
while (start < end)
{
sumLeft += array[start];
sumRight += array[end];
if (sumLeft == sumRight) // note lengths will automatically be equal
{
return true;
}
start++;
end--;
}
return false;
}
example 2 is incorrect,{1,2,2} remove element 1 and you shall get array {2} and {2} of equal sum.
Algorithm based on partition set problem, checks for each distinct element if total sum - array[i] % 2, if so then check to see if there's a subset in array without element array[i] which sums to (sum - array[i])/2.
Code in Java:
public class PartitionSet {
public static void main(String[] args) {
int[] a = {1,1,1,1,1};
isDivisible(a);
int[] b = {1,2,2};
isDivisible(b);
}
public static boolean isDivisible(int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
boolean foundAny = false;
Map<Integer, Boolean> removableElements = new HashMap<>();
for (int i = 0; i < a.length; i++) {
if (!removableElements.containsKey(a[i])) {
if ((sum - a[i]) % 2 == 0) {
foundAny = isSubsetSum(removeElement(a,i), (sum - a[i])/2);
removableElements.put(a[i], foundAny);
} else {
removableElements.put(a[i], Boolean.FALSE);
}
}
}
if (foundAny) {
StringBuilder sb = new StringBuilder();
for(Map.Entry<Integer, Boolean> e : removableElements.entrySet()) {
if (e.getValue().equals(Boolean.TRUE)) {
sb.append(e.getKey() + " ");
}
}
System.out.println("Yes. removing elements: " + sb.toString());
} else {
System.out.println("No");
}
return foundAny;
}
// returns a new array without element at index i of a
private static int[] removeElement(int[] a, int i) {
int[] b = new int[a.length-1];
int k = 0;
for (int j = 0; j < a.length; j++) {
if (j != i) {
b[k++] = a[j];
}
}
return b;
}
public static boolean isSubsetSum(int[] a, int sum) {
boolean dp[][] = new boolean[sum+1][a.length+1];
// array with sum 0 and any element true
for (int i = 0; i < dp.length; i++) {
dp[0][i] = true;
}
// array with sum non-zero and no element is false
for (int i = 0; i < dp.length; i++) {
dp[i][0] = false;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= a.length; j++) {
dp[i][j] = dp[i-1][j-1];
if (i >= a[j-1]) {
dp[i][j] = dp[i][j] || dp[i-a[j-1]][j-1];
}
}
}
return dp[sum][a.length];
}
}
Sort the list a[n]. Exclude each element starting from first element and calculate 2 sums, first one is with odd indexes and second one is with even indexes, check if both are equal.
e.g:
if a[0] is excluded.. first set: {a[1], a[3], a[5],...,a[n-1] } and second set: {a[2], a[4], a[6],....,a[n-2] }
Isn't it possible to remove 1 and split [2, 2] into two sets of equal length with the same length (i.e [2] and [2] ) in case of Input [1, 2, 2]? Or do you mean that it should be left and the right of the number removed that should have equal sum and equal length?
- mrsurajpoudel.wordpress.com July 22, 2016