Goldman Sachs Interview Question Financial Software Developers
let sum = total of all elements of the array.. O(n)
+
start from index 0 and proceed and keep on adding it to sum2 n subtracting ti from sum
when sum == sum2, that is the position..
void equilibrium(int *a,int left,int right)
{
int sum1=0,sum2=0,i=left,j=right-1;
sum1 +=a[i];
sum2 +=a[j];
while(i!=j-2)
{
if(sum1< sum2)
sum1 +=a[++i];
else if(sum2 < sum1)
sum2 +=a[--j];
else
{
sum1 +=a[++i];
sum2 +=a[--j];
}
}
if(sum1==sum2)
printf("equal sum = %d and equilibrium point= %d \n",sum1,a[i+1]);
else
printf("no equilibrium point...\n");
}
runninG time O(N)...
Simple solution. O(n) complexity.
static void Main(string[] args)
{
int[] ar = { 12, 3, 7, 4 };
int eqIndex = findEquilibriumPoint(ar);
Console.Write(eqIndex);
Console.Read();
}
static int findEquilibriumPoint(int[] arr)
{
int eqIndex = -1;
int ls = arr[0];
int rs = arr[arr.Length - 1];
int s=0, e= arr.Length-1;
while (s < e)
{
if (ls < rs)
{
s++;
ls += arr[s];
}
else if (rs < ls)
{
e--;
rs += arr[e];
}
else
{
if (e - s <= 2)
break;
if ((e - s) > 2)
{
e--;
rs += arr[e];
}
}
}
if (ls == rs)
eqIndex = s+1;
return eqIndex;
}
int a[] ={1,3,4,10,18,3,1,6,3,1,4}; // 18 is the point..
int len = a.length;
int j = len-1,i=0;
int temp_sum1=0,temp_sum2=0;
while ( (j-i)>=1 ) {
if(temp_sum1>temp_sum2)
temp_sum2 = temp_sum2 + a[j--];
else
temp_sum1 = temp_sum1 + a[i++];
}
if(temp_sum1 == temp_sum2)
System.out.println("point " + a[i]);
Gor two simple approaches:
1.
Use two indices start & end
uses start_sum = a[start] & end_sum = a[end]
increase start if start_sum < end_sum & update start_sum += a[start]
decrease end if end_sum < start_sum & update end_sum += a[end]
repeat until start_sum == end_sum && start = end-1
O(n)
2. sum all elements complete_sum
start = 0
repeat:
until complete_sum != 0
complete_sum -= 2 * a[start++]
O(n) again but less complex
int main()
{
int a[] ={9,-7,4,5,2,3,0,8};
int n = 8,sum1 = 0,sum2 =0,i,j;
i=0;
j=n-1;
while(i<j)
{
if( sum1 < sum2)
sum1 = sum1 + a[i++];
else
sum2 = sum2 + a[j--];
if( (sum1 == sum2) != 0)
{
if(i == j)
printf("\n equilibrium point is i = %d\ and value is = %d \n", i, a[i]);
else
printf("\n there is no equilibrium point \n");
break;
} // End of If
} // End of while
return 0;
}
pseudo code:
Assuming array a[0...n-1]
i=-1; j=n;
sumLeft=sumRight=0;
while(i!=j)
{
if(sumLeft<sumRight)
{
i++;
sumLeft+=a[i];
}
else if( sumLeft > sumRight)
{
j--;
sumRight += a[j];
}
else
{
if(j-i == 2)
{
print "equilibrium point; " +a[i+1];
return;
}
else
{
i++; j--;
sumleft += a[i];
sumright +=a[j];
}
}
}
print "no equilibrium point"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int main()
{
int i=0;
int j=6;
int a[7]={2,5,6,4,8,7,1};
int s,b;
s=a[0];
b=a[6];
for(i=0;i<j;)
{
while(s<b)
{printf("hi");
i++;
s+=a[i];
}
while(b<s)
{
j--;
b+=a[j];
}
if(s==b&&i+1==j-1){
printf("the posn = %d",i+1);
break;
}
}
printf("element nt found");
getch();
return 0;
}
recursive approach
int checkEquinArr (int a[], int ind, int size, int prevsum, int *eqpoint);
int main ()
{
int a[] = {1, 3, 4, 10, 1, 7};
int n = sizeof(a)/sizeof(int);
int eqpoint = -1;
checkEquinArr (a, 0, n, 0, &eqpoint);
printf ("eqpoint: %d\n", eqpoint);
return 0;
}
int checkEquinArr (int a[], int ind, int size, int prevsum, int *eqpoint)
{
int nextsum;
if (ind == size-1)
{
return a[ind];
}else if (ind < size-1)
{
nextsum = checkEquinArr(a, ind+1, size, prevsum+a[ind], eqpoint);
if (prevsum == nextsum)
*eqpoint = ind;
return nextsum+a[ind];
}
}
1.] Loop thru given array start from index "1" until index is "array.lenght-2"
Each time find sum of elements
a.)in the left of index and right of index
b.)compare both sums if equal return equi point
else
increase index and do same.
public class ArrayApp {
//return Equi point if found else Zero
public static int findEquiPoint(int[] arry)
{
//start from array index 1
int num =1;
//loop until array index is array.lenght-2
while(num<arry.length-1)
{
int leftSum=0;
int rghtSum=0;
//Calculate leftSum
for(int i=0;i<num;i++)
{
leftSum=leftSum+arry[i];
}
//Calculate rightsum
for(int j=num+1;j<=arry.length-1;j++)
{
rghtSum=rghtSum+arry[j];
}
//Compare both sums
if(leftSum==rghtSum)
{
return num;
}
else
{
num++;
}
}
return 0;
}
public static void main(String[] args) {
int[] arry1={10,6,4,1,16,4};
int res=ArrayApp.findEquiPoint(arry1);
if(res==0)
{
System.out.println(" no equi point ");
}
else
{
System.out.println(" index of equi point "+res+" element at index point "+arry1[res]);
}
}
}
// 0 will be returned if no equilibrium point else index of the equilibrium point
public static int findEquilPoint(int[] Arr) {
int sumLArr = 0;
int sumRArr = 0;
int eqPoint = 1;
if (Arr.length < 3) {
System.out.println("Cannot find equilibrium point...");
return 0;
}
for (int i = 0; i < Arr.length; i++) {
if (i < eqPoint) {
sumLArr += Arr[i];
} else if (i > eqPoint) {
sumRArr += Arr[i];
}
}
while (eqPoint <= Arr.length - 2) {
if (sumLArr == sumRArr) {
return eqPoint;
} else {
sumLArr += Arr[eqPoint];
sumRArr -= Arr[eqPoint + 1];
eqPoint = eqPoint + 1;
}
}
return 0;
}
private static void findEquilibirum() {
Object arr[] = {1,2,3,4,5,6,7,8,9,10,11};
if((arr.length-1)%2 == 0){
System.out.println(arr[(arr.length-1)/2]);
}else{
System.err.println("No Equilibrium found");
}
}
None of the above would work for -ve values:
below would work:
public static int equilibrium(int[] data){
int equilibriumSum = 0;
for (int i = 0; i < (data.length-1) ; i++){
equilibriumSum += data[i];
}
int checkSum = 0;
for(int i = data.length-1; i > 0; i--){
checkSum += data[i];
equilibriumSum -= data[i-1];
if(equilibriumSum == checkSum)
return i-1;
}
return -1;
}
public static int equilibrium(int[] data){
int partial_sums = int[data.length];
partial_sums[0] = data[0];
for (int i = 1; i < data.length; i++) {
partial_sums[i] = partial_sums[i - 1] + data[i];
}
for (int i = 1; i < data.length; i++) {
if (partial_sums[i] == partial_sums[data.length - 1] - partial_sums[i]) {
return i;
}
}
}
###### equilibrium element ######
S Y S
Add all the elements, Sum = 2S+Y , its half = S+Y/2 = R
now from the index 1 keep on adding S[I] {sum till ith element} + A[i+1]/2 until you find it equal to R , that ith element will be the equilibrium point..
#include<iostream>
using namespace std;
int equ_point(int *arr,int n)
{
int left_sum = arr[0];
int right_sum = 0;
int eq_pt;
for(int i=2;i<n;i++)
right_sum += arr[i];
for(eq_pt = 1;eq_pt<n-1;)
{
if(left_sum == right_sum)
return eq_pt;
left_sum += arr[eq_pt];
eq_pt++;
right_sum -= arr[eq_pt];
}
return -1;
}
int main()
{
int arr[10] = {1,2,-3,4,-5,6,-5,0,2,0};
cout<<equ_point(arr,10);
}
Question:
1. {0,0} How many equilibrium points does it have?
2. {4} What's the equilibrium point?
3. Is it possible to have more than 1 equilibrium point in a normal integer array?
public class Equillibrium {
public static void equi(int[] array) {
if (array.length == 0) {
return;
}
if (array.length == 1) {
System.out.println("Equilibrium Point:" + "0:" + array[0]);
return;
}
int left_sum = 0;
int right_sum = 0;
for (int i = 0; i < array.length; i++) {
left_sum = sum(array, 0, i);
right_sum = sum(array, i, array.length - 1);
if (left_sum == right_sum) {
System.out.println("Equilibrium Point:" + i + "-" + array[i]);
}
}
}
private static int sum(int[] array, int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += array[i];
}
return sum;
}
public static void main(String[] args) {
// int[] array = { 1, 3, 4, 10, 18, 3, 1, 6, 3, 1, 4 };
// int[] array = {3,4,5,2,5};
// int[] array = {0,0};
int[] array = { -3, 0, 3, -3, 0, 3 };
equi(array);
}
}
public int equi ( int[] A ) {
if(A ==null) return -1;
if(A.length == 1)return A[0];
if(A.length == 2)
return(A[0]== A[1])? 0: -1;
int right=A.length-1;
int equiPoint = -1;
//extra space O(2*n) = O(n) ? Fix_it
int[] leftSumArr = new int[A.length];
int[] rightSumArr = new int[A.length];
int leftSum =0, rightSum=0;
//time complexity O(n)
for(int i=0; i<A.length;i++){
int k = right-i;
leftSum = leftSum+A[i];
leftSumArr[i]= leftSum;
rightSum = rightSum+A[k];
rightSumArr[k] = rightSum;
if(i == A.length-1){
if(leftSumArr[A.length-1] == rightSumArr[A.length-1] ){
equiPoint = i;
}
}
if(k ==0){
if(leftSumArr[0] == rightSumArr[k] ){
equiPoint = k;
}
}
if((k-2 >= 0) &&(leftSumArr[k-2] == rightSumArr[k])){
equiPoint = k-1;
}
if((i +2 <= A.length-1) &&(leftSumArr[i] == rightSumArr[i+2])){
equiPoint = i+1;
}
}
return equiPoint;
}
static void test2DArray(int[][] matrix) {
if (matrix.length == 0)
return;
int xMax = matrix.length;
int jMax = matrix[0].length;
int[][] leftMatrix = new int[xMax][jMax];
int[][] rightMatrix = new int[xMax][jMax];
for (int i = 0; i < xMax; i++) {
// walk through row e.g. column by column
int leftCount = 0, rightCount = 0;
for (int j = 0; j < jMax; j++) {
leftCount += matrix[i][j];
leftMatrix[i][j] = leftCount;
}
// walk through row e.g. column by column
for (int j = jMax - 1; j >= 0; j--) {
rightCount += matrix[i][j];
rightMatrix[i][j] = rightCount;
}
for (int j = 0; j < jMax; j++) {
if (leftMatrix[i][j] == rightMatrix[i][j]) {
System.out.println("match for (i,j):(" + i + "," + j + ")");
}
}
}
}
#include <iostream>
using namespace std;
int main() {
int arr[] = { 1, 3, 4, 10, 18, 3, 2, 6, 3, 1, 4 };
int nLen = sizeof(arr) / sizeof(int);
int i = 0, j = nLen - 1;
int sum1 = 0, sum2 = 0;
while (i < j) {
if (sum1 >= sum2) {
sum2 += arr[j--];
}
else {
sum1 += arr[i++];
}
}
getchar();
return 0;
}
int a[] ={1,3,4,10,18,3,1,6,3,1,4}; // 18 is the point..
- Vikas June 23, 2011int len = a.length;
int j = len-1,i=0;
int temp_sum1=0,temp_sum2=0;
while ( (j-i)>=1 ) {
if(temp_sum1>temp_sum2)
temp_sum2 = temp_sum2 + a[j--];
else
temp_sum1 = temp_sum1 + a[i++];
}
if(temp_sum1 == temp_sum2)
System.out.println("point " + a[i]);