Codility

Is this really a 1 silver star difficulty as your ...

2012-02-02T17:45:58.127+01:00

Is this really a 1 silver star difficulty as your tasks page shows?

Python 100% score: def equi ( A ): '''...

2012-01-31T22:05:09.858+01:00

Python 100% score:

def equi ( A ):
''''N = len(A)
''''total = sum(A)
''''lefts = 0
''''for p, value in enumerate(A):
''''''''partial = total - value
''''''''if partial % 2 == 0 and lefts == (partial / 2) and 0 <= p < N:
''''''''''''return p
''''''''lefts += value
''''return -1

We are not removing any tasks from the pool, becau...

2012-01-31T17:26:26.727+01:00

We are not removing any tasks from the pool, because this can be really painful for recruiters in the middle of the process. We mark tasks as "wel-known" once we see that its screening ability diminished. We keep adding new tasks (average one task per week). Interestingly, some tasks do not deteriorate even after long time on-line. We track occurrences of solutions to Codility tasks online and it shows that most of solutions on-line are wrong. This is beneficial--cheaters trying to copy solutions are likely to copy the wrong ones.

Definitely you are right. But changing questions s...

2012-01-31T12:05:33.717+01:00

Definitely you are right. But changing questions should depend also from the usage of each question. Some are more popular than other.

What You think ?

2012-01-26T12:41:19.212+01:00

What You think ?

I think that tasks should be changed every 1 year ...

2012-01-26T12:40:38.449+01:00

I think that tasks should be changed every 1 year for example.

People who solve tasks, exchange information with colleagues, publish the content and solutions of tasks on forums, etc.. Systematic knowledge about the tasks becomes publicly available.

Armchairathelete, OK let's do the math: MED w...

2012-01-12T14:36:41.889+01:00

Armchairathelete, OK let's do the math:

MED works for two segments of (almost) equal sizes.
If their sizes differ significantly, MEDIAN truncates the longer segment.

Let us assume, that x > y.
So, we would like to eliminate c.a. x-y elements from the first segment without changing the median.
x+y is odd, so x-y is also odd.
Moreover total length of the two segments should stay odd.
Therefore we have to eliminate x-y-1 elements from the first segment.
The idea is to eliminate z=(x-y)//2 elements larger and the same amount of elements smaller than the median.

There are x + y = 2*y + 2*z + 1 elements in the two segments.
So y+z of them are less or equal to the median, and y+z of them are larger or equal to the median.

If A[p+z] >= B[s], then we are lucky: A[p+z] is the median. There are y+z elements less or equal, namely: A[p..p+z-1] and B[r..s], and y+z elements larger or equal, namely: A[p+z+1..q].

Similarly, if A[q-z] <= B[r] we are also lucky: A[q-z] is the median. There are y+z elements less or equal, namely: A[p..q-z-1], and y+z elements larger or equal, namely: A[q-z+1..q] and B[r..s].

Even when it seems, that we are unlucky, we are lucky!
If A[p+z] < B[s] and A[q-z] > B[r], then A[p..p+z-1] are among z+y-1 bottom elements,
and A[q-z+1..q] are among z+y-1 top elements.
Therefore, we can safely truncate the first segment to A[p+z..q-z] not changing the median.

The case when x < y is symmetrical.

I'm not sure I fully understand the simplifica...

2012-01-06T06:23:34.170+01:00

I'm not sure I fully understand the simplification process in median(), is there a place I can find the math done out step by step?

Nice solution, MED is so nicely done and nice impl...

2012-01-05T08:50:23.313+01:00

Nice solution, MED is so nicely done and nice implementation of Algo of five.

i did try with the approach mentioned in first comment, but missed to to carry indices instead passed sub-arrays as argument, causing trouble in bigger test-cases.

Good to learn from your blogs.

Nice and clear solution as always... One can solv...

2012-01-04T18:48:01.979+01:00

Nice and clear solution as always...

One can solve it using similar approach...
Let's say we have two sorted arrays A[1...m] and B[1...n] and we have to find median of two of them...(m+n)is odd
Let's start from rray A, and we pick i-th element we know that A[i] is greater in array A than i-1 elements.
If A[i] is a median of union, we know that A[i] is greater than (m+n-1)/2 so we immediately know the index in B array , j=(n+m-1)/2-(i-1)
so if A[i] is between B[j] and B[j+1] we found median in first step, if A[i] is higher or lower, we trim A by half and so on unless we find median. If our trimmed array has one element and it is not median, we do the binary search in array B and we find the median there for sure.
It seems easy to code but it is a little bit tricky...

