## Monday, March 26, 2012

### Hey Coders! We’re happy to announce our recent partnership with Whitetruffle, the eHarmony for technical talent.

Their recruiting platform leverages the same statistical modeling as the best dating, travel, and eCommerce systems to better match and introduce companies to candidates, starting with engineers. You’ll soon be able to add your Codility scores to improve the speed and accuracy of your matches.

If you’re tired of applying to jobs on job boards, getting spammed by technical recruiters, or reaching out to all of your friends to find a better job, this is a must. See the diagram below of how we plan to work together.

Together, we’re better solving two major problems for engineers:

1.     Relevance -- By providing Codility scores on Whitetruffle, they’re able to better match you with job opportunities for which you qualify.
2.     Intent -- By using Whitetruffle’s platform, you’re able to better identify the teams, companies, roles, locations of interest and much more. You’re also able to indicate whether or not you’re actively looking for jobs so you’re only contacted by companies when you’re interested.

The goal is to help our engineers better manage their careers with less time and effort. Since their public launch, Whitetruffle engineers have experienced introduction rates 5-10x higher than job boards, competition sites, direct applications, or even social recruiting.

Their team has worked with companies such as Facebook, Yahoo!, AppSumo, AirBnB, and TopTal. And their current customers include top companies from startups to Fortune 500 in the US and London.

Join whitetruffle.com today and tell them we've sent you.

## Wednesday, March 14, 2012

### Test coding skills with new task!

From now you can test your candidate's  coding skills with new programming task “BaseNeg2OfInt".

This is just one from more than 160 possibilities!

## Tuesday, March 6, 2012

### Omicron 2012 Codility Programming Certificate Solution

Another month has passed and it is time to reveal how the Codility Certificate codenamed Omicron can be solved. You can still give it a try, but no certificate will be granted. If you want to obtain a Codility Certificate, a fresh new problem is awaiting you here.

In the Omicron certificate problem, the task was to compute $$Fib_{N^M} \mod\ 10,000,103$$, where $$Fib_i$$ is the $$i$$-th Fibonacci number. Fibonacci numbers grow exponentially quickly, so without performing calculations modulo 10,000,103, one would have to use arbitrarily large integers. Note that 10,000,103 is a prime number. Unsurprisingly, you may have seen this trick in various Codility tasks before; it simplifies computations. As long as we use only addition, subtraction and multiplication, it suffices to perform all the operations modulo 10,000,103, and there is no need to implement arithmetic for arbitrary large integers. Even division can be used, though its implementation is less straightforward.

So, we can operate on ordinary'' integers and avoid arithmetical overflows. But how quickly can we compute Fibonacci numbers? There is a closed analytic formula: $$Fib_i = \frac{\varphi^i - (1 - \varphi)^i}{\sqrt{5}}$$, where $$\varphi$$ is the golden ratio $$\varphi = \frac{1+\sqrt{5}}{2}$$. Unfortunately, for $$i = N^M$$, use of this formula is not feasible due to the limited precision of floating point operations.

The second fastest method of computing Fibonacci numbers is based on matrix multiplication and uses only operations on integers. It is based on the following equation, where $$F = \left(\begin{array}{@{}cc@{}}1 & 1 \\ 1 & 0\end{array}\right)$$:

$$F \times \left(\begin{array}{@{}c@{}} Fib_n \\ Fib_{n-1} \end{array} \right) = \left(\begin{array}{@{}c@{}} Fib_{n+1} \\ Fib_n \end{array} \right)$$
Hence:
$$F^k \times \left(\begin{array}{@{}c@{}} Fib_{n} \\ Fib_{n-1} \end{array}\right) = \left(\begin{array}{@{}c@{}}Fib_{n+k} \\ Fib_{n+k-1}\end{array}\right)$$
Taking $$n=1$$, we obtain:
$$F^k \times \left(\begin{array}{@{}c@{}} 1 \\ 0 \end{array}\right) = \left(\begin{array}{@{}c@{}} Fib_{k+1} \\ Fib_k \end{array}\right)$$
Generally, one can prove by simple induction that:
$$F^k = \left(\begin{array}{@{}cc@{}} Fib_{k+1} & Fib_k \\ Fib_k & Fib_{k-1} \end{array}\right)$$

Powers of matrices can be computed in a similar way to powers of integers: by squaring and multiplication. Elements of $$A^k$$ (modulo 10,000,103) can be computed in $$O(\log k)$$ time. Here are procedures in Pascal to implement multiplication and exponentiation of $$2 \times 2$$ matrices, modulo 10,000,103, and to compute Fibonacci numbers:

  const
P = 10000103;

type
matrix = array[1..2, 1..2] of int64;

const
F  : matrix = ((1, 1), (1, 0));
id : matrix = ((1, 0), (0, 1));

function mul(A, B : matrix) : matrix;
var
C :  matrix;
begin
C[1,1] := (A[1,1] * B[1,1] + A[1,2] * B[2,1]) mod P;
C[1,2] := (A[1,1] * B[1,2] + A[1,2] * B[2,2]) mod P;
C[2,1] := (A[2,1] * B[1,1] + A[2,2] * B[2,1]) mod P;
C[2,2] := (A[2,1] * B[1,2] + A[2,2] * B[2,2]) mod P;
mul := C
end;

function pow(A : matrix;  K : longint) :  matrix;
begin
if K = 0 then
pow := id
else if K mod 2 = 0 then
pow := pow(mul(A,A), K div 2)
else
pow := mul(pow(A, K-1), A)
end;

function Fib(K :  longint) : longint;
var
A : matrix;
begin
A := pow(F, K);
Fib := A[1,2]
end;


Unfortunately, such a solution doesn't work for larger values of $$N^M$$. Even if we modified it to work for an arbitrarily large $$K=N^M$$, it would be too slow. Computing $$F^{N^M}$$ (modulo 10,000,103) requires $$O(\log (N^M)) = O(M \log N)$$ time.

Use of modulo 10,000,103 not only simplifies arithmetical operations: for any $$P>0$$, the sequence $$(Fib_i \mod P)$$ is periodic. It follows from the fact that values of $$Fib_i \mod P$$ and $$Fib_{i+1} \mod P$$ fully determine the following elements of this sequence, and there are at most $$P^2$$ different pairs of such values. In particular, for $$P = 10,000,103$$ the sequence $$(Fib_i \mod P)$$ has period $$Q = 20,000,208$$. Its value can be established by the use of a simple program. Here is a function in Pascal that computes the period for a given $$P$$:


function count_period(P : longint) : longint;
var
a, b, c, i : longint;
begin
a := 1;
b := 2;
i := 1;
while (a <> b) or (a <> 1) do begin
c := (a+b) mod P;
a := b;
b := c;
inc(i);
end;
count_period := i
end;


So, the task reduces to computing $$(Fib_{N^M \mod Q}) \mod P$$. Here is a procedure in Pascal that computes $$N^M \mod Q$$:

  function exp(N : int64; M : int64) : longint;
begin
if M = 0 then
exp := 1
else if M mod 2 = 0 then
exp := exp((N*N) mod Q, M div 2)
else
exp := (N*exp(N, M-1)) mod Q
end;

Finally, here is a solution to this task:
  function power_fib(N: longint; M : longint) : longint;
begin
power_fib := Fib(exp(N,M));
end;