## Apple Interview Question

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

``````#include <iostream>
using namespace std;

bool splitarrayex(int * array, int start, int sum)
{
if (sum == 0) {return true;}

if (array[start] == sum){return true;}
if (array[start] > sum ){
start++;
return splitarrayex(array, start, sum);}
else{
sum = sum - array[start];
start++;
return splitarrayex(array, start, sum); }
}

int main()
{
int array [] = {1, 2, 5, 6};

int sum = 0;
for (int i = 0 ; i < 4 ;i ++)
{
sum += array[i];
}

int half = sum/2;

if (sum == half * 2)
{
if (splitarrayex(array, 0 , sum/2)){printf("\r\n TRUE \r\n");}
else{printf("\r\n FALSE \r\n");}
}
else
{
printf("\r\n FALSE \r\n");
}

return 0;
}``````

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

This is all well and good, but you still need to check for an end condition, that is if the index "start" exceeds the array's length. Do this after the first condition check in the helper method.

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

I think this greedy algorithm does not.. try [5,2,3,4,2]

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

Ha, for some reason this question is popular among interviewers. I've seen variations of it being asked at Amazon - it included a task of splitting array into parts of similar average.

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

You know the desired sum (half of the sum of all elements). Then it is a knapsack problem.

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

<pre lang="" line="1" title="CodeMonkey48804" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public boolean checkSum(int[] arr, int st, int end, int sum){
if(sum==0)return true;
for(int i=st;i<end;i++){
int tmp = sum - arr[i];
if(tmp <0)continue;
if(checkSum(arr, i+1, end, tmp))return true;
}
return false;
}

public boolean splitArray(int[] arr){
int sum = 0;
for(int i=0;i<arr.length();i++)sum+=arr[i];
return checkSum(arr, 0, arr.length(), sum/2);
}

public static void main (String[] args) throws java.lang.Exception
{
int[] arr = {2,3,5,6,2};
if(splitArray(arr))System.out.println("true");
else System.out.println("false");
return;
}
}

</pre><pre title="CodeMonkey48804" input="yes">
</pre>

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

Funny, somebody is interested in posting wrong answers...

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

I think this will work, hope to see some better solution

package ArraysAndStrings;

import java.util.Arrays;

public class ArraySepValue {

public boolean canDivide(int[] input) {
if(input.length < 2)
return false;
double sum = 0;
for(int x : input)
sum += x;
Arrays.sort(input);
if(sum % 2 == 1)
return false;
return canDivHandler(input, 0, sum / 2);
}

public boolean canDivHandler(int[] input, int start, double sum) {
if(start == input.length || input[start] > sum)
return false;
int cur = input[start];
if(cur == sum)
return true;
start += 1;
return canDivHandler(input, start, sum) || canDivHandler(input, start, sum - cur);
}

public static void main(String[] args) {
int[] array = new int[]{3,3,3,3,3,7,1};
ArraySepValue a = new ArraySepValue();
System.out.println(a.canDivide(array));
}

}

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

//using dynamic programming

bool splitArray(int[] array){
int sum = sum(array);
int i = count(array);
return Q(array, i, sum/2);
}

Q(int[] array, int i, int sum){
if(i == 1){
return array[i]==sum?true:false;
}
if((array[i]==sum)
|| Q(array, i-1, sum-array[i]) //have a subset with array[i]
|| Q(array.removeAt(i), i-1, sum)) //have a subset without array[i]
return true;
else
return false;
}

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

def splitArray(arr, n=0):
if (sumArray(arr[:n]) == sumArray(arr[n:])):
return True
if (n == len(arr) - 1):
return False
return splitArray(arr, n+1)

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

Here is my solution in C

``````#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int sum(int array[], int start, int end){

int sum = 0, i;
for(i = start; i < end; i++){
sum += array[i];
}
return sum;
}

