Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 2 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 5 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 2 weeks
Controls
Register

Jobbintervjuspørsmål

Jeg hadde et jobbintervju i dag, for en toårig jobb som utvikler hos EPCC. Det var ganske spennende, og jeg tror det gikk i alle fall helt greit, skjønt jeg har ikke allverdens erfaring med jobbintervjuer. Dette var vel faktisk mitt andre jobbintervju totalt, der det første var når jeg var 16 år og begynte å jobbe på trelastlageret. Den gangen sa jeg at jeg gikk med avisen, som ble tolket som et tegn på at jeg greide å stå opp tidlig og komme meg på jobb, og muligens førte til at jeg fikk jobben, men i dag slapp jeg ikke fullt så billig unna.

Jeg har naturligvis hørt om intervjuspørsmål, og til og med lest litt om temaet, så jeg var spent på om jeg ville få noe sært som «Hvor mange pianostemmere er det i Storbritannia?» eller «Hvor mye skulle du hatt for å vaske alle vinduene i London?», men jeg fikk noe litt mer håndfast, nemlig et lite programmeringsspørsmål.

Sett at du har en liste med 1000 tilfeldige tall. Hvordan vil du gå frem for å finne de to største?

Først foreslo jeg at man kunne gå gjennom alle tallene en gang, notere seg de to første, og oppdatere hver gang man finner noe som er større. Dette er den raskeste måten regnemessig, siden du bare ser på hvert tall en gang, og det er det minste du kan gjøre. Han spurte om det finnes andre måter, og jeg foreslo et slags binær-søk, men kommenterte at det ville være mindre effektivt, og dessuten mer prakk å programmere. Så spurte han om jeg ikke kunne bruke en ferdig sorteringsfunksjon, og etter at jeg var ferdig med å irritere meg over at jeg ikke kom på det selv sa jeg at det kan man naturligvis, og påpekte at det ville være tregere regnemessig, men til gjengjeld kan det implementeres på to linjer. Til slutt spurte han om jeg kunne skrive ned på tavlen det første programmet jeg beskrev.

Etter litt frem og tilbake kom jeg frem til følgende:
N1 = random_array[0]
N2 = random_array[1]
if N2 > N1:
    N1, N2 = N2, N1

for r in random_array:
    if r > N1:
        N2 = N1
        N1 = r
    else:
        if r > N2:
            N2 = r

Så det som skjer her er at først setter jeg N1 og N2 til de to første tallene i listen. Jeg vil at N1 skal bli det største tallet, og N2 det nest største, så hvis N2 er større bytter jeg plass på dem. Så kjører jeg gjennom hele listen én gang. For hvert tall sjekker jeg om det er større enn N1, og hvis det er større flytter jeg det tallet jeg hadde i N1, som var det største hittil, ned til N2, og putter det nye tallet i N1. Hvis tallet var mindre enn N1 sjekker jeg om det er større enn N2, og hvis det er det putter jeg det i N2.

Jeg har naturligvis programmert løsningen min og sjekket at den funker, og hvis du er veldig ivrig kan du laste ned programmet mitt her og ta en kikk. Og med det føler jeg at jeg har gitt mitt bidrag til jobbintervjuspørsmållitteraturen.

-Tor Nordam
Are, Eivind likes this

Comments

Are,  20.04.12 21:50

Artig! Jeg vet ikke akkurat hva du legger i "tregere regnemessig", men som regel har jo folka som lager innebygde biblioteker mer snøring enn den jevne utvikler og har antakelig utnyttet de tjuvtriks som måtte være for å få ting til å gå fortest mulig. Og ikke minst er koden deres antakelig allerede testet. Så det rette svaret er alltid å bruke eksisterende kode, såfremt den gjør det du trenger og kan antas å være av høy kvalitet.

Blir moro å høre hva tilbakemeldingen på intervjuet blir, da :)
Tor,  20.04.12 22:32

Jeg trodde dere IT-gutter kunne disse tingene, men for all del, jeg kan være mitt ansvar som fysiker, og dermed best, bevisst, og belære deg:

