pierwsze podejście - 15 minut robienia i... 0 procent, bo miałem błąd off-by-one. Właczyłem od nowa, zamieniłem zero na jedynkę, po czym... miałem 11 procent, bo znowu coś wyskoczyło (jakiś prosty warunek brzegowy), więc go szybko uzupełniłem i wrzuciłem taki kod (jedna z wczesnych wersji):
function solution(A) {
let result;
if (!A.includes(1)) return 1;
for (let i = 0; i < A.length; i++) {
const c = A[i] + 1;
if (!A.includes(c)) result = c;
}
if (result < 0) result = 1;
return result;
}
dostałem 44 punkty i
Detected time complexity: O(N**2)
no i w pewnych innych warunkach brzegowych podawał inny wynik (correctness 80%, performance 0%).
przy okazji poprawiania warunku brzegowego (około 30 sekund mi zajęło poprawianie tego warunku), wpadłem na pomysł, żeby zmienić trochę algorytm i sortować tablicę
Wysmarowałem więc inne rozwiązanie od zera (przez 6 minut), ale coś fejlowało, bo znowu warunek brzegowy, wziąłem jakąś prostą poprawkę (znowu z 30 sekund) i coś nie działało, kolejną poprawkę (kolejne 30 sekund) i znowu. Potem dwie minuty znowu modyfikacja rozwiązania i znowu coś fejluje.
...
No i po iluś takich próbach - pokombinuj coś przez minutę, submituj, zobacz wyniki - zmodyfikuj algorytm - w końcu udało mi się osiągnąć 100 na 100.
i kodzik
function solution(A) {
A = A.filter(a => a >= 0).sort((a,b)=>a-b);
for (let i = -1; i < A.length; i++) {
const curr = i > -1? A[i] : 0;
if (curr < 0) continue;
const next = A[i + 1], candidate = curr + 1;
if (curr != next && next != candidate)
return candidate;
}
}
Detected time complexity:
O(N) or O(N * log(N))
Jakie wnioski?
- jestem pewnie słabym algorytmiarzem(tj. słabym olimpijczykiem, maturzystą, uczestnikiem hackatonu itp.) - nie umiałem napisać czegoś poprawnie za pierwszym razem, a potem nie przewidziałem przypadków brzegowych. Gdyby to był test do firmy to odpadłbym w przedbiegach (moja pierwsza próba nawet nie działała poprawnie!). Jakbym miał brać udział w olimpiadzie matematycznej czy hackatonie też bym przegrał.
- jednak jako developer wykazałem się jednak ogarnięciem i sprytem - wykorzystałem logi o błędach do poprawienia algorytmu, i w skutek tego osiągnąłem w końcu maksymalny wynik. Potrafiłem też szybko myśleć, skoro na sygnał "wywala się" potrafiłem szybko zmodyfikować algorytm, żeby kolejnymi krokami przybliżać się do postawionego sobie celu. Dostrzegam również wady ostatecznego rozwiązania, które nie zostały wykryte przez maszynę (np. nie podoba mi się, że filtruję i sortuję tablicę na wejściu, mam wrażenie, że to może być nie do końca wydajne).
Tylko, że tak - w realnej pracy programisty, wymagane są raczej te drugie skille - nikt nie każe zrobić czegoś w chwilę, tylko raczej ma się więcej czasu, kombinuje, poprawia się, żeby osiągnąć dobre rozwiązanie. A ten test mierzy to pierwsze, czyli umiejętność klepania algorytmów na czas.
Więc samo zadanie ciekawe, ale sam sposób działania Codility pozostawia wiele do życzenia (zwróćcie uwagę, że mogłem kilka razy podchodzić tylko dlatego, że była to wersja demo - więc wchodziłem jeszcze raz w całość. W zadaniu do pracy bym miał tylko jedno podejście i rosyjska ruletka - albo zadziała - albo nie). Czyli Codility mierzy umiejętność niepopełniania pomyłek, a niekoniecznie umiejętność myślenia.