int splitArray(int array[], int start, int end, int ind){

if( ind == end){
return 0;
} else {
int left = sum(array, start, ind);
int right = sum(array, ind+1, end);
return (left == right) || splitArray(array, start, end, ind+1);

}
}

int main(int argc, char* argv[]){

int array[] = { 7,3,4,0,1,2};

int res = splitArray(array, 0, 5, 0);

if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");

return 0;
}``````

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

Here is my solution in C

``````#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int sum(int array[], int start, int end){

int sum = 0, i;
for(i = start; i < end; i++){
sum += array[i];
}
return sum;
}

int splitArray(int array[], int start, int end, int ind){

if( ind == end){
return 0;
} else {
int left = sum(array, start, ind);
int right = sum(array, ind+1, end);
return (left == right) || splitArray(array, start, end, ind+1);

}
}

int main(int argc, char* argv[]){

int array[] = { 7,3,4,0,1,2};

int res = splitArray(array, 0, 5, 0);

if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");

return 0;
}``````

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

``````#include "stdio.h"
2
3 int splitArray(int list[], int index)
4 {
5         int i, sum1, sum2;
6         /* left half */
7         sum1 = 0;
8         for(i=0;i<index;i++)
9                 sum1 = sum1 + list[i];
10         /* right half */
11         sum2 = 0;
12         for(i=index;i<6;i++)
13                 sum2 = sum2 + list[i];
14
15         if(sum1 == sum2)
16                 return 1;
17         else
18                 return 0;
19 }
20
21
22 int main(void)
23 {
24         int i, list[] = { 7,0, 2, 3,4,2};
25
26         for(i=0;i<6;i++)
27                 if(splitArray(list, i)) {
28                         printf(" TRUE \n");
29                         break;
30                 }
31 }
~``````

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

#if 1

#include <stdio.h>
#include <stdlib.h>

int sum(int array[], int start, int end)
{
int sum = 0, i;
for(i = start; i < end; i++)
{
sum += array[i];
}
return sum;
}

int splitArray(int array[], int start, int end, int ind)
{
if( ind == end)
{
return 0;
}
else
{
int left = sum(array, start, end);
printf("\n total sum of all elements in array \n");
//int end1 = (end)/2;
ind = ind+1;
int left1 = sum(array,start,ind);
int right = sum(array, ind, end);
if(left1 == right)
return 1;
else
splitArray(array, start, end, ind);
}
}

int main(int argc, char* argv[])
{

int array1[] = {5,2,2,4,5};
int len = sizeof(array1)/ sizeof(array1[0]);

int res = splitArray(array1, 0, len, 0);
if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");
return 0;

}

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

``````long sum(array a)
{
result = 0;
for all element x in a
result += x;
return result;
}

BOOL recursiveSplit(index, previousSum, targetSum, array a)
{
currentSum = 0;
if(index < 0) return no;
if(a[index] == targetSum || (a[index] + previousSum) == targetSum) return yes;
if(a[index] + previousSum > targetSum)
currentSum = previousSum;
else
currentSum = previousSum + a[index];

return recursiveSplit(index - 1, currentSum, targetSum, a);
}

main()
{
array a = [1,1,1,1,4,2];
index = a.length - 1;
targetSum =  sum(a)/2;
if(recursiveSplit(index, 0, targetSum, a))
log("YES");
else
log("NO");
}``````

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

only loop is for initial sum of the array...

``````#include <iostream>
using namespace std;

bool test(int x[], int i, int sum, int cursum, int n, bool take)
{
bool done=false;
if (take)
cursum += x[i];
i++;

if (cursum<sum && i<n)
done = test(x,i,sum,cursum,n,true) || test(x,i,sum,cursum,n,false);
else if(cursum==sum)
done = true;

return done;
}

bool splitArray(int x[], int n)
{
int sum=0;
for (int i=0; i<n; i++)
sum+=x[i];

int halfsum = sum/2;
if (halfsum*2 != sum)
return false; //sum needs to be even

return test(x,0,sum/2,0,n,true) || test(x,0,sum/2,0,n,false);
}

