Amazon Interview Question
SDE1sTeam: Machine learning
Country: India
Interview Type: Phone Interview
private static int FindIndexWhereLeftSumEqualRightSum(int[] arr)
{
if (arr == null || arr.Length == 0)
return -1;
int i = 1;
int j = arr.Length - 2;
int leftSum = arr[0];
int rightSum = arr[arr.Length-1];
while (i < j)
{
if (leftSum < rightSum)
{
leftSum += arr[i];
i++;
}
else
{
rightSum += arr[j];
j--;
}
}
if (leftSum == rightSum)
{
return leftSum;
}
return -1;
}
Java
Complexity: O(n)
public class SumOfLeftEqualsSumofRight {
public static void main(String[] args) {
int arr[] = {-1, 100, 1, 98, 1};
SumOfLeftEqualsSumofRight sumOfLeftEqualsSumofRight = new SumOfLeftEqualsSumofRight();
int totalSum = getSum(arr);
System.out.println(sumOfLeftEqualsSumofRight.getElementWithEqualSum(arr,totalSum));
}
public static int getSum (int []arr){
int sum=0;
for(int curr:arr){
sum=sum+curr;
}
return sum;
}
public int getElementWithEqualSum(int arr[], int sum){
if (arr == null || arr.length == 0)
return -1;
int leftTotal = 0;//arr[0];
int rightTotal = sum-arr[0];
for(int i=1;i<arr.length;i++){
leftTotal = leftTotal + arr[i-1];
rightTotal = rightTotal - arr[i];
if(leftTotal==rightTotal){
return i;
}
}
return -1;
}
}
it is a phone interview question and should not complicate by aping solutions of similar type of problem
int findIndexHalfSum(int a[], int sz)
{
int lsum = 0, rsum = 0;
for (int i = 1; i++ ; i<sz) rsum +=a[i];
for (int i = 1; i++ ; i<=sz-2)
{
lsum +=a[i-1]; rsum -= a[i];
if (lsum == rsum) return i;
}
return -1;
}
I don't understand the question. If it's simply the sum of the left == sum of the right, then no split would make your example of [-1, 100, 1, 98, 1] work. That question would actually be fairly difficult to do and would require multiple passes.
- Josh January 23, 2015If the question is at what point does some left slice and some right slice have the same sum, then simply have a left sum pointer and a right sum pointer.