# Programming Test

• (2 Pages)
• 1
• 2

## 21 Replies - 2834 Views - Last Post: 08 September 2010 - 04:32 PM

### #1 m-e-g-a-z

• Winning

Reputation: 495
• Posts: 1,451
• Joined: 19-October 09

# Programming Test

Posted 03 September 2010 - 02:16 AM

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

Is This A Good Question/Topic? 0

## Replies To: Programming Test

### #2 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: Programming Test

Posted 03 September 2010 - 09:03 AM

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

### #3 m-e-g-a-z

• Winning

Reputation: 495
• Posts: 1,451
• Joined: 19-October 09

## Re: Programming Test

Posted 03 September 2010 - 09:34 AM

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.

### #4 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: Programming Test

Posted 03 September 2010 - 09:38 AM

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.

### #5 m-e-g-a-z

• Winning

Reputation: 495
• Posts: 1,451
• Joined: 19-October 09

## Re: Programming Test

Posted 03 September 2010 - 09:44 AM

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

### #6 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: Programming Test

Posted 03 September 2010 - 09:48 AM

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.

### #7 m-e-g-a-z

• Winning

Reputation: 495
• Posts: 1,451
• Joined: 19-October 09

## Re: Programming Test

Posted 03 September 2010 - 09:55 AM

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.

### #8 mojo666

Reputation: 233
• Posts: 549
• Joined: 27-June 09

## Re: Programming Test

Posted 03 September 2010 - 09:56 AM

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)

### #9 KYA

• su wtf -am -i /doing/with/my/life

Reputation: 2979
• Posts: 19,033
• Joined: 14-September 07

## Re: Programming Test

Posted 03 September 2010 - 10:39 AM

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%

• MrCupOfT

Reputation: 1948
• Posts: 8,665
• Joined: 29-May 08

## Re: Programming Test

Posted 03 September 2010 - 10:54 AM

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

### #11 Nikitin

• D.I.C Regular

Reputation: 56
• Posts: 264
• Joined: 02-August 10

## Re: Programming Test

Posted 03 September 2010 - 11:45 AM

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

### #12 Nikitin

• D.I.C Regular

Reputation: 56
• Posts: 264
• Joined: 02-August 10

## Re: Programming Test

Posted 03 September 2010 - 12:44 PM

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.

### #13 mostyfriedman

• The Algorithmi

Reputation: 674
• Posts: 4,349
• Joined: 24-October 08

## Re: Programming Test

Posted 04 September 2010 - 01:59 PM

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.

### #14 Ahmedn1

Reputation: 18
• Posts: 531
• Joined: 04-August 09

## Re: Programming Test

Posted 04 September 2010 - 04:54 PM

can't open the site

### #15 cfoley

• Cabbage

Reputation: 1500
• Posts: 3,211
• Joined: 11-December 07

## Re: Programming Test

Posted 06 September 2010 - 11:35 AM

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%.