Algoritmide ja andmestruktuurioskuste parandamine

Pilt rakendusest Dynamo Primer.

Mõned selle artikli ressursid ilmusid algselt ühes minu kommentaaris redditi postituse kohta, mis sai üsna populaarseks. Siin on algne niit ja allpool on minu uus kirjutis.

Alused

Esimene asi, mida vajate algoritmide ja andmestruktuuride paremaks tundmiseks, on kindel alus. Seda alust saab õppida ühel mitmest viisist, kas ülikoolis arvutiteaduse programmi kaudu, mõned kodeerivad alglaadimislaagrid keskenduvad natuke allpool olevatele teemadele või võite ise õppida raamatutest, videotest või veebiloengutest. Nii et alustamiseks on vaja põhiteadmisi järgmistest teemadest:

Andmestruktuurid

Siit saate teada massiivide, lingitud loendite, binaarsete puude, räsitabelite, graafikute, virnade, järjekordade, hunnikute ja muude põhiliste andmestruktuuride kohta.

Matemaatika ja loogika

Kui soovite algoritmidega silma paista, peate teadma mõnda matemaatilist mõistet mitmest erinevast valdkonnast. Siit saate teada kogumiteooria, piiratud olekute masinate, korrapäraste avaldiste, maatriksi korrutamise, bitituumsete toimingute, lineaarvõrrandite lahendamise, oluliste kombinatoorika mõistete, näiteks permutatsioonide, kombinatsioonide, tuvide augu põhimõtte kohta.

Arvuti arhitektuur

Siit saate teada, kuidas andmed on arvutis esindatud, digitaalse loogika kujundamise põhialused, Boolean algebra, arvuti aritmeetika, ujukoma esitus, vahemälu disain. Proovige veidi õppida C ja Assembly programmeerimisest.

Põhialuste minek edasi

Kui tunnete, et olete enamikust ülalloetletud mõistetest hästi aru saanud, on aeg hakata sukelduma algoritmide ossa. Siin on nimekiri ressurssidest ja asjadest, mida ma tegin, et saada paremini aru olulistest algoritmidest.

Lehed on võetud algoritmi kujundamise juhendist.

Big-O ja Runtime

  • Siit saate teada, mis on Big-O ja kuidas analüüsida algoritmide tööaegu. See on selleteemaline klassikaline raamat (siin on peatükk funktsioonide kasvu kohta).
  • Siin on hea nimekiri veebikursustest, kus õpetatakse algoritme.

Rakendage mõned algoritmid ise

Alustuseks rakendage ise mitu olulist algoritmi ja õppige tundma nende tööaega. Mõned näited:

  • Binaarne otsing
  • Euclid'i algoritm
  • Esimene sügavus ja laius
  • Dijkstra lühim tee
  • Binaarsed puud
  • Sisestuse sort, Mergesort, Quicksort
  • Min ja max hunnikuid
  • Veel näiteid ja loendeid.

Algoritmiraamatud

  • Lugege algoritmi kujundamise juhendit. See on suurepärane raamat ja see on minu lemmik.
  • Algoritmide sissejuhatus on klassikaline raamat, mis hõlmab palju materjali.
  • Programmeerimisintervjuude elemendid sisaldavad palju väljakutseid ja koodilahendusi, mis aitavad teil intervjuudeks valmistuda.

Väljakutsed

  • Harjutage lihtsate ja seejärel keerukamate algoritmide kodeerimist saitidel nagu Coderbyte ja HackerRank, mis pakuvad selgitusi ja lahendusi, nii et saate õppida ka teistelt koodijatelt.
  • Tutvuge interaktiivse pythoni algoritmide veebisaidi väljakutsetega.
  • 10 kõige populaarsemat kodeerimisväljakutse veebisaiti 2017. aastaks.
  • 5 kõige raskemat koodiväljakutset algajatele.

Algoritmide seletused ja intervjuuküsimused

  • Lugege GeeksforGeeksis nii palju algoritmi seletusi ja koodinäiteid. Siin on näide graafi algoritmide hea postituse kohta.
  • Vaadake mõnda CareerCupisse postitatud intervjuuküsimust ja proovige aru saada, kuidas teised kasutajad küsimused lahendasid. Nagu see näide.
  • Lisaks kodeerimise väljakutse saitidele proovige lahendada ka veebis leiduvaid levinumaid kodeerimisega seotud intervjuu küsimusi, näiteks neid, mis on selles loendis.

Dünaamiline programmeerimine

See on väga oluline kontseptsioon, mida peate mõistma, kui soovite algoritme paremini tundma õppida - see on põhjus, miks eraldasin selle teema ülejäänud osadest. Vikipeedia kirjeldus selle kohta on (paksus on minu oma):

Meetod keeruka probleemi lahendamiseks, jagades selle lihtsamate alamprobleemide kogumiks, lahendades kõik need alamprobleemid üks kord ja salvestades nende lahendused. Järgmine kord, kui sama alamprobleem ilmneb, otsib selle lahenduse uuesti arvutamise asemel lihtsalt üles eelnevalt arvutatud lahenduse, säästes sellega arvutamisaega.

Olen näinud dünaamilist programmeerimist mitmetes kodeerimisintervjuudes. Olen näinud ka probleeme, mis nõuavad dünaamilist programmeerimislahendust selliste väljakutsete saitidel nagu LeetCode, Google Code Jam ja mitmed Google Foo Bari väljakutsed nõudsid DP-lahendust.

Ma soovitaksin proovida ja lahendada selles loendis võimalikult palju probleeme. TopCoderil on ka hea õpetus pealkirjaga: Dünaamiline programmeerimine - algajast edasijõudnutele. Paljudel DP-probleemidel on sama struktuur ja mustrid, nii et kui lahendate 3 DP-probleemi iga päev umbes kahe nädala jooksul, on mõne aja pärast võimalik DP-probleemi märgata ja lahendada.

Täpsemad ressursid algoritmides (valikuline)

  • Täpsemad andmestruktuuride loengud Erik Demaine
  • Algoritmilised alajäsemed: lõbus kõvadustõenditega, autor Erik Demaine
  • Konkureeriva programmeerija käsiraamat
  • Programmitööde võistluste autori juhendaja
  • AlgoWiki: konkurentsivõimelisele programmeerimisele pühendatud viki
  • Arvutusliku geomeetria probleemid ja algoritmid (lahedad ja lõbusad, kuid võivad muutuda üsna keeruliseks)
  • NP-täielike probleemide loetelu
  • Avatud andmestruktuuride raamat: jadade, järjekordade, prioriteetsete järjekordade, järjestamata sõnaraamatute, tellitud sõnaraamatute ja graafikute andmestruktuuride rakendamine ja analüüs

Loodetavasti teile meeldis see ressursside loetelu. Harjutage Coderbyte'is kodeerimist ja kommenteerige allpool muid ressursse, mis on teie arvates abiks.