int main (int argc, char * const argv[]) {

int x[]={2,3,20,5,10};
int len = sizeof(x)/ sizeof(x[0]);

cout << (splitArray(x,len)?"true":"false");

cout << "\n";
return 0;
}``````

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

Here is a solution in C (it actually computes the sum as it checks if the partition is possible).

We need to rely on the array being sorted beforehand for this.

``````#include <stdlib.h>
#include <stdio.h>

int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}

int array_partition_possible(int *array, int count) { //array needs to be already sorted
int sum_a = 0;
int sum_b = 0;

for (int i = count-1; i >= 0; i--) {
if (sum_a <= sum_b) {
sum_a += array[i];
} else {
sum_b += array[i];
}
}

printf("%d, %d\n",sum_a, sum_b );

return (sum_a == sum_b);
}

int main(int argc, char *argv[]) {
int count = argc - 1;

// Create the input array based on the arguments of the main function.
int *input = malloc(count);

for (int i = 0; i < count; ++i) {
input[i] = atoi(argv[i+1]);
}

// Sort the input array
qsort(input, count, sizeof(*input), compare_function);

// Find if the partition is possible
if (array_partition_possible(input, count))
{
printf("true\n");
} else {
printf("false\n");
}

return 0;
}``````

This solution can also be found here: h**ps://gist.github.com/nilsou/6969993

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

``````#include <iostream>
using namespace std;

bool isPartition(int* arr, int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}

if (sum & 1) {
return false;
}

sum = sum / 2;
bool** T = new bool*[n + 1];
for (int i = 0; i < n + 1; i++) {
T[i] = new bool[sum + 1];
}

// Initializing the first row as false
for (int j = 0; j < sum + 1; j++) {
T[0][j] = false;
}

// Initializing the first column as true
for (int i = 0; i < n + 1; i++) {
T[i][0] = true;
}

// Computing the T matrix
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
if (j < arr[i - 1]) {
T[i][j] = T[i - 1][j];
}
else {
T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]];
}
}
}
return T[n][sum];
}

int main() {
int arr[] = { 3, 1, 1, 2, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << isPartition(arr, n) << endl;
}``````

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

``````#include <iostream>

using namespace std;

bool splitarrayex(int *array, int numele, int sum1, int sum2)
{
if (sum1 == sum2 && numele == 0)
return true;

if (numele == 0)
return false;

return splitarrayex(array+1, numele-1, sum1+(*array), sum2) || splitarrayex(array+1, numele-1, sum1, sum2+(*array));
}

int main()
{
//        int array [] = {1, 2, 5, 6};
int array [] = {5, 2, 3, 4, 2};
//        int array [] = {5, 2, 3, 4, 30};

if (splitarrayex(array, 5, 0, 0))
cout << "TRUE" << endl;
else
cout << "FALSE" << endl;

return 0;
}``````

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

``````#include <iostream>

using namespace std;

bool splitarrayex(int *array, int numele, int sum1, int sum2)
{
if (sum1 == sum2 && numele == 0)
return true;

if (numele == 0)
return false;

return splitarrayex(array+1, numele-1, sum1+(*array), sum2) || splitarrayex(array+1, numele-1, sum1, sum2+(*array));
}

int main()
{
//        int array [] = {1, 2, 5, 6};
int array [] = {5, 2, 3, 4, 2};
//        int array [] = {5, 2, 3, 4, 30};

if (splitarrayex(array, 5, 0, 0))
cout << "TRUE" << endl;
else
cout << "FALSE" << endl;

return 0;
}``````

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

partitioning question...can be done using dynamic programming

let P(i,b) be true if there is a subset of array from a1 to ai such that its sum is b

P(i,b) = max (P(i-1,b), P(i-1, b-a[i]))

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

Could you please explain more here?

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.