Let us fix the root of the tree. (In the example i...

2011-11-09T02:25:54.939+01:00

Let us fix the root of the tree. (In the example it is 1.) The nodes are ordered in the increasing order of their heights. In the example, nodes 2, 3, 5, 6, and 7 are leaves (height 1). Nodes 4 and 8 are leaves' parents (height 2). The height of node 0 is 3, of node 9 is 4, and finally the height of the root 1 is 5.

I don't see any analogy between this algorithm and the Dijkstra's algorithm. Mainly, because in the Dijkstra's algorithm vertices are processed in the order of increasing distance from the starting vertex. Here, the tree is scanned twice, once in a bottom-up order and once in a top-down order.

Hi, I understood degree and order calculation but ...

2011-11-05T22:04:55.767+01:00

Hi, I understood degree and order calculation but didn't understand ordering concept? Could you please elaborate on ordering? Are you trying to mimic Dijkstra's algorithm? Thank you very much. This site is really helpful.

2011-11-04T22:19:55.769+01:00

This comment has been removed by the author.

By any chance did you compute the combinations inc...

2011-10-07T22:30:47.062+02:00

By any chance did you compute the combinations incorrectly and then correct them at the end, pajton? This worked for me and absolutely smashed the time limit for big4. Caching didn't occur to me either...

I think the caching wasn't necessary: I wrote ...

2011-10-04T22:31:56.623+02:00

I think the caching wasn't necessary: I wrote my solution in python and the times were almost OK. If I used modulo div it would pass all the tests

I tried that, but never thought about caching the ...

2011-10-04T21:46:50.420+02:00

I tried that, but never thought about caching the factorials. You learn something new everyday, I guess:D.

Great! I came close to this, I know I had to use m...

2011-10-04T15:49:42.991+02:00

Great! I came close to this, I know I had to use modular arithmetic, but didn't know that division by modulo exists and it's legal to use here.

So I only applied it to resulting factorials, which was far to slow:-).

Codility as many other systems is just pointless i...

2011-09-13T21:13:10.996+02:00

Codility as many other systems is just pointless in my opinion and I would doubt working with a company which rely on using those kind of systems. Programming and code optimization is a process which requires attention which lacks due to the pressure to complete the task. I understand that using those systems help companies in speeding up the selections, but I think it's very unfair especially because companies should hire people based on their potential(as whatever experience someone can have, a new job is always NEW!). Whether you are a computer/software programming geek or not, those systems are unfair. That's it.

2011-09-13T21:10:44.191+02:00

This comment has been removed by the author.

The PS test, lends itself to using a hash table, t...

2011-07-15T11:20:57.492+02:00

The PS test, lends itself to using a hash table, this means its hard to produce a solution in C in the time scale required (both writing and execution). Has anyone managed to do this?

I noticed the question did not state, what to do with an out of bounds data set.

This was my solution, it had a speed up but not a good enough one it seems.

int ps ( int A[], int n ) {
if (n<1 || n>1000000)
return -1;

int count;
int count2;

int test[1000000];
int test_total=0;
int pos=0;

for (count=0;count<n;count++)
{
int found=0;
for (count2=0; count2<test_total; ++count2)
if (test[count2]==A[count])
{
found=1;
continue;
}

if (!found)
{
pos=count;
test[test_total++]=A[count];

}
}
return pos;
}

Anybody got a solution to the disc intersections p...

2011-07-14T21:57:11.891+02:00

Anybody got a solution to the disc intersections problem that is < O(n^2)? I failed the tests on scalability.

Here was my attempt:

class Solution {

int number_of_disc_intersections ( int[]A )
{

int count = 0;

for(int i=0; i= j - A[j])
{
count++;
}

if(count > 10000000)
return -1;
}

}

return count;

}
}

Surely its not about a vector/array being 'in ...

2011-07-14T20:01:11.642+02:00

Surely its not about a vector/array being 'in equilibrium', its about the existence of a position P that satisfies the problem's conditions. For an array of size 0, this is false because of the condition: 0 <= P < N. No positions exist in an empty array and certainly no positions that are < N!

From the task description, I concluded that an emp...

2011-07-06T20:16:06.221+02:00

From the task description, I concluded that an empty vector (C++) was always in equilibrium (just like a vector with only 1 element) since for any index, the number of elements before or after is zero, so they're sums are equal (0).

Also, the concept that an empty container is in equilibrium "feels" right. So my check was if vector.size()>1 before using the algorithm, i.e. all vectors with a size of 0 or 1 are in equilibrium.

Brent212, Didn't see the reference to the sta...

2011-07-06T19:02:14.091+02:00

Brent212,

Didn't see the reference to the standard library in the task description, but I used std::accumulate().

So what's that C++ standard library that the t...

2011-06-28T21:33:02.474+02:00

So what's that C++ standard library that the task description mentioned as being useful?