Ranking pytań do wywiadu FizzBuzz (1), wdrożenie malloc (10) [zamknięte]

Chciałbym poznać Twoją opinię na temat trudności następującego pytania podczas rozmowy kwalifikacyjnej:

Znajdź ciągłą podtablicę z maksymalną sumą w tablicy liczb całkowitych w czasie O (n).

Ten trywialny problem brzmieniowy zasłynął Jon Bentley w swoich Programming Pearls, gdzie wykorzystuje go do zademonstrowania technik projektowania algorytmów.

W skali 1-10, 1 oznacza test FizzBuzz (lub HoppityHop ), a 10 oznacza implementację funkcji C stdlib malloc (), jak oceniłbyś powyższy problem?

Myślę, że ludzie, którzy najlepiej potrafią odpowiedzieć na to pytanie, to ci, którzy przeczytali Perły programistyczne i próbowali rozwiązać ten problem samodzielnie. Aby zmotywować tych, którzy tego nie zrobili, „Programming Pearls” pojawia się wiele razy na liście „10 najlepszych książek o programowaniu”.

Kilka komentarzy może pomóc uzyskać lepszą ocenę:

• Wdrożenie malloc () nie jest tak trudne, jak się wydaje. Zobacz na przykład język programowania C w K&R. Czasami jest pytany w Microsoft .

• Obserwacja CLRS na temat rozwiązywania problemów: często trudniej jest rozwiązać problem od zera niż zweryfikować jasno przedstawione rozwiązanie, szczególnie w przypadku pracy w ograniczonym czasie .

To naprawdę zależy od dewelopera.

Gdyby Malloc miał 10 lat, oceniłbym ten problem na 20. Ale znowu zrobiłem już Malloc i prawdopodobnie mógłbym to zrobić ponownie.

Ktoś, kto rozwiązał ten problem lub zna odpowiedni algorytm na czubku głowy, ustawi go na 5, a malloc () na 10.

Problem z tego typu pytaniami polega na tym, że jeśli zrobiłeś je wcześniej, to są one łatwe i naprawdę jest to test, czy widziałeś już ten algorytm. Dlatego nie lubię ich za wywiady.

Teraz w przypadku testów, w których dajesz programistom kilka dni, jest to bardzo dobry test, ponieważ jeśli nie znają algorytmu, dajesz im szansę przeprowadzenia badań i przyspieszenia, a jest to test nie tylko twoja wiedza, ale twoja zdolność do zdobywania nowej wiedzy.

Myślę, że ocena powinna być przynajmniej dwuwymiarowa. FizzBuzz - mallocopisuje zasięg na jednej osi, nazwałbym to „złożonością technologiczną”. Ale ten jeden wymiar z pewnością nie wystarcza do opisania problemu. Aby rozwiązać omawiany problem, programista powinien myśleć więcej niż kod , a implementacja mallocwymaga więcej dyscypliny kodowania niż tworzenia skomplikowanych algorytmów.

Oto jak zorganizowałbym te problemy:

Aby zilustrować moją tezę, dodałem do wykresu sortowanie metodą scalania równoległego , ponieważ, jak sądzę, jest to dobry przykład zaawansowanego technologicznie i algorytmicznie zadania.

Myślę, że jest to znacznie trudniejsze niż FizzBuzz lub HoppityHop - te dwie rzeczy to nic innego jak prosta pętla typu „if-else” lub „case-switch”.

Maksymalna podgrupa będzie wymagała głębszej analizy leżącego u podstaw problemu - nie jest to coś, czego można się spodziewać w klasie programowania dla początkujących, ponieważ wymaga wyższych umiejętności matematycznych niż problem typu FizzBuzz. Ten problem jest podobny do problemu najkrótszej ścieżki, który rozwiązuje algorytm Dijkstry - być może jest to specjalizacja problemu najdłuższej ścieżki .

W skali od 1 do 10 prawdopodobnie oceniłbym go między 3 a 5.

* Gdy serwer był wyłączony, odkryłem, że problem maksymalnych podtablic ma swoją stronę na wikipedii.

Daję mu 3. Poza większością programistów, z którymi rozmawiałem, ale łatwy problem dla tych, których poleciłem do zatrudnienia.