Forbedring af dine algoritmer og datastrukturfærdigheder

Billede fra Dynamo Primer.

Nogle af ressourcerne i denne artikel kom oprindeligt i en af ​​mine kommentarer til et reddit-indlæg, der blev ret populært. Her er den originale tråd, og min nye opskrivning er nedenfor.

Fundamentals

Den første ting, du har brug for, hvis du vil blive bedre til algoritmer og datastrukturer, er en solid base. Denne base kan læres på en af ​​flere måder, enten gennem et datalogi-program på universitetet, nogle kodning af bootcamps fokuserer lidt på emnerne nedenfor, eller du kan lære på egen hånd fra bøger, videoer eller online-forelæsninger. Så du har brug for en grundlæggende forståelse af følgende emner for at komme i gang:

Datakonstruktioner

Lær om arrays, sammenkoblede lister, binære træer, hash-tabeller, grafer, stabler, køer, dynger og andre grundlæggende datastrukturer.

Matematik & logik

Du skal kende nogle matematiske begreber fra flere forskellige områder, hvis du vil udmærke dig ved algoritmer. Lær om sætteori, finite-state-maskiner, regelmæssige udtryk, matrixmultiplikation, bitvise operationer, løsning af lineære ligninger, vigtige kombinationskoncepter, såsom permutationer, kombinationer, duerhulprincippet.

Computer Arkitektur

Lær, hvordan data er repræsenteret i en computer, det grundlæggende i digital logikdesign, boolsk algebra, computeraritmetik, flydepunktrepræsentation, cache-design. Prøv at lære lidt om programmering af C og forsamling.

At bevæge sig frem forbi de grundlæggende

Når du har lyst til at have en god forståelse af de fleste af de koncepter, der er anført ovenfor, er det tid til at begynde at dykke ned i algoritmens del. Her er en liste over ressourcer og ting, jeg gjorde for at blive bedre til at skrive og forstå vigtige algoritmer.

Sider taget fra Algorithm Design Manual.

Big-O & Runtime

  • Lær, hvad Big-O er, og hvordan man analyserer algoritmernes kørtider. Dette er en klassisk bog om emnet (her er kapitlet om vækst af funktioner).
  • Her er en god liste over onlinekurser, der underviser i algoritmer.

Implementere dig selv nogle algoritmer

Start med at implementere flere vigtige algoritmer selv og lære om deres køretider. Nogle eksempler er:

  • Binær søgning
  • Euclids algoritme
  • Dybde og bredde første søgning
  • Dijkstra's korteste sti
  • Binære træovergange
  • Indsættelsessortering, Mergesort, Quicksort
  • Min & max dynger
  • Flere eksempler og lister.

Algoritmebøger

  • Læs Algorithm Design Manual. Det er en fantastisk bog, og den er min favorit.
  • Introduktion til algoritmer er en klassisk bog, der dækker meget materiale.
  • Elementer af programmeringssamtale indeholder en masse udfordringer og kodeløsninger, der hjælper dig med at forberede dig til interviews.

Udfordringer

  • Øv dig på at kode enkle og derefter mere avancerede algoritmer på websteder som Coderbyte og HackerRank, som giver forklaringer og løsninger, så du også kan lære af andre kodere.
  • Gå igennem udfordringerne på dette interaktive pythonalgoritmerwebsted.
  • De 10 mest populære kodningsudfordringswebsteder for 2017.
  • De 5 sværeste kodeudfordringer for begyndere.

Algoritmer Forklaringer & Interviewspørgsmål

  • Læs så mange algoritme forklaringer og kodeeksempler som du kan på GeeksforGeeks. Her er et eksempel på et godt indlæg på grafalgoritmer.
  • Se på nogle interviewspørgsmål, der er lagt ud på CareerCup, og prøv at forstå, hvordan andre brugere løste spørgsmålene. Som dette eksempel.
  • Udover kodning af udfordringswebsteder, kan du prøve at løse almindelige spørgsmål om kodningssamtaler, som du finder online, såsom dem på denne liste.

Dynamisk programmering

Dette er et meget vigtigt koncept, du bliver nødt til at forstå, hvis du ønsker at blive bedre til algoritmer, hvilket er grunden til, at jeg adskiller dette emne fra resten. Beskrivelsen fra Wikipedia for den er (fed skrift er min):

En metode til at løse et komplekst problem ved at opdele det i en samling af enklere underproblemer, løse hvert af disse underproblemer bare én gang og gemme deres løsninger. Næste gang det samme underproblem opstår, i stedet for at beregne dens løsning, søger man simpelthen den tidligere beregnede løsning op og sparer dermed beregningstid.

Jeg har set dynamisk programmering dukke op i flere kodningsinterviews, jeg har haft. Jeg har også set problemer, der kræver en dynamisk programmeringsløsning på udfordringswebsteder som LeetCode, Google Code Jam og flere udfordringer på Google Foo Bar krævede en DP-løsning.

Jeg vil anbefale at prøve at løse så mange problemer på denne liste, som du kan. Der er også en god tutorial på TopCoder med titlen: Dynamisk programmering - Fra begynder til avanceret. En masse DP-problemer har den samme struktur og mønstre, så hvis du løser 3 DP-problemer hver dag i 2 uger eller deromkring, vil du efter et stykke tid kunne se og løse et DP-problem uden problemer.

Avancerede ressourcer i algoritmer (valgfrit)

  • Avancerede datastrukturer Foredrag af Erik Demaine
  • Algoritmiske nedre grænser: Sjovt med hårdhedsbevis af Erik Demaine
  • Konkurrencedygtig programmerers håndbog
  • The Hitchhiker's Guide to Programming Contests
  • AlgoWiki: En wiki dedikeret til konkurrencedygtig programmering
  • Computational Geometry problems and algorithms (cool og sjovt, men kan blive ret vanskeligt)
  • Liste over NP-komplette problemer
  • Åben datakonstruktionsbog: implementering og analyse af datastrukturer for sekvenser, køer, prioriterede køer, uordnede ordbøger, ordnede ordbøger og grafer

Jeg håber, at du nød denne liste over ressourcer. Du er velkommen til at øve kodning på Coderbyte, og kommenter nedenfor med andre ressourcer, du synes er nyttige.