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

- puneet.sohi March 28, 2014 | Flag Reply
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)

- puneet.sohi March 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[0] = A[0];
	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[7] = {5, 7, 10, 10, -30, 17, 19};
	int size = sizeof(a)/sizeof(int);
	
	isSplittable(a, size);
	

	
	return 0;
}

- puneet.sohi March 28, 2014 | Flag
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;
        }

- Anonymous March 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- puneet.sohi March 28, 2014 | Flag
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;
}

- Nix March 28, 2014 | Flag Reply
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;
}

- Nix March 28, 2014 | Flag Reply
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;
}

- Anonymous March 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is NP hard problem.

- Viral March 29, 2014 | Flag Reply
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;

- Ricky April 01, 2014 | Flag Reply
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;
}

- cdo2 April 03, 2014 | Flag Reply
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;
}

- Anonymous April 03, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More