Som intervjuoppgave for programvareutvikler har jeg fått oppgaven. Jeg har en liste over barn, og oppgaven er: sorter barn som stiger etter fødselsdato-tidsstempelet, bryter bånd etter ID
Barnets struktur er:
"child": { "id": "14" "name": "John" "birth_date": "1990-12-20T11:50:48Z" } Jeg kan ikke få betydningen av uttrykket «bryte bånd» i den gitte konteksten. Jeg antar at det kan være en av følgende:
- hvis
birth_dateer det samme – først går barn med lavereid - mens du sorterer med
birth_date, ignorer--tegnet.
Kommentarer
- Det ' er sannsynligvis det første alternativet du ga.
- dette er et engelskspråklig spørsmål
- Som andre har nevnt, er det ' nesten helt sikkert den første tolkningen. Jeg vil bare gi et råd, skjønt: hvis intervjuet blir gjennomført personlig, eller hvis det ' er en enkel måte å kontakte dem på, er du velkommen til å spørre for avklaring akkurat der og da. Ingen med noen mening vil holde det mot deg.
Svar
A tie-break er et ekstra spill når to spillere har like mange poeng, for å avgjøre hvem som er vinneren.
Jeg har aldri hørt dette uttrykket i sortering, men å transponere fra tennis til det området, betyr det at alt annet er likt, gjør du en ekstra sammenligning av id for å bestemme hvem som er først.
Vil du snakke om en lenket liste, vil jeg nøle mer, fordi et slips er også en lenke eller en forbindelse. Men selv med denne betydningen, i din kontekst av sortering, vil den eneste forbindelsen som kan være fornuftig være den av likhet.
Kommentarer
- Begrepet " binder " i sortering er absolutt vanlig nok til å ha et nøkkelord for det i SQL. " bryte uavgjort " er ikke et teknisk begrep, men betyr ganske enkelt å håndtere bånd ved å ta noen ekstra skritt for å sikre unik rangering – ofte et skritt som er falskt eller tilfeldig (som å kaste en mynt for å bestemme en fotballkamp, eller rangere data etter jeg d).
- @Steve Takk for denne opplysende bekreftelsen. Faktisk refererer SQL TOP WITH TIES til like verdier. På den andre siden ser C ++ bånd veldig annerledes, std :: tie er en gruppe elementer som er koblet sammen til en tuple. Det ' brukes også i sortering, men bare for å lage en leksikografisk rekkefølge mellom elementene.
Svar
I sorteringssammenheng handler det om å sikre en total ordre.
Ta en titt på eksempeldataene:
"id": "14" //made up data "name": "John" //real data "birth_date": "1990-12-20T11:50:48Z" //real data Det er nøyaktig to virkelige data, hva skjer hvis det er to personer med identiske navn og fødselsdatoer?
Sorteringsalgoritmen kan ikke bestemme hvilken som går først, eller til og med om de egentlig er de samme tingene, og den bare skal kastes på kopi. elementpar (a[0] == b[0] && a[1] == b[1] && ...) vil da resultere i falsk.
Dette er grunnen til at en total ordre er viktig.
Nå er det ikke mer reelle data å skille mellom, så hvordan skal vi sikre at elementene alltid blir sortert i samme rekkefølge. svaret er å bryte uavgjort ved å bruke de sammensatte dataene. Det er helt vilkårlig, men nå, uansett hvor ofte listen blir kryptert og brukt, den vil alltid sortere elementene i de samme posisjonene, slik at sammenligning kan gjøres ved å sammenligne hvert elementpar.