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

10

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 .

blrs
źródło
12
Trudność polega na tym, że liczby całkowite mogą być ujemne? (w przeciwnym razie cała tablica jest zawsze największą podtablicą, stąd O (1) :-P)
Macke
4
Problem powinien
brzmieć
6
Nie uczyniłbym „w O (n)” wymogiem w wywiadzie. Możesz zacząć od naiwnego rozwiązania, a następnie dopracować je, jeśli chcesz, ale nie spodziewałbym się, że ktoś będzie w stanie uzyskać rozwiązanie O (n) w 1-godzinnym wywiadzie bez uprzedniej ekspozycji na ten algorytm.
Dean Harding
2
Dobrze. Jest to prosty problem, jeśli pozwalasz na rozwiązania O (n²).
dan04
@Dean, mam nadzieję, że będą w stanie przenieść działającą sumę typu uśrednienia z lokalizacji j do j + 1 w O (1). Być może, aby być uczciwym, może to być podpowiedź. (Zakładam, że długość podtablicy została wcześniej określona)
Omega Centauri

Odpowiedzi:

17

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.

Martin York
źródło
pogoda -> czy w czwartym akapicie (i przepraszam za hałas, nie mam przedstawiciela do edytowania literówek ...)
Matthieu M.
Martin, myślę, że to zależy od rodzaju aplikacji, z którą przeprowadzasz wywiady z ludźmi. W przypadku typów systemów Malloc jest dość prosty. Dla mnie - utknąłem [zakładam, że adres stosu i długość itp. Zostały celowo ukryte przede mną] przy pomocy malloc, ale problem z podtablicą jest prawie trywialny. Kluczem jest dopasowanie pytań do potrzeb pracy.
Omega Centauri
8

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:

wprowadź opis zdjęcia tutaj

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.

P Shved
źródło
2

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.

oosterwal
źródło
Czy ktoś może wyjaśnić, dlaczego potrzebny jest algorytm opisany na wikipedii, gdy działa dla mnie następujący koncepcyjnie znacznie prostszy algorytm: W jednym przejściu oblicz sumę sumaryczną, znajdując minimum i maksimum w zwykły sposób. Maksymalna suma kolejnych podsekwencji rozpoczyna się po minimalnym indeksie sumy i rozciąga się aż do maksymalnego indeksu sumy włącznie.
Ben Voigt
2
@Ben Voigt: wypróbuj sekwencję {+2, -4, +1} lub {+1, +1, -1, -1, -1, -1, +1}. W rzeczywistości metoda Kadane jest bardzo prosta - skanuje tablicę tylko raz i aktualizuje trzy zmienne w stylu programowania dyanmicznego.
rwong
@rwong: ah ok, Kadane jest potrzebny w przypadku, gdy minimum następuje po maksimum. I liczę 5 zmiennych, a nie 3, plus indeks pętli.
Ben Voigt
@Ben: masz rację, to 5 zmiennych plus indeks pętli.
rwong
1

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.

Kevin Cline
źródło