Jak ważne jest, aby programista wiedział, jak zaimplementować algorytm QuickSort / MergeSort z pamięci? [Zamknięte]

58

Przeglądałem swoje notatki i natknąłem się na implementację różnych algorytmów sortowania.

Kiedy próbowałem zrozumieć implementację QuickSort i MergeSort, przyszło mi do głowy, że chociaż programuję na życie i uważam się za przyzwoitego w tym, co robię, nie mam ani pamięci fotograficznej, ani siły mózgowej do wdrożenia tych algorytmów bez opierając się na moich notatkach. Pamiętam tylko, że niektóre z tych algorytmów są stabilne, a niektóre nie. Niektóre wymagają czasu O (nlog (n)) lub O (n ^ 2). Niektóre wykorzystują więcej pamięci niż inne ...

Czułbym się, jakbym nie zasługiwał na tego rodzaju pracę, gdyby tak nie było, ponieważ moja pozycja nie wymaga użycia żadnego algorytmu sortowania innego niż te, które można znaleźć w standardowych interfejsach API. Mam na myśli, ilu z was ma pozycję programistyczną, w której jest tak naprawdę ważne, abyście mogli samodzielnie zapamiętać lub wymyślić tego rodzaju rzeczy?

algorithms John Smith
źródło
13
Musisz pamiętać, że istnieje rozwiązanie i kiedy go użyć. Następnie przejdź do dokumentacji i zaimplementuj ją. Jeśli nie wiedziałeś o szybkim sortowaniu lub łączeniu, nadal będziesz używać bąbelkowego sortowania i patrzysz, jak twój program się indeksuje i wymyśla słabe rozwiązania, gdy zwiększa się ilość danych.
Pieter B,
1
Oprócz dobrych odpowiedzi wymienionych poniżej, zauważ również, że wiele firm wymaga (1) znajomości złożoności takich algorytmów, (2) płynnej implementacji ich na tablicy.
sakisk
3
Jestem pewien, że ważne jest, aby zapamiętać te algos, ponieważ często zdarza się, że Google jest offline. : o
Lee James
Musisz znać ich wydajność, przypadki użycia itp. Wiedza, jak wdrożyć je na pamięć, jest wymagana tylko przez firmy technologiczne w wywiadach.
sakisk
@PieterB, nie zgadzam się. Nie trzeba wiedzieć o „scalaniu” i „szybkim sortowaniu” do „najlepiej działającego algorytmu sortowania” Google
Hyankov,

Odpowiedzi:

117

Zapytajmy Alberta i zobaczmy, co ma do powiedzenia na ten temat:

„Nie muszę wiedzieć wszystkiego, muszę tylko wiedzieć, gdzie je znaleźć, kiedy tego potrzebuję”

- Albert Einstein , parafrazowany

Amen, brat Albert, Amen.

Po dokładnym przeanalizowaniu podstawowych algorytmów w dowolnej dyscyplinie (sortowanie, wyszukiwanie, cokolwiek) możesz zapomnieć o szczegółach implementacji, dopóki faktycznie nie potrzebujesz algo, w którym to przypadku przejrzysz go lub użyjesz istniejąca lib. 25 lat temu zbudowałem główny system wyszukiwania za pomocą drzewek B *, ale dziś musiałbym RTFM, aby dobrze z nich korzystać.

