## Interview Question

Country: United States

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

First lets prove that an array can be split at only one point:

E.g
Array = [……….17……….19]
Lets say its split able at 19. To be also split able at 17, the sum of numbers b/w 19 and 17 would have to be -ve(-2 in this case). Which means sum total going from 17 to 19 would be < 17 (=15 in this case). So array would not be split able at 19.

Same can be proven if there is a num > 19 say 23

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

Now, for quickest run time, we’ll use an extra array to hold the sums.(S)
Algo would be:
Going forward, add and store the sum till that idx i into S[i].
Once the end is reached, walk backward, adding the sum of terms from back
and compare with the sum from front (S[i]
If match found, return true, else return false

Run time would be O(n)

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

Code:

``````#include <iostream>
#include <map>
#include <tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std;
using namespace tr1;

bool isSplittable(int *A, int size){

if(size < 2){return false;}

//array to hold sums
int *S = new int[size];
S = A;
int i = 1;
int bkwd_sum = A[size-1]; //to hold sum while walking backwards
int fwd_sum = 0;
//put forward sum into S from 0 to len - 1
while(i<size-1){
S[i] = S[i-1] + A[i];
i++;
}
i--;

//Start walking backwards till a match in sum is found
while(i>0){
fwd_sum = S[i];
if(fwd_sum == bkwd_sum){
cout << "array can be split at idx:" << i << endl;
return true;
}
bkwd_sum = bkwd_sum + A[i];
i--;
}

return false;
}

int main (int argc, char * const argv[]) {
int a = {5, 7, 10, 10, -30, 17, 19};
int size = sizeof(a)/sizeof(int);

isSplittable(a, size);

return 0;
}``````

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

``````public static bool IsSplittable(List<int> arr)
{
if (arr == null || arr.Count() == 0)
return false;

int total = arr.Sum();
if(total%2!=0) return false;

int half = (int)(total/2);

arr.Sort();
int st, end, sum;
st = end = sum = 0;
bool endFwd = true;

while (st < arr.Count() && end < arr.Count)
{
if (endFwd)
{
sum += arr[end];
}
else
{
sum -= arr[st - 1];
}

if (sum == half)
return true;

if (sum > half)
{
st++;
endFwd = false;
}
else
{
end++;
endFwd = true;
}
}

return false;
}``````

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

I don't think we're allowed to modify the array. You're sorting it and in process modifying it.

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

Start by accumulating sum of left side elements in "sumLeft". Collect more elements only if sumLeft is smaller than sum of elements to the right of idx till idx < size.

``````bool isSplittable(int[] arr)
{
int size = sizeof(arr)/sizeof(int);
if(size < 2) return false;

int i=0;
int sumLeft = 0;
while(1)
{
sumLeft += arr[i];
int tmpSum = sumLeft;
for(int idx=i; idx < size; idx++) {
tmpSum -= arr[idx];
}

if (tmpSum == 0) return true;
if (tmpSum < 0) i++;
else return false;
}
return false;
}``````

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

Improved/corrected a bit:

``````// Return true if arr can be divided into two parts having equal sums; return false otherwise.

#include <iostream>

#define PRINT(_X, _size)	std::cout << std::endl << "ARRAY = {"; for (int i=0; i < _size; ++i) std::cout << " " << _X[i]; std::cout << " }" << std::endl;

int isSplittable(int *arr, int size)
{
//int size = sizeof(arr)/sizeof(int);
if(size < 2) return -1;

int i=0;
int sumLeft = 0;
while(1)
{
sumLeft += arr[i];
int tmpSum = sumLeft;
for(int idx=i+1; idx < size; idx++) { // O(n log(n)) ???
tmpSum -= arr[idx];
}

//std::cout << "i = " << i << ", tmpSum = " << tmpSum << ", sumLeft = " << sumLeft << std::endl;

if (tmpSum == 0) return i;
if (tmpSum < 0) i++;
else return -1;
}
return -1;
}

int main(void)
{
//int arr[] = { 7, 0, 2, 6, 3 }; // Splittable at index 2, elem 2
//int arr[] = { 7, 0, 2, 6, 3, 18 }; // Splittable at index 4, elem 3
//int arr[] = { -7, 0, 2, 6, 3, 11 }; // Not splittable
//int arr[] = { -7, 0, 2, 6, -14, 3 }; // Splittable at index 2, elem 2
int arr[] = { -7, 0, 2, 6, 2, 3 }; // Splittable at index 4, elem 2

const int size = sizeof(arr)/sizeof(int);
PRINT(arr, size);

int at = isSplittable(arr, size);
if (at > 0)
std::cout << "The array is splittable at " << at << " (ie, at element " << arr[at] << ")" << std::endl;
else
std::cout << "The array is NOT splittable" << std::endl;

return 0;
}``````

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

In Java, unless I'm missing something (O(n) time, O(1) memory)

``````boolean isSplittable(int [] arr) {

if ( (arr==null) || (arr.length<=1) ) return false;

int total = 0;
for (int i=0; i<arr.length; i++) total += arr[i];
if (total%2==1) return false;

int half = total/2;
total = 0;
for (int i=0; i<=arr.length; i++) {
total += arr[i];
if (total==half) return true;
}
return false;
}``````

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

This is NP hard problem.

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

It can be done as follows:

``````// Take two int(s) for the sum as leftSum & rightSum.
int start = 0, end = n-1;
int leftSum     = data[start];
int rightSum   = data[end];
while ( start < end )
{
If ( leftSum > rightSum )
{
rightSum += data[--end];
}
else
{
leftSum += data[++start];
}
}

if(leftSum == rightSum)
{
return true;
}
return false;``````

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

public boolean isSplitable(int [] ia)
{
int leftSum = 0;
int rightSum = 0;

if (ia.length < 2) return false;
for (int i=1; i < ia.length; i++)
rightSum += ia[i];

for (int i=0; i<ia.length; i++)
{
leftSum += ia[i];
rightSum -= ia[i];
if (leftSum == rightSum)
return true;
}
return false;
}

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

public boolean isSplitable(int [] ia) { int leftSum = 0; int rightSum = 0; if (ia.length < 2) return false; for (int i=1; i < ia.length; i++) rightSum += ia[i]; for (int i=0; i<ia.length; i++) { leftSum += ia[i]; rightSum -= ia[i]; if (leftSum == rightSum) return true; } return false;
}

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.