Codility

Codility to ciekawy serwis dla osób z HR, który służy do automatycznego testowania umiejętności programistycznych kandydatów.

Serwis w założeniach przypomina automatyczne sprawdzarki stosowane na konkursach programistycznych. Firma powstała w Anglii, ale sadząc po imionach i nazwiskach założyli ją Polacy ;) Może w końcu na rozmowach kwalifikacyjnych częściej będzie się dostawać zadania programistyczne niż te typu "Wieśniak musi przewieźć przez rzekę wilka, kozę i kapustę..."

Aby zobaczyć jak działa Codility można:
a) mieć szczęście i trafić na dział HR który tego używa,
b) samemu wykupić subskrypcję,
c) kliknąć przycisk "Demo test".

Jeżeli kogoś przeraża "geeks only!", to niech się nie przejmuje ;) Rozwiążmy tutaj (w Javie) zadanie, które jest tam prezentowane.

Dana jest tablica liczb A. Znajdź taki indeks i tej tablicy, że suma elementów o wyższych indeksach jest równa sumie elementów o indeksach niższych od i. Jeżeli mamy daną tablicę:

A[0] = -7
A[1] = 1
A[2] = 5
A[3] = 2
A[4] = -4
A[5] = 3
A[6] = 0

To poszukiwane indeksy to 3:

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

jak również 6:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

Ponieważ nie ma elementów o indeksie większym niż 6, więc ich suma jest równa 0.

Jeżeli takich indeksów jest kilka zwróć dowolny z nich. Jeżeli nie ma takiego indeksu zwróć -1.


OK... Pierwszym pomysłem pewnie będzie rozwiązanie siłowe:

int equi ( int[] A ) {
  for (int i = 0; i < A.length; ++i) {
    long L = 0;
    for (int j = 0; j < i; j++) {
      L += A[j];
    }
    long R = 0;
    for (int j = i + 1; j < A.length; j++) {
      R += A[j];
    }
    if (L == R) {
      return i;
    }
  }
  return -1;
}

Ma ono jednak złożoność obliczeniową O(n²). Słabo. A wystarczy zauważyć, że na początku po lewej stronie nie ma nic (L = 0), a po prawej stronie są wszystkie elementy (R = suma (i : A)). Teraz kiedy sprawdzamy pierwszy element A[0], to po lewej stronie nadal nic nie ma, natomiast strona prawa jest o ten element "uboższa" (R -= A[0]). Jeżeli L != R, to dodajemy A[0] do strony lewej (L += A[0]) i sprawdzamy kolejny element A[1] itd.

Przekuwając to na kod w Javie:

int equi ( int[] A ) {
  long L = 0;
  long R = 0;
  for (int a : A) {
    R += a;
  }
  for (int i = 0; i < A.length; ++i) {
    R -= A[i];
    if (L == R) {
      return i;
    }
    L += A[i];
  }
  return -1;
}

Łatwo, prosto i przyjemnie. Codility poda nam wynik punktowy, "wywróży" złożoność obliczeniową zaproponowanego rozwiązania i powie jakich testów nasz program nie przeszedł i dlaczego. Dostajemy nawet obrazek z rozkładem wyników punktowych i zaznaczoną naszą pozycją ;)