Peter Rowell
źródło
5
Cytat ten jest wątpliwy: „nie jestem w stanie znaleźć żadnych merytorycznych dowodów łączących powiedzenie z Einsteinem” .
Wok
9
Jak to odpowiada na pytanie? Powiedział „Nie muszę wszystkiego wiedzieć”, nie powiedział „Nie muszę nic wiedzieć”. Niektóre umiejętności są fundamentalne, a całe pytanie dotyczyło tego, czy dana informacja należy do kategorii umiejętności podstawowych, czy nie.
Konrad Rudolph
1
Myślenie, że celem jest zapamiętanie szybkiego sortowania, oznacza pominięcie sedna pytania. Oczywiście w prawdziwym świecie, gdybyś potrzebował ogólnego szybkiego sortowania, skorzystałbyś z procedury bibliotecznej lub poszukałeś kodu i skopiowałem go. Test polega na sprawdzeniu, czy rozumiesz rekurencję, niezmienniki pętli itp., A prośba o szybkie zanotowanie algorytmu sortowania jest po prostu bardzo prostym pokazem tej wiedzy. Jeśli nie jesteś w stanie ponownie uzyskać 20-liniowego szybkiego sortowania na miejscu, ile rzeczy rutynowo robisz naprawdę nieefektywnie lub niepoprawnie, nawet o tym nie wiedząc?
Larry Gritz
3
@ Larry: Myślę, że zapomniałem więcej niż wielu programistów wie o szczegółach algorytmów - a szybkie sortowanie od zera jest jednym z nich - z bardzo dobrego powodu - zdecydowałem się czytać o rzeczach na wysokim poziomie i używać języków wysokiego poziomu niż pozostać w misach o niskim poziomie szczegółowości implementacji. Szczerze mówiąc - nie dbam o to, jakiego rodzaju rutynę biblioteczną używam - może, jeśli o mnie chodzi, używać chochlików i wróżek. Dokumenty poinformują O () o rozmiarach - to wszystko, co muszę wiedzieć.
mattnz
2
@mattnz: Trochę spóźniona kontynuacja twojego „O () rozmiaru”. Jedną rzeczą, której nauczyłem się na poważnie, było to, że przy dużym zestawie danych zła lokalizacja odniesienia może całkowicie przytłoczyć O (). Być może masz algo O(n log n), ale jeśli dostaniesz dużo braków pamięci podręcznej lub (Boże, nie trafisz) trafisz na dysk, to n log nbędzie tylko miłe wspomnienie.
Peter Rowell,
49

  1. To naprawdę nie jest kwestia zapamiętywania. Jest to kwestia głębokiego zrozumienia ogólnych klas algorytmów, takich jak dzielenie i podbijanie. Jeśli naprawdę rozumiesz dziel i zwyciężaj, nie musisz zapamiętywać szybkiego sortowania. W razie potrzeby możesz go odzyskać na miejscu. Co więcej, prawdziwa wypłata nie polega nawet na samodzielnym odzyskaniu szybkiego sortowania, lecz na rozpoznaniu, kiedy nowy problem jest podatny na rozwiązanie typu dziel i zwycięż.

  2. Nie wszystkie zadania programistyczne są takie same. Niektóre prace wymagają dogłębnej znajomości algorytmów, niektóre potrzebują ludzi, którzy rozumieją teorię typów, a niektórzy potrzebują ludzi, którzy mogą zeskrobać dane z formularza internetowego i przenieść go do bazy danych. Niektóre prace wymagają nawet tych wszystkich umiejętności naraz. W jakiej pracy chcesz pracować?

Charles E. Grant
źródło
5
Nie sądzę, że można zrozumieć QuickSort bez pamiętania QuickSort. To nie jest skomplikowana i tajemnicza sprawa, to tylko dwa ogólne pomysły połączone. To samo dotyczy sortowania według scalania, ale masz tylko jeden pomysł: P
drxzcl
Nie zgadzam się z drugim punktem. wszystkie prace są takie same, tylko zmiany ankietera. ten bardzo dobrze zna sortowanie i uważa, że ​​każdy dobry programista musi znać sortowanie, ponieważ to wszystko, co wie i na czym mu zależy.
IAdapter
2
@IAdapter, na pewno jesteś! Wiem z własnego doświadczenia, że ​​wiedza i umiejętności potrzebne do mojej pierwszej pracy pisania makr TROFF dla firmy zajmującej się oprogramowaniem do pakowania w folię termokurczliwą bardzo różnią się od tych, których potrzebuję do mojej obecnej pracy w laboratorium biologii obliczeniowej.
Charles E. Grant,
@ CharlesE.Grant przez większość czasu interwenient nie sprawdza, czy masz umiejętności potrzebne do wykonywania pracy (nie pamiętam ostatniego pytania o javascript / css, które mi zadawano i robię aplikacje internetowe).
IAdapter
10

Myślę, że jedynym czasem, o którym musisz pamiętać, jest ubieganie się o pracę, kiedy musisz udzielić odpowiedzi na miejscu i nie masz zewnętrznych zasobów.

Miałem współpracowników, którzy przepisywali szybkie sortowanie i tak dalej, ale powtarzam im, aby wrócili do korzystania z wbudowanych funkcji sortowania w języku. Wiem, że w zależności od typów projektów, nad którymi pracujemy, musimy pamiętać inne algorytmy, ponieważ zwykle nie są one zawarte w standardowych bibliotekach, ale sortowanie nie jest takie, które pojawia się, ponieważ zwykle jest wbudowane w język.

Kiedy jednak musimy pamiętać o tych algorytmach, zwykle zwracamy się do Google'a lub książki i zazwyczaj nie szukamy konkretnej implementacji, ale jaka byłaby najlepsza implementacja dla naszego problemu.

