Just to inform you guys, if you're interested in the Google Internship programs, you might want to perform a test on Codility. Just got inside information that they may use the site to test for credibility of your programming skills.

Try this challenge

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + , + A[P−1] = A[P+1] + , + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 7 elements:
A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0
P = 3 is an equilibrium index of this array, because A[0] + A[1] + A[2] = A[4] + A[5] + A[6].
P = 6 is also an equilibrium index, because: A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0 and there are no elements with indices greater than 6.
P = 7 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function
class Solution { public int equi(int[] A); }
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
Assume that:
N is an integer within the range [0, 10,000,000];
each element of array A is an integer within the range [−2,147,483,648, 2,147,483,647].
For example, given array A such that
A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0
the function may return 3 or 6, as explained above.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Err.

So conceptually couldn't I just:

1) Set i=0.
2) calculate the sum to the left and right of index i, producing two numbers A_i and B_i. I can compute the sums in O(N) time, of course (A_i=0 and requires no computation, B_i equals the sum of the list minus A[0] and takes O(N) time to compute.)
3) Then for k=(i+1). . .  (N-1), compute A_k and B_k. Note that I can do this cheaply just be adding/subtracting components from the original array. So I pay constant time to do each update on an iteration.
4) If I find an equilibrium index when looping from k=(i+1). . . (N-1), then halt the loop and output it.

I pay at most O(N) time in stage (2), and O(N) in stage 3. Throughout this problem, I'm also using only a constant amount of space beyond the original N length list.

I think the above algorithm is correct. All that would be left would be to implement it in Java (shouldn't be too hard.)

good thinking good product.nice pseudocode,i followed it and came up with the code below.dealing with p=0 and p = n-1.i know it doesnt run in o(n) time.i have problem analyzing my own code's running time.


public class Solution {

/**
* @param args
*/



public static int equi(int[] A){
int sum = A[0],sum2 = 0;
int p = -1;

for(int i=2;i<A.length;i++){
sum2 += A[i];
}

if((sum2 + A[1]) == 0)
return 0;
if(((sum2 + A[0] + A[1])-A[A.length-1]) == 0)
return p = A.length-1;


if(sum == sum2)
return 1;

for(int k=2;k<A.length;k++){
sum += A[k-1];
sum2 -= A[k];

if(sum==sum2)
return k;
}

return p;

}
public static void main(String[] args) {
// TODO Auto-generated method stub

int[] A = {-7,1,5,2,-4,3,0};

System.out.println(equi(A));


}

}

^-- cool!

Is there any programming buk that can take u thru this array programming?

@Danyl

Most data structures and algorithms book always start with a study on arrays because it is a basic data structure that is very handy and is used to build other abstract data structures.

I have some algorithms books (sedgewick and goodrich) in java.

^-- I've heard good things about the Sedgewick book, though never used it.

I can personally recommend using "Data Structures and Algorithms in Java" by Lafore. Nice, clear explanations.

ekt_bear:

^-- I've heard good things about the Sedgewick book, though never used it.

I can personally recommend using "Data Structures and Algorithms in Java" by Lafore. Nice, clear explanations.

Lafore is good but i prefer Goodrich and lately sedgewick which is next to knuth's in levels of abstraction while i read skiena for practical and programming challanges purposes.