Som en interviewopgave for softwareudvikler har jeg modtaget opgaven. Jeg har en liste over børn, og opgaven er: sorter børn, der stiger efter deres fødselsdato-tidsstempel, bryder bånd efter ID
Barnets struktur er:
"child": { "id": "14" "name": "John" "birth_date": "1990-12-20T11:50:48Z" } Jeg kan ikke få betydningen af udtrykket “bryde bånd” i den givne kontekst. Jeg antager, at det kan være et af følgende:
- hvis
birth_dateer den samme – først går barn med lavereid - mens du sorterer ved hjælp af
birth_date, skal du ignorere--tegnet.
Kommentarer
- Det ' er sandsynligvis den første mulighed, du gav.
- dette er et engelsksproget spørgsmål
- Som andre har bemærket, er det ' næsten helt sikkert den første fortolkning. Jeg vil bare give et råd, selvom: hvis interviewet gennemføres personligt, eller hvis der ' er en nem måde at kontakte dem på, er du velkommen til at spørge til afklaring lige der og da. Ingen med nogen mening vil holde det imod dig.
Svar
A tie-break er et ekstra spil, når to spillere har det samme antal point for at afgøre, hvem der er vinderen.
Jeg har aldrig hørt dette udtryk i sortering, men at transponere fra tennis til det område betyder det, at alt andet er lige, du laver en ekstra sammenligning af id for at beslutte, hvem der er først.
Vil du tale om en linket liste, vil jeg tøve mere, fordi en tie er også et link eller en forbindelse. Men selv med denne betydning, i din kontekst af sortering, ville den eneste forbindelse, der kunne give mening, være ligestilling.
Kommentarer
- Begrebet " binder " i sortering er bestemt almindeligt nok til at have et nøgleord til det i SQL. " bryde uafgjort " er ikke et teknisk udtryk, men betyder simpelthen at håndtere bånd ved at tage et ekstra trin for at sikre unik placering – ofte et trin, der er falsk eller tilfældigt (som at kaste en mønt for at bestemme en fodboldkamp eller rangordne data efter I d).
- @Steve Tak for denne oplysende bekræftelse. Faktisk refererer SQL TOP WITH TIES til lige værdier. På den anden side ser C ++ bånd meget forskelligt, std :: tie er en gruppe af elementer, der er bundet sammen til en tuple. Den ' bruges også til sortering, men bare for at oprette en leksikografisk rækkefølge mellem elementerne.
Svar
I forbindelse med sortering handler slipsafbrydelse om at sikre en samlet ordre.
Se på eksemplet på dataene:
"id": "14" //made up data "name": "John" //real data "birth_date": "1990-12-20T11:50:48Z" //real data Der er nøjagtigt to stykker reelle data, hvad sker der, hvis der er to personer med identiske navne og fødselsdatoer?
Sorteringsalgoritmen kan ikke afgøre, hvilken der går først, eller endda hvis de i det væsentlige er de samme ting, og det bare skal kasseres på kopi.
Dette er et reelt problem, fordi sortering af to separate kopier af en liste kan resultere i to forskellige rækkefølger, sammenlignet med elementpar (a[0] == b[0] && a[1] == b[1] && ...) ville så resultere i falsk.
Dette er grunden til, at en total ordre er vigtig.
Nu er der ikke mere reelle data at skelne mellem, så hvordan skal vi sikre, at elementerne altid sorteres i samme rækkefølge. svaret er at bryde uafgjort ved hjælp af de sammensatte data. Det er helt vilkårligt, men nu er det ikke vigtigt, hvor ofte listen bliver krypteret og anvendt, den vil altid sortere elementerne i de samme positioner, hvilket muliggør sammenligning ved at sammenligne hvert elementpar.