Anvendt algoritmik: Ordnung muss sein

På min arbejdsplads hed et af standardspørgsmålene til jobsamtalen for en udvikler: "Nævn tre sorteringsalgoritmer". Hvad er det nu lige, man måler med sådan et spørgsmål? For det første måler man, hvor lang tid siden, det er, kandidaten har gået på universitetet; jeg havde immervæk listen over klassiske sorteringsalgoritmer liggende noget længere fremme på den mentale harddisk kort tid efter mit algoritme-kursus end jeg har i dag. Ja, det er relevant at vide, at der findes flere forskellige sorteringsalgoritmer med forskellig tidskompleksitet, men som Java-udvikler er det endnu ikke overgået mig at have brug for andre former for sortering end de mergesorts og quicksorts, der anvendes i Arrays-biblioteket. Egentlig vil jeg nok nærmere blive bekymret, hvis jeg en dag skulle interviewe en kandidat, som har fundet det nødvendigt at lave sin egen quicksort-implementering! Summa summarum er vi holdt op med at stille det spørgsmål...
 
Men her er et bonusspørgsmål til de af jer, der ikke kom forbi Iforms Kvindeløb på Frederiksberg sidste søndag: Hvad sker der, når man beder 5500 kvinder (hvoraf en promille formentlig har en datalogisk uddannelse) om at sortere sig efter startnummer inden løbets start' Distribueret bubble sort' Nogen stabil algoritme er det i hvert fald ikke.

Kommentarer (17)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Peter Makholm Blogger

Nu har jeg aldrig været til Iforms kvindeløb, men jeg antager at startnumrene er unikke? Så er det vel lidt ligemeget om sorteringsalgoritmen er stabil?

Jeg er enig i at det er lidt ligemeget med bara er kunne rable en ramse ala "mergesort, quicksort, bogosort" af, det relevante opfølgningsspørgsmål ville selvfølgelig være at bede kandidaten om at fortælle lidt om forskellene på algoritmerne.

Det kan nu være rart at kunne se lidt ud over quick- og mergesort. For eksempel hvis man ved at ens inddata altid er næsten sorteret eller næsten bare sorteret omvendt.

  • 0
  • 0
Anne-Sofie Nielsen

Du har ret i, at startnumrene er unikke, og at stabilitet derfor i princippet ikke er et issue.

Det er dog sådan, at man primært inddeles pr. startnummer i grupper af 1000, og at den indbyrdes rækkefølge i gruppen ikke nødvendigvis er bestemt af startnummeret, men mere af hvor langt man synes, man kan tillade sig at møve frem, når man forventer at løbe hurtigere end de fleste... ;-)

Så reelt er det et nemmere problem, da man skal inddeles i et antal buckets, men til gengæld er der et vist element af kaos internt i hver bucket!

  • 0
  • 0
Martin Toft Bay

Jeg deler Palles synspunkt. Hvis man er vant til at kode C, så burde udtrykket ikke volde en problemer. Til gengæld er det grimt og burde gøres med memcpy eller strcpy, alt efter hvilken kontekst man er i (håber ikke jeg laver en bommert her og får klovnehatten på)... og pas nu på de farlige string-funktioner uden længde-parameter. Der findes langt værre C-udtryk :-) Se f.eks. http://www.ioccc.org/ (The International Obfuscated C Code Contest).

  • 0
  • 0
Morten Andersen

Joel-on-software (hvis man ikke kender ham, så er der basis for at "spilde" en hel regnvejrsdag på at læse nogen af hans artikler) har over flere omgange også skrevet artikler om kunsten at holde job-interviews - hans seneste udgave er her: http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html (kan klart anbefales).

Han mener at der bør "kode på bordet" til en samtale, men at man bør skelne klart mellem såkaldte "aha" spørgsmål/brain-teasers, hvor man sandsynligvis kun kender svaret hvis man har set spørgsmålet før, og så mere åbne programmerings spørgsmål, som siger mere om de ønskelige kvaliteter ved programmøren ("smart-and-get-things-done").

Selv har jeg desværre kun oplevet en enkelt samtale hvor der faktisk blev stillet en programmerings-"case" - skide skægt faktisk, og også med til at øge min respekt for virksomhedens seriøsitet, og endelig også med til at forsikre mig om at intervieweren (og firmaet?) faktisk var temmeligt smart (blev afsløret på en hel anden måde under diskussionen om forskellige arkitektur-konstruktioner, end under en "almindelig" hygge-samtale).

  • 0
  • 0
Jesper Laisen

>Til gengæld er det grimt og burde gøres med memcpy eller strcpy, alt efter hvilken kontekst man er i (håber ikke jeg laver en bommert her og får klovnehatten på).

Uanset kontekst skal du nok lade være med at bruge strcpy, som Viega og McGraw i Building Secure Software kalder "very risky".

  • 0
  • 0
Anne-Sofie Nielsen

Jeg vil give Morten helt ret i, at det kan være vældigt underholdende, og ofte også givtigt at læse Joel on Software (selvom han er faldet en del af på den på det seneste; det må være en lektion til os andre om at lukke vores blog ned i tide).

Til gengæld giver han i dette indlæg: http://www.joelonsoftware.com/articles/fog0000000073.html Jabe Blumenthal positiv omtale for at have bedt sine kandidater om at tegne et hus, og dumpe dem, hvis de begynder at tegne uden først at have spurgt ind til en "kravspecifikation" for huset. Jeg mener, at det er en noget enøjet tilgang, hvis ens tilgang til billedkunst forventes at være den samme som til softwareudvikling....

  • 0
  • 0
Anne-Sofie Nielsen

Hej Peter,

Skal dit spørgsmål tages som indledningen til en fornærmelse eller hva'? Eller var det bare fordi jeg har udtrykt mig uklart...

Jeg har haft fornøjelsen af dette kursus: http://www.shb2002.dtu.dk/megetgamlekurser/1999-2000/kurser/it/49142_dk.htm (det var nu ikke Staunstrup der kørte det dengang). Suk, jeg kom i øvrigt til at kigge på URL'en: Jeg hører nu til den årgang, som har haft "megetgamlekurser". :-P

Jeg anfægter absolut ikke værdien i algoritmik-kurser; det er nok et af de absolut mest nyttige kurser, jeg har haft. Detaljerne om de enkelte algoritmer rykker dog alligevel langsomt men sikkert tættere på de evige jagtmarkers "arkiv"-status (sammen med mit fransk), hvorfra de måske en dag, skulle det vise sig nødvendigt, vil genopstå.

  • 0
  • 0
Karsten Nyblad

"Så længe CLRS står i reolen er de jo ikke længere end et greb væk :)"

Du skal stadig vide, at der er en algoritme, der kan løse dit problem, for at du forsøger at slå den op. De forskellige sorteringsalgoritmer har jo forskellige fordele og ulemper, og hvis du tror, at man altid skal quicksort, kan du komme til at bruge den i et tilfælde, hvor den ikke er hensigtsmæssig.

  • 0
  • 0
Rasmus Kaae

Jeg har hørt rygter om at man for et par år siden kunne finde på at stille følgende opgave under et jobinterview hos et spilfirma:

"Skriv en algoritme til at linjetegning og beskriv hvilke specialtilfælde der bør tages højde for."

... Jeg ved ikke med jer men det er sjældent at jeg kan huske f.eks. Bresenhams algoritme udenad og vil da slet ikke stille min krop tilrådighed for et tilsvarende spørgsmål under en jobsamtale.

  • 0
  • 0
Log ind eller Opret konto for at kommentere