## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 6 vote

1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)

``````public static int equilibriumIndex(int[] A) {
int sum = 0;
int i = 0;
for (i = 0; i < A.length; i++)
sum += A[i];

int contSum = 0;
for (i = 0; i < A.length; i++) {
if ( (sum - A[i] - contSum) == contSum) return i;

contSum += A[i];
}

}``````

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

O(n) time, O(1) space

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

answer will be wrong if input is
1,2,-3,4,-6,5,1

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

this is the correct version, this version can achieve O(n) time with O(n) space:

``````1) given an array a
2) from left to right, a[i]+=a[i-1]; which is 3,0,8,14,13,8
3) generated an array b, memcpy(b,a,sizeof(a))
4) from right to left ,b[i-1]+=b[i]; which is 8,5,8,0,-6,-5
5) find the place '8', which is a[i] and b[i](i==2), if a[i-1]==b[i+1] then return 1
6) else return 0``````

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

``````def equilibrium(list):
leftsum = rightsum = 0
left = []
for i in range(0, len(list)):
leftsum += list[i]
left.append(leftsum)
for i in range(0, len(list)):
rightsum += list[-(i+1)]
if left[len(list) - i - 1] == rightsum:
return list[-(i + 1)]``````

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

``````#include<iostream>
using namespace std;
int equilibrium(int * arr, int size){
int sum = 0;
int left_sum = 0;
for (int i = 0; i<size; i++){
sum+=arr[i];
}
for(int i = 0; i<size; i++){
sum -= arr[i];
if(sum == left_sum) return i;
else left_sum+=arr[i];
}
return -1;
}
int main(){
int arr[] = {3,-3,8,6,-1,-5};
int size = 6;
int equil = equilibrium(arr, size);
cout<<equil;
}``````

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

arr[] = 2 -3 4 -2 3 1

sumarray[i] = sum of all elements from index 0 to i

from start index sum_array_start[] = 2 -1 3 1 4 5
from end index sum_array_end[] = 5 3 6 2 4 1

now compare all elements in both sum arrays... at one index location the data is same in both sum_arrays, that index location is the equilibrium point index a[index]...
here 4 is same for both sum arrays and it is at index 4... so a i.e 3 is equilibrium point

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

I suppose the following idea also should work.

``````0.Assuming 1-based index, for n elements, take mid = (n+1)/2.
1.Compute the sum from 1 to mid-1 and call it LSum
2.Compute the sum from mid +1 to n and call it RSum
3. If LSum = RSum return mid
4. if LSum < RSum
4a. whlle (LSum < RSum) {
if (mid ==n) return -1;
LSum += a[mid]
RSum -= a[mid+1]
mid = mid+1;
if (LSum == RSum)
return mid;
else if if (LSum > RSum)
return -1;
}
5. if LSum > RSum
4a. whlle (LSum > RSum) {
if (mid == 1) return -1;
LSum -= a[mid-1]
RSum += a[mid]
mid = mid-1;
if (LSum == RSum)
return mid;
else if (LSum < RSum)
return -1;
}``````

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

C++ implementation time complexity o(n) and space o(1)

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

int findPoint(int arr[],int size)  {
int leftSum=arr;
int rightSum=arr[size-1];
int leftIndex=0;
int rightIndex=size-1;
while(true )    {
if(leftSum>rightSum)    {
rightSum=rightSum+arr[--rightIndex];
if(leftSum==rightSum)   {
return rightIndex-1;
}
}
else    {
leftSum=leftSum+arr[++leftIndex];
if(leftSum==rightSum)   {
return leftIndex+1;
}
}
}
return leftIndex;
}

int main()  {
int arr[]={1,3,2,5,4,6,7,8};
int point=findPoint(arr,sizeof(arr)/sizeof(arr));
std::cout<<point;
return 0;

}``````

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

good one

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

This is the simple methodical approach, loop through array to get the total sum. iterate back through the array from 1 to length - 1. subtracting each the value at each previous index , doing the comparison, and returning early when we find an equilibrium.

``````public class equilibriumApp
{

public static void main(String args[])
{

int[] eqArray = { 1,2,3,4,3,2,1 };

int equilibrium = findEquilibriumIndex(eqArray);
System.out.println(equilibrium);

}

private static int findEquilibriumIndex(int[] eqArray)
{
int leftSum = 0,rightSum = 0;

for(int i = 0; i < eqArray.length; i++)
{
rightSum += eqArray[i];
}

for(int j = 1; j < eqArray.length; j++)
{
leftSum += eqArray[j-1];
rightSum-= eqArray[j-1];
rightSum-= eqArray[j];

if(leftSum == rightSum)
return j;
rightSum+= eqArray[j];
}

return -1; //no equilibrium

}
}``````

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