De beste sorteringsalgoritmene er gjennomsnittlig O(n log n), mens den algoritmen jeg beskrev er O(n). Dermed er det beviselig umulig å gjøre det raskere ved å bruke sortering, når det begynner å bli litt størrelse på n. Det spiller ingen rolle hvor mange skitne triks du bruker, forutsatt at alt annet er likt må det ta lengre tid å sortere.

I praksis er det naturligvis noe helt annet. For det første er utviklertid ofte dyrere enn kjøretid, og så lenge man ikke driver med latterlig store lister er begge metodene dessuten omtrent like raske. For det andre, i eksempelet over bruker jeg python, og for-løkker i python er tregt, mens den innebygde sorteringsalgoritmen i python er formodentlig skrevet i C, og er mest sannsynlig raskere.

*** Intermezzo ***

Ok, jeg gjorde en test, og det er mulig jeg tok feil om sorteringen i python. Metoden min er i allefall raskere selv for n = 1000, og den blir enda bedre for større n. Her er en moddet versjon av programmet jeg la ut i går, med timing. Om du er interessert.
Tor,  24.04.12 19:02

Algoritmen min var tydeligvis ikke rask nok for dem. Jeg fikk i alle fall ikke jobben. Det er selvfølgelig irriterende å bli avvist, men jeg kan trøste meg med at den ikke var spesielt godt betalt.

Are,  24.04.12 20:24

Så ikke oppfølgingskommentaren din før nå, Tor :) Poenget mitt var i alle fall ikke fremgangsmåten din ift algoritme, men nettopp, som du kommenterer, at noen antakelig kan det spesifikke programmeringsspråket bedre enn deg og kan optimalisere den biten på et lavere nivå.

Synd du ikke fikk tilbudet, sånn at du eventuelt hadde hatt gleden av å takke nei til det. Eller ja.

Are,  24.04.12 20:25

Dette får meg forresten til å tenke at vi trenger en "send e-post til meg hvis det er aktivitet på en post jeg har kommentert på"-funksjon.
Tor,  24.04.12 20:34

Vi har jo den hendige "hak av her for å få en epost når det er aktivitet på denne posten"-funksjonen. Jeg har vurdert å gjøre denne dobbelt så hendig ved å legge til et frekt lite javascript som sørger for at innstillingen blir oppdatert i det du haker av, slik at du slipper å trykke lagre endringer, men du kunne kanskje tenke deg en global innstilling i profilen din, der du kan velge å automatisk melde deg på epostlisten for en artikkel du har kommentert? Det burde i såfall være en smal sak.

Are,  24.04.12 21:24

Ja, det er akkurat det jeg personlig trenger i alle fall :)
Det er jo naturlig at man er interessert i å følge opp aktivitet som kommer. Men det er definitivt best om man får innholdet i de påfølgende kommentarene med i mailen også, slik at man slipper å åpne en nettleser for å se om man skal hoste opp et svar.

Are,  24.04.12 21:24

(Jeg var forresten ikke klar over at andre enn forfatter hadde tilgang til den funksjonen for en post.)
Tor,  24.04.12 21:25

Du har aldri kastet et blikk på boksen oppe til høyre?

Are,  24.04.12 21:29

Jeg leser som regel enten artikkelen eller en kommentar. Så, nei.
Det illustrerer kanskje at det som er i den boksen burde være mellom artiklene og kommentarene, på en stripe, eller på en tilsvarende stripe mellom nederste kommentar og inputboksen for kommentarer? I alle fall hvis det skal legges merke til.

Så kan man jo argumentere for at det er kjipt å ha for mye stæsj som skiller kommentarer fra artikkel eller inputfelt, men jeg tror jeg hadde foretrukket å ha det et sted der jeg ser det uten å måtte eksplisitt tenke "nå skal jeg lese tags" eller "nå skal jeg sette epostnotification".

Ole Petter,  13.03.13 21:51

Ikke helt det samme, men alikevel:
Jobinterviewquicksort(): http://xkcd.com/1185/
Are likes this
Tor,  23.03.13 00:14

Noen implementerte stacksort: gkoberger.github.com/stacksort/
Are likes this