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 :)
C->Master napisał(a): 2010-06-17 12:29
A ja się trochę pobawiłem i zrobiłem to w samo C.
int equi(int arr[], int n)
{
long long int iSuma = 0;
long long int iLewo = 0;
int j,i;
int iReturn = -1;
for (j = 0;j < n; j++)
iSuma += arr[j];
for (i = 0; i < n; i++){
if (i > 0) iLewo+= arr[i-1];
if (iLewo == iSuma - arr[i] - iLewo){
iReturn = i; }}
return (iReturn);}
m napisał(a): 2010-10-28 00:26
ja mam w javie bez tych BIGów na 100
int equi ( int[] A ) {
int rightSum=0,leftSum=0;
for (int i=0; i<A.length; i++){
rightSum+=A[i];
}
int current;
for (int i=0; i<A.length; i++){
current=A[i];
rightSum-=current;
if (leftSum==rightSum){
return i;
}
leftSum+=current;
}
return -1;
}
K napisał(a): 2010-10-29 19:26
Wydaje mi sie, ze bardziej czytelnie wygladaloby rozwiazanie polegajace na zastapieniu int na long w niektorych miejscach w pierwszym rozwiazaniu, bez wytaczania BigInteger'ow :)
VGT napisał(a): 2010-10-30 02:23
@k:
Fakt, teraz pewnie bym tak zrobil, ale wtedy jakoś nie przyszło to do głowy i z jednej skrajności poszedłem w drugą ;)
dpc napisał(a): 2010-11-22 13:33
Optymalizacja:
int equi ( int A[], int n ) {
signed long long sum = 0;
signed long long l = 0;
int i;
for (i = 0; i < n; ++i) {
sum += A[i];
}
for (i = 0; i < n; ++i) {
sum -= A[i];
if (sum == l) {
return i;
}
l += A[i];
}
return -1;
}
dobry napisał(a): 2011-03-06 18:37
co ciekawe, w przypadku C++ long int nie wystarczył. zastosowałem double i dopiero wtedy dostałem 100
blady napisał(a): 2011-10-23 22:51
Hey! Dzięki za opis problemu. Co powiecie na takie rozwiązanie? bez sum, jedna pętla:
pozdrawiam
public int equilibriumIndex(long[] values){
int leftIndex = 0;
int rightIntex = values.length - 1;
long left = values[leftIndex];
long right = values[rightIntex];
long substract = left- right;
do {
if (substract > 0)
substract -= values[--rightIntex];
else
substract += values[++leftIndex];
} while (rightIntex != leftIndex);
return rightIntex;
}