The way I solved is:

1. Calculate the sum of elements upto index i from left and store in ltemp[i] for all elements
2. Calculate the sum of elements upto index 0 from right and store in rtemp[i] for all elements
3. Find the index i where ltemp[i] is same as rtemp[i].

Time Complexity: O(n).
Space Complexity O(n) which can be optimized further if needed.

``````int main() {
const int length = 6;
int arr[length] = {3,-3,8,6,-1,-5};
int rtemp[length];
int ltemp[length];

// Find the sum of elements from left to right
int lsum = 0;
for (int i = 0; i < length; i++) {
lsum = lsum + arr[i];
ltemp[i] = lsum;
}
// Here ltemp array will have values 3, 0, 8, 14, 13, 8

// Find the sum of elements from right to left
int rsum = 0;
for (int i = length - 1; i >= 0; i--) {
rsum = rsum + arr[i];
rtemp[i] = rsum;
}
// Here rtemp array will have values 2, 5, 8, 0, -6, -5

// Find the index i where rtemp[i] is same as ltemp[i]
for (int i = 0; i < length; i++) {
if (ltemp[i] == rtemp[i]) {
cout << "Value = " << arr[i] << " and index = " << i << endl;
return 0;
}
}

return -1;
}``````

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

#include <stdio.h>

#define SIZE 15

int main(void)
{
int num[SIZE], i, sum = 0, count = 0, n, *p = num;

printf("Enter number of elements: ");
scanf("%d", &n);

for (i = 0; i < n; i++)
{
scanf("%d", &num[i]);
sum += num[i];
}

if (n % 2 == 0)
{
printf("\nEquilibrium number: 0");
return 0;
}

for (i = 0; i < SIZE; i++)
{
if ((sum - num[i] + count) == count)
{
printf("Equilibrium number: %d\n", num[i]);
break;
}
else
count += num[i];
}

return 0;
}

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

int findequilibrium()
{
int a={-3, 2, 4, -2 ,3};//{-3,4,5,-8,10,-1};
int sum={0};
sum=a;
for(int i=0;i<4;i++)
{
sum[i+1]=sum[i]+a[i+1];
}
for(int j=0;j<5;j++)
{
if(sum-sum[j+1]==sum[j])
return j+1;

}
return -1;
}

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

We can solve it using a modified "two-finger walking" method.

The idea is, we maintain a prefix sum and a suffix sum, with indexes lo and hi, respectively.

If prefix sum < suffix sum, we need to add one more element to prefix sum to try to make them equal.

Similarly, if prefix sum > suffix sum, we need to add one more element to suffix sum to try to make them equal.

Do this until there is only one element left in the array (lo = hi - 1), if the two sums are equal, then we found an equilibrium point (A[lo]); otherwise there is no equilibrium point.

Time: O(n)
Space: O(1)

public int equilibriumIndex(int[] A) {
/* Assume that the length of the array is always an odd number */
int prefixSum = A;
int suffixSum = A[A>length - 1];
int lo = 1;
int hi = A.length - 2;
while(lo < hi - 1) {
if (prefixSum < suffixSum) {
prefixSum += A[lo];
lo++;
}
else if (prefixSum > suffixSum) {
suffixSum += A[hi];
hi--;
}
else {
prefixSum += A[lo];
suffixSum += A[hi];
lo++;
hi++;
}
}
if (prefixSum != suffixSum)
no such equilibrium point
else
return A[lo];
}

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

@vgeek I had the same idea, but we need to traverse the array again to make sure the element which we get as sum is actually present in the array , if not present we need to say no equilibrium element present in the array

``````int main()
{
int a={2,2,-4,5,-6,6,10,-10};
int x,y;
for(int i=0;i<8;i++)
{
if(i==0)
x=a[i]+a[i+1];
else
{
y=x+a[i+1];
x=y;
}
}
int k=1;
for(int j=0;j<8;j++)
{
if(a[j]==x)
{
k=0;
}
}
if(k==0)
std::cout<<"\n Equilibrium is:"<<x;
else
std::cout<<"\nNo equilibrium number found:";
return 0;
}``````

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

int equilibriumIndex(int[] A)
{
int sumLeft=0;
int sumRight=0;
for(int i=0;i<length;i++)//length is length of array
{
sumLeft=sumLeft+a[i];
sumRight=sumRight+a[(length-1)-i];
if(sumLeft==sumRight && (length-1-i)==2)
return i+1;
}
return -1;
}

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

I think it can be done in a straight way:
a. Just sum all the elements in the array
b. The number that you will get after the sun that will be the equilbrium number as all others would have cancelled each other.
c. Find the index of that number in the array.

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

this is wrong
counter example -3 2 4 -2 3

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

Yeah you are right got that. Thanks for pointing this out

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.