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 .
źródło
Odpowiedzi:
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.
źródło
Myślę, że ocena powinna być przynajmniej dwuwymiarowa. FizzBuzz -
malloc
opisuje 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 implementacjamalloc
wymaga 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.
źródło
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.
źródło
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.
źródło