[m-e-g-a-z]

Found this the other day, someone at work sent it to me so I thought I would post it. So far it looks good, a neat way to test interview candidates.

http://codility.com/...ke-sample-test/

This post has been edited by m-e-g-a-z: 03 September 2010 - 02:17 AM

[KYA]

I've seen this before, much nicer then any of the competition thus far. Got a 75% due to a O(n^2) solution

[m-e-g-a-z]

I got the same as you KYA for the same reason, much better then the one that was featured on here a couple weeks ago. This will scare off people who can't code. I'll prob go home and optimize my solution when I get home.

[KYA]

I'm trying to figure out how I would make it more efficient.

It cannot be done in O(log n) time since you have to touch every index at least once worse case (i.e no equilibrium indexes).

For each index you have to sum its "left" and "right" and that has to be done for every index, worse case.


I'm wondering if there's some mathematical theorem or principle I'm not thinking of.

[m-e-g-a-z]

Exactly. I wonder what the other members can come up with, if anyone can get 100%.

[KYA]

The histogram chart at the top right was fascinating. It appears that the vast majoirty of test takes scored a 0-20% on that question.

[m-e-g-a-z]

KYA, on 03 September 2010 - 03:48 PM, said:

The histogram chart at the top right was fascinating. It appears that the vast majoirty of test takes scored a 0-20% on that question.

I feel slightly more happier knowing I got higher, I wonder what other tests they have, first time i've heard of this equilibrium stuff.

[mojo666]

I havent taken the test, but this is how you get better than O(n^2).

Suppose we have the sequence 1,2,3,4,3,2,1

1.Add them all up to get 16 and store this in a variable called "right".
2.Add the value in a second variable called "current" into a variable called "left"
3.Subtract the ith value from "right" and store it in "current"
4.Repeat 2 and 3 until right==left or there are no more values
3.When right==left, you are at an equilibrium index.

The iterations will look like this.

0. 0, 0, 16
1. 0, 1, 15
2. 1, 2, 13
3. 3, 3, 10
4. 6, 4, 6 -> 4 is equilibrium

This algorithm is O(n)

[KYA]

Very nice. I ended up striking out the 'current' variable and putting the right == left conditional between the decrement of the 'right' and the increment of the 'left', respectfully.

100%

[AdamSpeight2008]

With a C# version I got 94/100, only losing point on extremely large numbers.

[Nikitin]

Simply keep track of left and right partial sums. Easy 100%.

[Nikitin]

KYA, on 03 September 2010 - 08:38 AM, said:

I'm wondering if there's some mathematical theorem or principle I'm not thinking of.

Just looking at the definition and doing elementary sum operations can give a solution.


So keeping a single partial sum is enough. Multiply each by 2, add the next element. If it equals to total sum, you found equilibrium point.

int equi ( int[] A ) {
    long[] partial_sums = new long[A.length+1];
    partial_sums[0]=0;
    for (int i = 0; i < A.length; i++)
        partial_sums[i+1] = partial_sums[i] + A[i];
    for (int i = 0; i < A.length; i++)
        if (2*partial_sums[i]+A[i] == partial_sums[A.length])
            return i;
    return -1;
}

There's probably a dozen other clever ways of solving it, if you really want to.

[mostyfriedman]

mojo666, on 03 September 2010 - 06:56 PM, said:

I havent taken the test, but this is how you get better than O(n^2).

Suppose we have the sequence 1,2,3,4,3,2,1

1.Add them all up to get 16 and store this in a variable called "right".
2.Add the value in a second variable called "current" into a variable called "left"
3.Subtract the ith value from "right" and store it in "current"
4.Repeat 2 and 3 until right==left or there are no more values
3.When right==left, you are at an equilibrium index.

The iterations will look like this.

0. 0, 0, 16
1. 0, 1, 15
2. 1, 2, 13
3. 3, 3, 10
4. 6, 4, 6 -> 4 is equilibrium

This algorithm is O(n)

I thought of the exact same solution.

[Ahmedn1]

can't open the site

[cfoley]

I got 94% in Java before I read the thread. Turns out I used the same method as mojo666, even down to having a variable called current until I refactored it out. I lost out on very large numbers too but changing the data type for my summations to long gave me 100%.