Google Interview Question
Software EngineersCountry: United States
int GetEquiPoint(vector<int> &V)
{
if (V.empty())
{
return (-1);
}
if (V.size() == 1)
{
return 0;
}
vector<int> Prev(V.size(), 0);
vector<int> Post(V.size(), 0);
int Found = -1;
for (int i = 1; i < Prev.size(); ++i)
{
Prev[i] = Prev[i - 1] + V[i - 1];
}
for (int i = Post.size() - 2; i >= 0; i--)
{
Post[i] = Post[i + 1] + V[i + 1];
if (Post[i] == Prev[i])
{
Found = i;
break;
}
}
return (Found);
}
int equilibriumElement(int[] array, int N)
{
// Base Case
if(N == 0)
return -1;
long totalSum = 0;
long sumTillNow 0;
for(int i = 0; i< N ; i++)
totalSum += array[i];
if( sumTillNow == totalSum)
return 0;
sumTillNow = array[0];
for(int p = 1; p < N; p++)
{
if( sumTillNow == totalSum - sumTillNow - array[P])
return P;
sumTillNow += array[P];
}
return -1;
}
int equilibriumElement(int[] array, int N)
{
// Base Case
if(N == 0)
return -1;
long totalSum = 0;
long sumTillNow 0;
for(int i = 0; i< N ; i++)
totalSum += array[i];
if( sumTillNow == totalSum)
return 0;
sumTillNow = array[0];
for(int p = 1; p < N; p++)
{
if( sumTillNow == totalSum - sumTillNow - array[P])
return P;
sumTillNow += array[P];
}
return -1;
}
int equilibriumElement(int[] array, int N)
{
// Base Case
if(N == 0)
return -1;
long totalSum = 0;
long sumTillNow 0;
for(int i = 0; i< N ; i++)
totalSum += array[i];
if( sumTillNow == totalSum)
return 0;
sumTillNow = array[0];
for(int p = 1; p < N; p++)
{
if( sumTillNow == totalSum - sumTillNow - array[P])
return P;
sumTillNow += array[P];
}
return -1;
}
public static int findEquilibriumPoint(int[] numbers) {
int[] leftSum = new int[numbers.length + 1];
if (numbers.length == 0) {
throw new RuntimeException("Numbers array is empty");
}
leftSum[0] = numbers[0];
for (int i = 1; i < numbers.length; i++) {
leftSum[i] = leftSum[i - 1] + numbers[i];
}
int sum = 0;
for (int i = numbers.length - 1; i >= 0; i--) {
sum = numbers[i] + sum;
numbers[i] = sum;
if (leftSum[i] == numbers[i]) {
return i;
}
}
return -1;
}
public static int findEquilibriumPoint(int[] numbers) {
int[] leftSum = new int[numbers.length + 1];
if (numbers.length == 0) {
throw new RuntimeException("Numbers array is empty");
}
leftSum[0] = numbers[0];
for (int i = 1; i < numbers.length; i++) {
leftSum[i] = leftSum[i - 1] + numbers[i];
}
int sum = 0;
for (int i = numbers.length - 1; i >= 0; i--) {
sum = numbers[i] + sum;
numbers[i] = sum;
if (leftSum[i] == numbers[i]) {
return i;
}
}
return -1;
}
#include <stdio.h>
int equilibrium(int arr[], int n)
{
int sum = 0; // initialize sum of whole array
int leftsum = 0; // initialize leftsum
int i;
/* Find sum of the whole array */
for (i = 0; i < n; ++i)
sum += arr[i];
for( i = 0; i < n; ++i)
{
sum -= arr[i]; // sum is now right sum for index i
if(leftsum == sum)
return i;
leftsum += arr[i];
}
/* If no equilibrium index found, then return 0 */
return -1;
}
int main()
{
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("First equilibrium index is %d\n", equilibrium(arr, arr_size));
getchar();
return 0;
}
int solution(int A[], int n)
{
if (n <= 0) return -1;
if (n == 1) return 0;
int sum = 0, sumLeft = 0, sumRight = 0;
for (int i = 0; i < n; i++)
sum += A[i];
if ((sum - A[0]) == 0)
return 0;
sumRight = sum - A[0];
sumLeft = A[0];
int indx = 1;
int previndx = -1;
while (indx < n)
{
sumRight -= A[indx];
if (sumLeft == sumRight)
{
previndx = indx;
break;
}
sumLeft += A[indx];
indx++;
}
return previndx;
}
Swift 2.2
func sumOfItems(array:[Int]) -> Int {
var sum = 0;
for i in 0 ..< array.count {
sum += array[i]
}
return sum
}
func getEquils(array:[Int], n:Int) -> [Int] {
var result = [Int]()
var leftSum = 0
var rightSum = sumOfItems(array) - array[0]
if (leftSum == rightSum) {
result.append(0)
}
for i in 1 ..< n {
leftSum += array[i - 1]
rightSum -= array[i]
if (leftSum == rightSum) {
result.append(i)
}
}
return result
}
getEquils([-1, 3, -4, 5, 1, -6, 2, 1], n: 8) // [1, 3, 7]
public class Equilibrium {
public static void getEquilibrium(int[] A) {
int sum = 0, sumL = 0, sumR;
for(int i=0; i<A.length; i++) {
sum += A[i];
}
sumR = sum - A[0];
for(int i=0; i<A.length; i++) {
if(i < A.length -1)
sumR -= A[i+1];
else
sumR = 0;
if(i >= 0)
sumL += A[i];
else
sumL = 0;
if(sumL == sumR) {
System.out.println("Equilibrium found: " + Integer.toString(i+1));
}
}
}
public static void main(String[] args) {
int[] A = new int[]{-1, 3, -4, 5, 1, -6, 2, 1};
Equilibrium.getEquilibrium(A);
}
}
You can maintain two arrays left[] and right[]. Now update left[] such that left[i]= sum of all numbers from index 0 to i and update right[] such that right[i] = sum of all numbers from last index to i. Now, the list of indices where left[i]=right[i] would be you solution.
Optimization:
We can first compute left[]. To compute right[] we can reuse the input arr. As you update the input, compare with left[] and return when you find the first match.
- Vijay July 30, 2016