Codility - sprawdź swojego programistę

Niedawno miałem okazję trafić na stronę codility.com i pomysł mi się całkiem spodobał. W skrócie: ma ona na celu głównie ułatwić (nieco zautomatyzować) proces rekrutacji programistów w firmach. Pozwala wygodnie i szybko dokonać wstępnej weryfikacji umiejętności programisty. Ze strony kandydata wygląda to tak, że otrzymuje on zadanie, które należy rozwiązać za pomocą jednego z wybranych języków. Po zakończeniu zadanie to jest testowane różnymi parametrami wejściowymi, które mają ujawnić potencjalne mankamenty stworzonego algorytmu i za każdy pozytywnie zaliczony test przybywa punktów, których można mieć maksymalnie 100.

Przykładowe zadanie, na podstawie którego można przetestować sposób działania strony, jest (jak na razie) zawsze takie same, więc można sobie poeksperymentować. Zadanie polega na stworzeniu funkcji, która jako parametr, przyjmuję tablicę int'ów, a zwraca index będący Equilibrium danej tablicy (elementem, dla którego suma elementów tablicy po jego lewej stronie jest równa sumie elementów po stronie prawej).

Ponieważ zadanie ma ograniczenie czasowe, na start wybrałem język, w którym czuję sie pewniej, czyli PHP. Pierwsze podejście, to pewnie standardowe rozwiązanie, jakie każdemu przyjdzie do głowy, czyli dwie zagnieżdżone pętle. Treść zadania uczciwie ostrzegała o tym, że tablica może mieć duże rozmiary, a ja uczciwie to ostrzeżenie zignorowałem. W rezultacie pierwsze podejście zakończyło się wynikiem 75/100 (skutecznie padłem na testach oznaczonych, jako "O(n^2) solutions should fail." ;) ). Niezbyt zadowolony z rezultatu postanowiłem się nieco bardziej przyłożyć i przygotować lepszy algorytm, co po jednej drobnej poprawce dało upragnione 100 pkt. :)

Wtedy postanowiłem przetestować się także w Javie, co miało stanowić już tylko formalność, ale jednak życie potrafi zaskakiwać. Kod ładnie przepisany na Javę według dokładnie tego samego algorytmu prezentował się następująco:

int equi ( int[] A )
    {
    int iSuma = 0;
    int iLewo = 0;
    for (int i: A) iSuma+= i;
    for (int i = 0; i < A.length; ++i)
        {
        if (i > 0)
            iLewo+= A[i-1];
        if (iLewo == iSuma - A[i] - iLewo)
            return i;
        }
    return -1;
    }

Jednak otrzymany wynik, to 94/100, a niezaliczony test sprawdzał: "Sequence with extremly large numbers testing arithmetic overflow.". Trochę poprawek i 100 punktów osiągnięte także w Javie:

import java.math.BigInteger;

int equi(int[] A)
    {
    BigInteger iSuma = BigInteger.valueOf(0);
    BigInteger iLewo = BigInteger.valueOf(0);
    BigInteger iPrawo;
    for (int i : A)
        iSuma = iSuma.add(BigInteger.valueOf(i));
    for (int i = 0; i < A.length; ++i)
        {
        if (i > 0)
            iLewo = iLewo.add(BigInteger.valueOf(A[i - 1]));
        iPrawo = BigInteger.valueOf(0);
        iPrawo = iPrawo.add(iSuma);
        iPrawo = iPrawo.subtract(BigInteger.valueOf(A[i]));
        iPrawo = iPrawo.subtract(iLewo);
        if (iLewo.equals(iPrawo))
            return i;
        }
    return -1;
    }

Nauczka na przyszłość: nowy język - nowe niespodzianki :)