Algoritmien ja tietorakenteen taitojen parantaminen

Kuva Dynamo Primeriltä.

Jotkut tämän artikkelin resursseista esiintyivät alun perin yhdessä kommentissani reddit-viestistä, josta tuli melko suosittu. Tässä on alkuperäinen säie, ja uusi kirjoituksesi on alla.

perusteet

Ensimmäinen asia, jota tarvitset, jos haluat paremmin algoritmeissa ja tietorakenteissa, on vankka perusta. Tämä kanta voidaan oppia monista tavoista, joko yliopiston tietotekniikkaohjelman kautta, jotkut koodaavat käynnistysleirit keskittyvät vähän alla oleviin aiheisiin tai voit oppia omia kirjoja, videoita tai online-luentoja. Joten tarvitset perustiedot seuraavista aiheista aloittamiseksi:

Tietorakenteet

Tutustu taulukkoihin, linkitettyihin luetteloihin, binaaripuihin, tiivistelmätaulukoihin, kaavioihin, pinoihin, jonoihin, kasoihin ja muihin perustietorakenteisiin.

Matematiikka ja logiikka

Sinun on tiedettävä joitain matemaattisia käsitteitä useilta eri alueilta, jos haluat parantaa algoritmeja. Opi joukkoteoriasta, äärellisten tilakoneiden, säännöllisten lausekkeiden, matriisin kertolaskutuksen, bittioperaatioiden, lineaaristen yhtälöiden ratkaisemisen, tärkeiden kombinatoristen käsitteiden, kuten permutaatioiden, yhdistelmien, nivelreikäperiaatteen kanssa.

Tietokonearkkitehtuuri

Opi kuinka data on esitetty tietokoneessa, digitaalisen logiikan suunnittelun perusteet, Boolen algebra, tietokoneen aritmeettinen tieto, liukulukujen esitys, välimuistin suunnittelu. Kokeile ja opi vähän C: n ja Assembly-ohjelmoinnista.

Eteneminen perustajen ohi

Kun sinusta tuntuu, että sinulla on hyvä ymmärrys useimmista yllä luetelluista käsitteistä, on aika aloittaa sukeltaminen algoritmien osaan. Tässä on luettelo resursseista ja asioista, jotka tein parantaakseni tärkeiden algoritmien kirjoittamista ja ymmärtämistä.

Sivut on otettu Algoritmin suunnittelukäsikirjasta.

Big-O & Runtime

  • Opi mitä Big-O on ja kuinka analysoida algoritmien ajoaikoja. Tämä on klassinen kirja aiheesta (tässä on luku toimintojen kasvusta).
  • Tässä on hyvä luettelo algoritmeja opettavista verkkokursseista.

Toteuta joitain algoritmeja itse

Aloita toteuttamalla useita tärkeitä algoritmeja itse ja oppimalla niiden ajoajat. Joitakin esimerkkejä ovat:

  • Binaarihaku
  • Euclidin algoritmi
  • Ensimmäinen syvyys ja leveys
  • Dijkstra on lyhin polku
  • Binaarinen puun kulku
  • Lisäyslajittelu, Mergesort, Quicksort
  • Min ja max kasoja
  • Lisää esimerkkejä ja luetteloita.

Algoritmikirjat

  • Lue algoritmien suunnittelukäsikirja. Se on hieno kirja ja se on suosikkini.
  • Johdatus algoritmeihin on klassinen kirja, joka kattaa paljon materiaalia.
  • Ohjelmointihaastattelujen elementit sisältävät paljon haasteita ja koodiratkaisuja, jotka auttavat sinua valmistautumaan haastatteluihin.

haasteet

  • Harjoittele yksinkertaisten ja sitten edistyneempien algoritmien koodausta sellaisilla sivustoilla kuin Coderbyte ja HackerRank, jotka tarjoavat selityksiä ja ratkaisuja, jotta voit oppia myös muilta koodereilta.
  • Tutustu tämän interaktiivisen python-algoritmien verkkosivuston haasteisiin.
  • Kymmenen suosituinta koodaushaasteverkostoa vuodelle 2017.
  • 5 vaikeinta koodin haastetta aloittelijoille.

Algoritmien selitykset ja haastattelukysymykset

  • Lue niin monta algoritmien selitystä ja koodiesimerkkiä kuin mahdollista GeeksforGeeks-sivustossa. Tässä on esimerkki hyvästä postitusgrafiikkaalgoritmeista.
  • Katso joitain haastattelukysymyksiä, jotka on lähetetty CareerCupiin, ja kokeile ymmärtää, kuinka muut käyttäjät ratkaisivat kysymykset. Kuten tämä esimerkki.
  • Kokeile haastesivustojen lisäksi, kokeile ja ratkaise verkossa löytämiäsi yleisiä koodaushaastattelukysymyksiä, kuten tässä luettelossa olevat.

Dynaaminen ohjelmointi

Tämä erittäin tärkeä käsite, joka sinun on ymmärrettävä, jos haluat paremmin algoritmeihin, mistä syystä erotin tämän aiheen muusta. Wikipedian kuvaus siitä (lihavointi on minun):

Menetelmä monimutkaisen ongelman ratkaisemiseksi jakamalla se kokoelmaan yksinkertaisempia alioikeuksia, ratkaisemalla jokainen näistä alioikeuksista vain kerran ja tallentamalla niiden ratkaisut. Seuraavan kerran, kun sama osa-ongelma esiintyy, sen ratkaisun laskemisen sijasta etsitään yksinkertaisesti aiemmin laskettua ratkaisua, mikä säästää laskenta-aikaa.

Olen nähnyt dynaamisen ohjelmoinnin näkyvän useissa koodaushaastatteluissa. Olen myös nähnyt ongelmia, jotka vaativat dynaamista ohjelmointiratkaisua haastamissivustoilla, kuten LeetCode, Google Code Jam, ja useat Google Foo Barin haasteet vaativat DP-ratkaisun.

Suosittelen, että yrität ratkaista niin monta ongelmaa tässä luettelossa kuin pystyt. TopCoderilla on myös hyvä opetusohjelma, jonka otsikko on: Dynaaminen ohjelmointi - aloittelijasta edistyneeseen. Monilla DP-ongelmilla on sama rakenne ja mallit, joten jos ratkaista 3 DP-ongelmaa päivittäin noin kahden viikon ajan, pystyt jonkin ajan kuluttua havaitsemaan ja ratkaisemaan DP-ongelman ilman ongelmia.

Kehittyneet resurssit algoritmeissa (valinnainen)

  • Kehittyneet tietorakenteet Luennot Erik Demaine
  • Algoritmiset alarajat: hauskaa Erik Demainen kovuusodisteilla
  • Kilpailevan ohjelmoijan käsikirja
  • Ohjaajaoppaan ohjelmointikilpailuihin
  • AlgoWiki: Kilpailevalle ohjelmoinnille omistettu wiki
  • Laskennalliset geometriaongelmat ja algoritmit (siistiä ja hauskaa, mutta voi olla melko vaikeaa)
  • Luettelo NP-täydellisistä ongelmista
  • Avoin tietorakennekirja: sekvenssien, jonojen, prioriteettijonojen, järjestämättömien sanakirjojen, tilattujen sanakirjojen ja kaavioiden tietorakenteiden toteutus ja analyysi

Toivottavasti nautit tästä luettelosta. Harjoittele koodausta Coderbytessä ja kommentoi alla olevia resursseja, joiden mielestäsi olet hyödyllinen.