straszny
źródło
6

Samo zapamiętanie, który algorytm jest użyteczny w jakich scenariuszach, byłoby więcej niż wystarczające, aby pomóc w pracy. W rzeczywistości większość zadań programistycznych nie wymaga zapamiętywania podejścia, a raczej interesuje ich sposób rozpoznawania wzorca algorytmicznego w obliczu problemu .

W rzeczywistości w większości blogów / artykułów programistycznych na temat algorytmów jest mnóstwo informacji. Zatem zapamiętanie dokładnej implementacji nie ma znaczenia. Najbardziej wartościową informacją byłoby uzyskanie podstawowego pojęcia o tym, jaki rodzaj algorytmu jest dostępny i jaki konkretny problem są dobre w rozwiązywaniu . Wyszukiwanie dokładnej implementacji, gdy wiesz, czego szukasz, jest dość szybkie.

Podsumowując, zawsze lepiej jest wiedzieć, czego szukasz i gdzie są odniesienia - które poprowadzą cię do źródła.

EL Yusubov
źródło
5

Dokładne wdrożenie nie jest bardzo ważne. Ale zasada łączenia / szybkiego sortowania - rekurencja, partycjonowanie itp. Są bardzo podstawowe i każdy programista powinien to zrozumieć. Algorytmy te są w rzeczywistości bardzo proste do opisania słowami, gdy zrozumiesz.

Nie jest tak naprawdę problemem, czy możesz to sprawdzić, czy możesz google, to jest, czy programista rozumie te techniki rozwiązywania problemów i może zastosować się do innych sytuacji.

hgh
źródło
3

Mam dwa zdania na ten temat. Znam wielu programistów, którzy nie wiedzą, czym jest algorytm sortowania, ale wykonują swoją pracę dość dobrze. Wierzę również w zrozumienie zasad, aby naprawdę zrozumieć dziedzinę.

Trudno mi uzyskać bezstronną odpowiedź na ten temat, ponieważ programuję tak długo, że prawdopodobnie zapomniałem więcej algorytmów, które obecnie znam - ale nadal znam sortujące wymienione w tym pytaniu. Myślę, że myślący przywódcy Agile (np. Ron Jeffries, Alistair Cockburn) mają dobre pomysły na ten pomysł (np. Shu-Ha-Ri).

Podsumowując tę ​​wędrującą odpowiedź: zdecydowanie skorzystaj z API (NIH jest oznaką niedojrzałości programisty), ale zawsze rozumiem podstawowe zasady. Mam nadzieję, że to pomoże.

Mike Polen
źródło
2

Sortowanie i wyszukiwanie są niezwykle ważne, bez względu na to, czy jesteś fanem Donalda Knutha, czy chcesz zostać kolejną Larry Page. W zależności od branży, w której prowadzisz działalność, oraz poziomu konkurencji, jaką możesz kierować wśród swoich kandydatów, zalecam uwzględnienie w rozmowie niektórych z poniższych koncepcji.

Sortowanie

  • Szkic pewnego rodzaju algorytmu sortowania.
  • Wymień kilka przykładów algorytmów sortowania.
  • Porównaj / kontrast dwa rodzaje o różnych charakterystykach wydajności.
  • Jeśli nie wspominają o użyciu pamięci, zapytaj o to.

Badawczy

  • Podaj jak najwięcej algorytmów wyszukiwania.
  • Porównaj / kontrast dwa algorytmy wyszukiwania.
  • Naszkicuj dowolne wyszukiwanie inne niż wyszukiwanie liniowe.

Niektórzy mogą powiedzieć, że wymaganie kodu dla tych algorytmów to przesada, chyba że praca jest na bezludnej wyspie bez połączenia z Internetem. Inną kwestią jest to, że jeśli masz 30 minut i chcesz zapytać o cokolwiek innego, dla wielu kandydatów wdrożenie tego typu może zająć sporo czasu.

DeveloperDon
źródło
Kiedyś myślałem, że proszenie ludzi o programowanie wywiadów jest głupie, ale po prostu nie uwierzysz, że liczba osób z pozornie fantastycznymi życiorysami odpowiada na pytania „społeczne” w jaskrawych kolorach, ale którzy przez całe życie nie mogą zanotuj poprawną implementację „strcat” lub innej prostej funkcji. Kilka razy uratowało mnie to od zatrudniania kogoś, kto gdyby nie głupie pytanie o kodowanie, mógłby wywołać niekończący się smutek i pociągnąć zespół z niekompetencją.
Larry Gritz,