Ursprünglich habe ich dies als eine kurze To-do Liste von Studienthemen angefangen, um Softwareingenieur zu werden, aber es ist zu der riesigen Liste herangewachsen, die man heute sehen kann. Nachdem ich diesen Lehrplan durchgezogen habe, wurde ich als Software Entwickler bei Amazon eingestellt! Wahrscheinlich wirst du nicht so viel lernen müssen wie ich. Aber egal, alles was man braucht, findest man hier.
Ich habe ungefähr 8-12 Stunden am Tag gelernt, und das für mehrere Monate. Hier ist meine Geschichte: Why I studied full-time for 8 months for a Google interview
Die Einträge in dieser Liste werden dich gut auf ein Vorstellungsgespräch bei so gut wie jeder Software Firma vorbereiten, so bei den Giganten: Amazon, Facebook, Google oder Microsoft.
Viel Glück!
Übersetzungen:
Übersetzungen in Bearbeitung:
Das ist mein mehrmonatiger Lehrplan um sich vom Web Developer (Selbststudium, kein Abschluss in Informatik) zum Softwareingenieur bei einer großen Firma zu entwickeln.
Dies ist gedacht für neue Softwareingenieure oder solche die von der Software/Web Entwicklung zum Software Engineering wechseln wollen (wobei Informatikkenntnisse benötigt werden). Falls man behauptet mehrere Jahre an Erfahrung als Softwareingenieur zu haben, erwartet einen ein hartes Vorstellungsgespräch.
Falls du schon mehrere Jahre Erfahrung in der Software/Webentwicklung hast, muss dir klar sein, dass große Software Unternehmen wie Google, Amazon, Facebook oder Microsoft Software Engineering und Software Entwicklung als unterschiedliche Dinge ansehen, und sie setzen Informatikkenntnisse voraus.
Falls du ein Reliability Engineer oder Operations Engineer werden möchtest, solltest du dir besonders die optionale Liste (Netzwerke, Sicherheit) ansehen.
- Worum es geht
- Warum solltest du das hier lesen?
- Wie man dies hier benutzt
- Halt dich nicht für dümmer als du bist
- Über Videoquellen
- Ablauf von Vorstellungsgesprächen und allgemeine Vorbereitung darauf
- Wähle eine Sprache für das Vorstellungsgespräch
- Literaturliste
- Bevor du anfängst
- Was hier nicht behandelt wird
- Voraussetzungen
- Der Tagesplan
- Algorithmische Komplexität / Big-O (Groß-O Notation) / Asymptotische Analyse
- Datenstrukturen
- Mehr
- Trees (Bäume)
- Trees - Notizen und Hintergrund
- Binärer Suchbaum
- Heap / Vorrangwarteschlange / Binärer Heap
- balancierte Suchbäume (allgemeines Konzept, keine Details)
- Traversierung: preorder, inorder, postorder, Breitensuche, Tiefensuche
- Sortierung
- Auswahl
- Insertion Sort
- Heap Sort
- Quick Sort
- Merge Sort
- Graphen
- gerichtet
- ungerichtet
- Adjazenzmatrix
- Adjazenzliste
- Traversierung: Breitensuche, Tiefensuche
- Noch mehr
- Rekursion
- Dynamische Programmierung
- Objektorientierte Programmierung
- Design Patterns (Entwurfsmuster)
- Kombinatorik (n über k) und Wahrscheinlichkeiten
- NP, NP-Vollständig und Heuristiken
- Caches
- Prozesse und Threads
- Testen
- Scheduling
- Stringsuche und -manipulationen
- Tries (Präfixbäume)
- Fließkommazahlen
- Unicode
- Endianness (Byte-Reihenfolge)
- Netzwerke
- Systementwurf, Skalierbarkeit, Datenverarbeitung (wenn du 4+ Jahre erfahrung hast)
- Finaler Rückblick
- Übungen zu Programmieraufgaben
- Programmieraufgaben/Wettbewerbe
- Wenn das Vorstellungsgespräch bald ansteht
- Dein Lebenslauf
- Denk dran wenn das Vorstellungsgespräch kommt
- Stell Fragen an den Interviewer
- Wenn du den Job bekommst
---------------- Alles unter der Linie ist optional ----------------
Zusätzliche Materialien
- Zusätzliche Bücher
- Zusätzliches Wissen
- Compiler (Übersetzer)
- Emacs und vi(m)
- Unix Kommandozeilenwerkzeuge
- Informationstheorie
- Parität und Hamming Code
- Entropie
- Kryptographie
- Kompression
- Sicherheit
- Garbage collection (automatische Speicherbereinigung)
- Parallelisierung
- Messaging, Serialisierung und Queueing Systeme
- A*
- Fast Fourier Transform
- Bloom Filter
- HyperLogLog
- Locality-Sensitive Hashing
- van Emde Boas Trees
- Augmentierte Datenstrukturen
- Balanced search trees (Balancierte Suchbäume)
- AVL Bäume
- Splay Bäume
- Rot-Schwarz-Bäume
- 2-3 Bäume
- 2-3-4 Bäume (aka 2,4 Bäume)
- N-fache (K-fache, M-fache) Bäume
- B-Bäume
- k-D Bäume
- Skip Listen
- Netzwerkflüsse
- Disjunkte Mengen & Union Find
- Mathematik für schnelle Berechnungen
- Treap
- Lineare Programmierung
- Geometrie, Konvexe Hülle
- Diskrete Mathematik
- Machine Learning (maschinelles Lernen)
- Weitere Details zu ausgewählten Themen
- Videoreihen
- Infomatikkurse
- Paper (Wissenschaftliche Veröffentlichtungen)
Als ich dieses Projekt angefangen habe, konnte ich einen Stack nicht von einem Heap unterscheiden, wusste nichts von Groß-O, nichts über Bäume, oder wie man einen Graphen durchläuft. Wenn ich einen Sortieralgorithmus hätte schreiben sollen, dann wäre der nicht besonders gut geworden, so viel kann ich dir sagen. Jede Datenstruktur die jemals benutzt habe war direkt in der Programmiersprache eingebaut, und ich hatte keine Ahnung wie sie funktioniert haben. Ich muss niemals Speichermanagement betreiben, außer einer der Prozesse, die ich ausgeführt hatte hat einen "out of memory" Fehler gehabt. Und wenn das passiert ist, musste ich einen Umweg finden. Ich habe ein paar mehrdimensionale Arrays in meinen Leben benutzt und ein paar Tausend assoziative Arrays, aber ich habe nie selbst eine Datenstruktur von Grund auf neu geschrieben.
Es ist ein großer Plan. Es könnte mehrere Monate dauern. Falls dir schon vieles von dem bekannt ist, wird es dich viel weniger Zeit kosten.
Wie man dies hier benutzt
Alles hier drunter ist ein Umriss, und du solltest die Aufgaben von oben nach untern abarbeiten.
Ich benutze GitHub's spezielle Version von Markdown, das beinhält Aufgabenliste, um den Fortschritt zu prüfen.
Erstelle einen neuen Branch. Damit du Einträge abhaken kannst, füge einfach nur ein x in eckigen Klammern ein: [x]
Erstelle einen Fork dieses Projekts und gib die folgenden Kommandos ein
git checkout -b progress
git remote add jwasham https://github.com/jwasham/coding-interview-university
git fetch --all
Hake alle Kästchen mit x ab, nachdem du die Änderungen vollzogen hast
git add .
git commit -m "Marked x"
git rebase jwasham/main
git push --force
- Erfolgreiche Softwareingenieure sind klug, aber viele sind sich unsicher, ob sie klug genug sind.
- The myth of the Genius Programmer
- It's Dangerous to Go Alone: Battling the Invisible Monsters in Tech
- Believe you can change
- Think you're not smart enough to work at Google? Well, think again
Auf manche Videos kann man nur zugreifen, indem man sich bei einem Coursera- oder EdX-Kurs einschreibt. Das sind so genannte MOOCS. Manchmal werden die Kurse gerade nicht angeboten und man muss ein paar Monate warten. Man hat dann keinen Zugriff darauf.
Ich würde mich sehr freuen, wenn du mir dabei hilfst kostenlose und immer verfügbare öffentliche Quellen hinzuzufügen,
wie z.B. YouTube Videos, um die Online Kurse zu ergänzen.
Ich benutze gerne Vorlesungen von Hochschulen.
Ablauf von Vorstellungsgesprächen und allgemeine Vorbereitung darauf
-
Cracking The Coding Interview Teil 1:
-
Wie man einen Job bei den Großen 4 bekommt:
-
Vorbereitungskurse:
- Software Engineer Interview Unleashed (kostenpflichtiger Kurs):
- Hier lernt von einem ehemaligen Google Interviewer wie man sich auf ein Vorstellungsgespräch als Software Engineer vorbereitet.
- Python for Data Structures, Algorithms, and Interviews! (kostenpflichtiger Kurs):
- Ein auf Python zugeschnittener Kurs welcher Datenstrukturen, Algorithmen, Testinterviews und noch viel mehr behandelt.
- Intro to Data Structures and Algorithms using Python! (kostenloser Kurs auf Udacity):
- Ein kostenloser auf Python zentrierter Kurs über Datenstrukturen und Algorithmen.
- Data Structures and Algorithms Nanodegree! (kostenpflichtiges Nandegree Kurs auf Udacity):
- Hol dir praktische Erfahrungen im Umgang mit über 100 Datenstrukturen und Algorithmen unter der Führung eines engagierten Mentors der dir dabei hilft dich auf Vorstellungsgespräche und Beispiele aus den Berufsleben vorzubereiten.
- Software Engineer Interview Unleashed (kostenpflichtiger Kurs):
Man sollte eine Sprache wählen mit der man sich wohlfühlt beim Codingteil des Vorstellungsgesprächs. Aber für große Firmen sind das valide Optionen:
- C++
- Java
- Python
Man könnte auch diese verwenden, aber pass auf. Es könnte einige Vorbehalte geben:
- JavaScript
- Ruby
Hier ist ein Artikel den ich über die Auswahl der Programmiersprache für das Vorstellungsgespräch geschrieben habe: Pick One Language for the Coding Interview
Du musst dich mit der Sprache wohlfühlen und auskennen.
Hier kannst du mehr über die Wahl lesen:
- http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
- http://blog.codingforinterviews.com/best-programming-language-jobs/
Unten sind ein paar Materialien zu C, C++ und Python zu finden, weil ich das gerade lerne. Es gehören einige Bücher dazu, siehe unten.
Die Liste ist kürzer als die, die ich tatsächlich benutzt habe. Ich habe es etwas abgekürzt, um euch Zeit zu sparen.
- Programming Interviews Exposed: Coding Your Way Through the Interview, 4nd Edition
- Antworten in C++ und Java
- eine gute Aufwärmübung für Cracking the Coding Interview
- nicht allzu schwer, die meisten Probleme sind einfacher als das, was ihr in Vorstellungsgesprächen sehen werdet (von dem, was ich so gelesen habe)
- Cracking the Coding Interview, 6th Edition
- Antworten in Java
Wenn man extrem viel Zeit hat:
Such dir eins aus:
- Elements of Programming Interviews (C++ version)
- Elements of Programming Interviews (Java version)
- Write Great Code: Volume 1: Understanding the Machine
-
Das Buch wurde 2004 veröffentlicht und ist etwas veraltet, aber es ist eine hervorragende Quelle, um Computer in Kürze zu verstehen.
-
Der Autor hat HLA erfunden, also sollte man die Erwähnungen und Beispiele in HLA mit Vorsicht genießen. Nicht weit verbreitet, aber ein nettes Beispiel wie Assembly Code aussehen kann.
-
Diese Kapitel sind es wert zu lesen um euch eine gute Grundlage zu geben:
......
- Kapitel 2 - Numeric Representation
- Kapitel 3 - Binary Arithmetic and Bit Operations
- Kapitel 4 - Floating-Point Representation
- Kapitel 5 - Character Representation
- Kapitel 6 - Memory Organization and Access
- Kapitel 7 - Composite Data Types and Memory Objects
- Kapitel 9 - CPU Architecture
- Kapitel 10 - Instruction Set Architecture
- Kapitel 11 - Memory Architecture and Organization
-
Man muss sich für das Vorstellungsgespräch für eine Programmiersprache entschieden haben (siehe oben).
Hier sind meine Empfehlungen geordnet nach Sprache. Ich habe nicht für alle Sprachen Material. Ich begrüße Ergänzungen.
Wenn du dich durch eins davon durchgelesen hast, solltest du genügende Wissen über Datenstrukturen und Algorithmen haben, um Coding Probleme lösen zu können. Man kann alle Videolektionen in diesem Projekt überspringen, außer du willst eine Auffrischung.
Zusätzliches sprachspezifisches Material hier.
C++
Ich habe diese beiden zwar nicht gelesen, aber sie sind gut bewertet und von Sedgewick geschrieben. Er ist super.
- Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching
- Algorithms in C++ Part 5: Graph Algorithms
Wenn du eine bessere Empfehlung für C++ hast, bitte lass es mich wissen. Ich suche nach umfassenden Material.
Java
- Algorithms (Sedgewick und Wayne)
- Videos mit Buchinhalt (und Sedgewick!) auf Coursera:
ODER:
- Data Structures and Algorithms in Java
- von Goodrich, Tamassia, Goldwasser
- wird bei der UC Berkeley als Zusatzmaterial für den Informatik Einstieg benutzt
- siehe Zusammenfassung zur Python Version, dieses Buch behandelt dieselben Themen.
Python
- Data Structures and Algorithms in Python
- von Goodrich, Tamassia, Goldwasser
- Ich habe dieses Buch geliebt. Es hat alles behandelt und mehr.
- Python-hafter Code
- meine feurige Rezension: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/
Diese Liste ist über mehrere Monate gewachsen. Und ja, sie ist etwas aus dem Ruder gelaufen.
Hier einige Fehler die ich gemacht habe, damit ihr ein besseres Erlebnis haben könnt.
Ich habe stundenlang Videos gesehen und reichlich Notizen geschrieben. Monate später gab es viel, an das ich mich nicht mehr erinnern konnte. Ich habe 3 Tage damit verbracht meine Notizen durchzugehen und daraus Lernkarten zu erstellen, damit ich alles noch mal wiederholen konnte.
Bitte lesen damit ihr nicht meine Fehler wiederholt:
Retaining Computer Science Knowledge
Um das Problem zu lösen, habe ich eine kleine Webseite erstellt, wo ich 2 Arten von Lernkarten anlegen kann: Allgemein und Code. Jede Karte hat ihr eigenes Format.
Ich habe eine mobile-first Webseite gemacht, damit ich auf meinen Smartphone oder Tablet lernen kann, egal wo ich mich befinde.
Erstell kostenlos deine eigenen Lernkarten:
- Lernkarten-Webseiten Repo
- Meine Lernkarten Databank (alt - 1200 Karten):
- Meine Lernkarten Databank (neu - 1800 Karten):
Achtung, ich habe es übertrieben und Lernkarten über alles erstellt, von Assembly und Python Trivia bis hin zu Machine Learning und Statistik. Das ist viel mehr als eigentlich notwendig.
Anmerkung zu Lernkarten: Wenn man sich einmal an eine Antwort erinnert, sollte man das nicht als Wissen ansehen. Man muss sich die Karte mehrmals ansehen und richtig beantworten, bevor man es tatsächlich weiß. Wiederholung wird das Wissen tiefer in euren Verstand verankern.
Eine Alternative zu Lernkarten ist Anki, was mir schon öfters empfohlen wurde. Es benutzt ein Erinnerungssystem um einen dabei zu helfen sich zu erinnern. Es ist benutzerfreundlich, auf allen Plattformen erhältlich und kann sich mit der Cloud synchronisieren. Es kostet 25$ auf iOS, aber es ist kostenlos für andere Plattformen.
Meine Lernkarten Sammlung im Anki Format: https://ankiweb.net/shared/info/25173560 (Danke @xiewenya)
Ich behalte eine Reihe von Spickzetteln über ASCII, OSI Stack, Groß-O Notation, und mehr. Ich lerne sie in meiner Freizeit.
Nimm dir eine Pause vom Programmieren für eine halbe Stunde und gehe deine Lernkarten durch.
Es gibt eine Menge Ablenkungen, die deine kostbare Zeit stehlen können. Fokussiert und konzentriert zu bleiben ist schwer.
Das sind weitverbreitete Technologien aber nicht Teil des Lehrplans:
- SQL
- Javascript
- HTML, CSS, und andere Front-end Technologien
Einige der Themen brauchen einen Tag, für andere braucht man mehrere Tage. Manche sind reines Lernen ohne das man was implementiert.
Jeden Tag nehme ich mir ein Thema aus der Liste unten vor, schaue Videos über das Thema, und schreibe eine Implementierung in:
- C - mit structs und Funktionen die ein struct Pointer und und etwas anderes als Argumente benutzen.
- C++ - ohne vorgefertigte Typen
- C++ - mit vorgefertigte Typen, wie STL's std::list für verkettete Listen
- Python - mit vorgefertigte Typen (um Python weiterhin zu üben)
- und ich schreibe Tests um sicherzugehen, dass ich richtig liege, manchmal sind das nur einfache assert() Statements
- Du könntest auch Java oder etwas anderes machen. Das ist nur das, was ich tue.
Man braucht nicht alles davon. Man braucht nur eine Sprache für das Vorstellungsgespräch.
Warum ich in all diesen Sprachen programmiere?
- Üben, üben, üben, bis ich kotzen muss und es im Schlaf beherrsche (manche Probleme haben viele Sonderfälle und Wissen, an das man sich erinnern muss)
- Unter erschwerten Voraussetzungen arbeiten können (Speicher allokieren/freigeben ohne die Hilfe einer Garbage Collection (Ausnahmen sind Python oder Java))
- Vorgefertigte Typen verwenden damit ich Erfahrung im Umgang für echte Anwendungsfälle haben (ich werde sich meine eigene verkettete Liste im Alltag implementieren)
Vielleicht habe ich nicht die Zeit, um das alles für jedes Thema zu machen, aber ich werde es versuchen.
Man findet meinen Code hier:
Man muss sich nicht bei jeden Algorithmus an alle Details erinnern können.
Schreib Code auf einer Tafel oder auf Papier, aber nicht am Computer. Teste mit ein paar einfachen Eingaben. Dann kannst du es am Computer testen.
Voraussetzungen
-
Lerne C
- C ist überall. Du wirst Beispiele in Büchern, Vorlesungen, Videos, und generell überall finden, während du lernst.
- C Programming Language, Vol 2
- Das ist ein kurzes Buch, aber es wird dich viel über die C Sprache lehren und wenn du ein bisschen übst, wirst du schnell darin bewandert sein. C zu verstehen, hilft dir zu verstehen, wie Programme und Speicher funktionieren.
- Antworten auf Fragen
-
Wie Computer einen Prozess ausführen:
Algorithmische Komplexität / Big-O (Groß-O Notation) / Asymptotische Analyse
- nichts zum Implementieren
- Es sind eine Menge Videos hier aufgelistet. Schau dir einfach so viele an, bis du es verstanden hast. Man kann immer wieder zurückgehen und noch mal anschauen.
- Falls einige der Vorträge zu mathematisch sind, kann man ans untere Ende springen und sich Videos über diskrete Mathematik anschauen, um das notwendige Hintergrundwissen zu bekommen.
- Harvard CS50 - Asymptotic Notation (video)
- Big O Notations (kleines Tutorial) (video)
- Big O Notation (and Omega and Theta) - beste mathematische Erklärung (video)
- Skiena:
- A Gentle Introduction to Algorithm Complexity Analysis
- Orders of Growth (video)
- Asymptotics (video)
- UC Berkeley Big O (video)
- UC Berkeley Big Omega (video)
- Amortized Analysis (video)
- Illustrating "Big O" (video)
- TopCoder (beinhält Differenzgleichungen und Master-Theorem)
- Spickzettel
Datenstrukturen
-
- implementiere einen automatisch mitwachsenden Vektor
- Beschreibung:
- Arrays (video)
- UC Berkeley CS61B - Linear and Multi-Dim Arrays (video) (Start watching from 15m 32s)
- Dynamic Arrays (video)
- Jagged Arrays (video)
- Implementiere ein Vektor (veränderbares Array, das automatisch seine Größe verändert):
- Übe Arrays und Pointer (Zeiger) zu coden, und benutze Pointerberechnung, um ein Element aus einem Array auszuwählen statt den Index zu benutzen.
- neues Rohdaten-Array mit allokierten Speicher
- man kann intern ein int Array dafür verwenden, aber nicht die Features davon
- fang an mit der Größe 16, oder wenn die Startnummer schön größer ist, benutze Zweier-Potenzen - 16, 32, 64, 128
- size() - Anzahl der Elemente
- capacity() - Anzahl der Elemente die es enthalten kann
- is_empty()
- at(index) - gibt das Element an der gegebenen Index zurück, explodiert wenn der Index außerhalb der Grenzen ist
- push(item)
- insert(index, item) - fügt ein Element an der Index-Position ein, schiebt den ursprünglichen Wert vom Index und alle nachfolgenden Elemente eins nach rechts weiter
- prepend(item) - ist dasselbe wie oben mit Index 0
- pop() - entfernt das letzte Element und gibt dessen Wert zurück
- delete(index) - lösche das Element an der Indexposition und verschiebe jedes Element danach eins nach links
- remove(item) - sucht den Wert und entfernt den Index, der ihn enthält (auch wenn es mehrere Stellen sind)
- find(item) - sucht den Wert und gibt den ersten Index mit diesen Wert, -1 wenn der Wert nicht gefunden wird
- resize(new_capacity) // private Funktion
- wenn man die Kapazität erreicht hat, verdopple die Kapazität
- wenn du ein Element löscht und die Größe ist nur 1/4 der Kapazität, halbiere die Kapazität
- Zeit
- O(1) um am Ende etwas hinzuzufügen/zu löschen (amortisiert bei Verwendung von zusätzlichen Speicher), Indexzugriff, oder update
- O(n) um an eine andere Stelle hinzuzufügen oder zu löschen
- Speicher
- zusammenhängend im Speicher, Nähe hilft der Performance
- benötigter Speicher = (Array Kapazität, welche >= n ist) * Größe eines Elements, aber selbst bei 2n, immer noch O(n)
-
- Erklärung:
- C Code (video) - nicht das ganze Video nur die Teile über Knotenstruktur und Speicherverwaltung.
- Linked Lists vs Arrays:
- why you should avoid linked lists (video)
- Achtung: du brauchst Wissen über Pointer auf Pointer: (für den Fall, dass man einen Pointer an eine Funktion übergibt und die Funktion die Adresse verändern kann, zu der der Pointer zeigt) Diese Seite ist dafür Pointer auf Pointer grob zu verstehen. Ich würde diese Art der Listentraversierung nicht empfehlen. Lesbarkeit und Wartbarkeit leiden darunter wenn man versucht clever zu sein.
- Implementierung (ich habe es mit Tail-Pointern gemacht und ohne):
- size() - gibt Anzahl der Datenelemente in der Liste zurück
- empty() - bool gibt true zurück wenn leer
- value_at(index) - gibt den Wert an der Stelle index zurück (angefangen bei 0 für das erste Element)
- push_front(value) - fügt ein Element an den Anfang der List ein
- pop_front() - löscht das erste Element und gibt dessen Wert zurück
- push_back(value) - fügt ein Element ans Ende ein
- pop_back() - löscht das letzte Element und gibt dessen Wert zurück
- front() - hole den Wert des ersten Elements
- back() - hole den Wert des letzten Elements
- insert(index, value) - fügt Wert an der Indexposition ein, das neue Element an der Stelle zeigt auf das aktuelle Element an der Stelle
- erase(index) - löscht das Element an der gegebenen Stelle
- value_n_from_end(n) - gibt den Wert an der n-ten Position von hinten zurück
- reverse() - kehrt die Liste um
- remove_value(value) - entfernt das erste Element aus der Liste mit diesen Wert
- Doubly-linked List (doppelt verkettete Listen)
- Erklärung (Video)
- gibt keinen Grund das zu implementieren
-
- Stacks (video)
- Werde ich nicht implementieren. Implementierung mittels Array ist trivial.
-
- Queue (video)
- Circular buffer/FIFO
- Implementierung mittels verketteten Listen, mit Tail-Pointer:
- enqueue(value) - fügt Wert am Ende ein
- dequeue() - gibt das älteste Element (am Anfang der Liste) zurück und löscht es
- empty()
- Implementierung mittels Arrays fester Größe:
- enqueue(value) - fügt ein Element am Ende des verfügbaren Speicherplatzes ein
- dequeue() - gibt das älteste Element zurück und löscht es
- empty()
- full()
- Kosten:
- eine schlechte Implementierung wo man am Kopf einreiht und am Schwanz ausreiht wäre O(n) weil man das vorletzte Element braucht, wodurch man die Liste komplett durchgehen muss
- enqueue: O(1) (amortisiert, verkettete Liste und Array)
- dequeue: O(1) (verkettete Liste und Array)
- empty: O(1) (verkettete Liste und Array)
-
-
Videos:
-
Online Kurse:
-
Implementierung mit Array und linear probing
- hash(k, m) - m ist die Größe der Hash-Tabelle
- add(key, value) - falls key schon existiert, wird Wert überschrieben
- exists(key)
- get(key)
- remove(key)
-
Mehr
-
- Binary Search (video)
- Binary Search (video)
- Details
- Implementierung:
- Binärsuche (auf einem sortierten Array von Ganzzahlen)
- Binärsuche mittels Rekursion
-
- Bits Spickzettel - man sollte viele der Zweierpotenzen kennen (von 2^1 über 2^16 und 2^32)
- Erhalte sehr gutes Verständnis Bits zu manipulieren mit: &, |, ^, ~, >>, <<
- Zweier- und Einerkomplement
- Bits zählen
- zur nächsten Zweierpotenz aufrunden:
- Werte tauschen:
- Absolutwert:
Trees (Bäume)
-
- Series: Trees (video)
- generell Baumerstellung
- Traversieren (Durchlaufen)
- Algorithmen zur Manipulation
- BFS(breadth-first search) and DFS(depth-first search) (video)
- BFS (Breitensuche) Bemerkungen:
- Ebenenreihenfolge (BFS, mittels Queue)
- Zeitkomplexität: O(n)
- Speicherkomplexität: beste: O(1), schlechteste: O(n/2)=O(n)
- DFS (Tiefensuche) Bemerkungen:
- Zeitkomplexität: O(n)
- Speicherkomplexität: beste: O(log n) - durchschnittliche Höhe eines Baumes schlechteste: O(n)
- inorder (DFS: links, selber, rechts)
- postorder (DFS: links, rechts, selber)
- preorder (DFS: selber, links, rechts)
- BFS (Breitensuche) Bemerkungen:
-
- Binary Search Tree Review (video)
- Series (video)
- startet mit Symboltabelle und geht durch die Anwendungsgebiete für BST
- Introduction (video)
- MIT (video)
- C/C++:
- Binary search tree - Implementation in C/C++ (video)
- BST implementation - memory allocation in stack and heap (video)
- Find min and max element in a binary search tree (video)
- Find height of a binary tree (video)
- Binary tree traversal - breadth-first and depth-first strategies (video)
- Binary tree: Level Order Traversal (video)
- Binary tree traversal: Preorder, Inorder, Postorder (video)
- Check if a binary tree is binary search tree or not (video)
- Delete a node from Binary Search Tree (video)
- Inorder Successor in a binary search tree (video)
- Implement:
- insert // füge Wert in Baum ein
- get_node_count // gibt Anzahl gespeicherter Werte zurück
- print_values // gibt die Werte im Baum aus, vom Minimum zum Maximum
- delete_tree
- is_in_tree // gibt true zurück wenn der gegebene Wert im Baum vorkommt
- get_height // gibt die Höhe in Knoten zurück (Höhe eines einzelnen Knotens ist 1)
- get_min // gibt den kleinsten Wert zurück der im Baum gespeichert ist
- get_max // gibt den größten Wert zurück der im Baum gespeichert ist
- is_binary_search_tree
- delete_value
- get_successor // gibt vom gegebenen Wert den nächstgrößeren Wert im Baum zurück, -1 wenn der nicht existiert
-
- visualisiert als Baum, aber wächst üblicherweise linear im Speicher (Array, Linked List)
- Heap
- Introduction (video)
- Naive Implementations (video)
- Binary Trees (video)
- Tree Height Remark (video)
- Basic Operations (video)
- Complete Binary Trees (video)
- Pseudocode (video)
- Heap Sort - jumps to start (video)
- Heap Sort (video)
- Building a heap (video)
- MIT: Heaps and Heap Sort (video)
- CS 61B Lecture 24: Priority Queues (video)
- Linear Time BuildHeap (max-heap)
- Implementierung eines Max-Heap:
- insert
- sift_up - gebraucht fürs Einfügen
- get_max - gibt den größten Wert zurück, ohne ihn zu löschen
- get_size() - gibt Anzahl gespeicherter Element zurück
- is_empty() - gibt true zurück wenn der Heap keine Elemente enthält
- extract_max - gibt das Max-Element zurück, löscht es
- sift_down - gebraucht für extract_max
- remove(i) - entfernt Element an Position i
- heapify - erstellt einen Heap aus einem Array, gebraucht für heap_sort
- heap_sort() - nimmt ein unsortiertes Array und verwandelt es in ein sortiertes Array (in-place) mittles Max Heap
- Bemerkung: stattdessen einen Min Heap zu verwenden, würde weniger Operationen brauchen, aber den Speicherbedarf verdoppeln (kann man nicht in-place machen).
Sortierung
-
Bemerkungen:
- Implementiere Sortierungen und kenne best case/worst case, durchschnittliche Komplexität von jeden:
- kein Bubble Sort - es ist furchtbar - O(n^2), außer wenn n <= 16
- Stabilität in Sortieralgorithmen ("Ist Quicksort stabil?")
- Welche Algorithmen können mit verketteten Listen genutzt werden? Welche mit Arrays? Welche bei beiden?
- Ich würde nicht empfehlen, verkettete Listen zu sortieren, aber Mergesort ist machbar.
- Merge Sort For Linked List
- Implementiere Sortierungen und kenne best case/worst case, durchschnittliche Komplexität von jeden:
-
Für Heap Sort, siehe Heap Datenstruktur oben. Heap Sort ist toll, aber nicht stabil.
-
UC Berkeley:
-
Mergesort Code:
-
Quicksort Code:
-
Implementierung:
- Mergesort: O(n log n) Durchschnitt und worst case
- Quicksort O(n log n) Durchschnitt
- Selection Sort und Insertion Ssort sind beide O(n^2) im Durchschnitt und worst case
- Für Heap Sort, siehe Heap Datenstruktur oben.
-
Nicht vorgeschrieben, aber würde ich empfehlen:
Als Zusammenfassung ist hier eine grafische Darstellung von 15 Sortieralgorithmen. Falls du noch mehr zu dem Thema wissen willst, schau dir "Sortierung" unter Weitere Details für ausgewählte Themen an
Graphen
Graphen können genutzt werden, um damit viele verschiedene Probleme in der Informatik darzustellen. Deswegen ist dieser Abschnitt so lang wie Bäume und Sortierung.
-
Bemerkungen:
- Es gibt 4 verschiedene Arten einen Graphen im Speicher zu repräsentieren:
- Objekte und Pointer
- Adjazenzmatrix
- Adjazenzliste
- adjacency map
- bekanntmachen mit jeder dieser Repräsentationen und ihrer Vor- und Nachteile
- BFS und DFS - kenne Komplexität, ihre Kompromisse, und wie man sie mit echten Code umsetzt
- Wenn eine Frage gestellt wird, suche zuerst nach einer graphbasierten Lösung, dann geh weiter, wenn es keine gibt.
- Es gibt 4 verschiedene Arten einen Graphen im Speicher zu repräsentieren:
-
MIT(videos):
-
Skiena Vorlesungen - tolle Einführung:
- CSE373 2012 - Lecture 11 - Graph Data Structures (video)
- CSE373 2012 - Lecture 12 - Breadth-First Search (video)
- CSE373 2012 - Lecture 13 - Graph Algorithms (video)
- CSE373 2012 - Lecture 14 - Graph Algorithms (con't) (video)
- CSE373 2012 - Lecture 15 - Graph Algorithms (con't 2) (video)
- CSE373 2012 - Lecture 16 - Graph Algorithms (con't 3) (video)
-
Graphen (Besprechung und mehr):
- 6.006 Single-Source Shortest Paths Problem (video)
- 6.006 Dijkstra (video)
- 6.006 Bellman-Ford (video)
- 6.006 Speeding Up Dijkstra (video)
- Aduni: Graph Algorithms I - Topological Sorting, Minimum Spanning Trees, Prim's Algorithm - Lecture 6 (video)
- Aduni: Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure - Lecture 7 (video)
- Aduni: Graph Algorithms III: Shortest Path - Lecture 8 (video)
- Aduni: Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (video)
-
CS 61B 2014 (starting at 58:09) (video) - CS 61B 2014: Weighted graphs (video)
- Greedy Algorithms: Minimum Spanning Tree (video)
- Strongly Connected Components Kosaraju's Algorithm Graph Algorithm (video)
-
Kompletter Coursera Kurs:
-
werde ich implementieren:
- DFS mit Adjazenzliste (rekursiv)
- DFS mit Adjazenzliste (iterativ mit Stack)
- DFS mit Adjazenzmatrix (rekursiv)
- DFS mit Adjazenzmatrix (iterativ mit Stack)
- BFS mit Adjazenzliste
- BFS mit Adjazenzmatrix
- Kürzester Pfad (Dijkstra)
- minimaler Spannbaum
- DFS-basierte Algorithmen (siehe Aduni Videos oben):
- auf Zyklus prüfen (für Topologische Sortierung benötigt, wir prüfen auf Zyklen bevor wir anfangen)
- Topologische Sortierung
- zähle Zusammenhangskomponenten in einen Graph
- liste starke Zusammenhangskomponenten auf
- prüfe ob es ein bipartiter Graph ist
Noch mehr
-
- Stanford Vorlesung über Rekursion und Backtracking:
- wann sollte man es benutzen
- Wann ist Endrekursion gut?
-
- Wahrscheinlich wirst du im Vorstellungsgespräch nichts mit dynamischer Programmierung zu tun haben, aber es ist wert zu erkennen, wann ein Problem für dynamische Programmierung geeignet ist.
- Dieses Thema kann ziemlich schwer sein. Jedes DP Problem muss als Rekursion dargestellt werden, und darauf zu kommen kann schwer sein.
- Ich schlage vor, dass man sich viele DP Probleme ansieht bis man ein gutes Verständnis vom zugrunde liegenden Muster hat.
- Videos:
- die Skiena Videos kann man manchmal schwer folgen, weil er manchmal auf einer Tafel schreibt, was zu klein zum Lesen ist
- Skiena: CSE373 2012 - Lecture 19 - Introduction to Dynamic Programming (video)
- Skiena: CSE373 2012 - Lecture 20 - Edit Distance (video)
- Skiena: CSE373 2012 - Lecture 21 - Dynamic Programming Examples (video)
- Skiena: CSE373 2012 - Lecture 22 - Applications of Dynamic Programming (video)
- Simonson: Dynamic Programming 0 (fängt an bei 59:18) (video)
- Simonson: Dynamic Programming I - Lecture 11 (video)
- Simonson: Dynamic programming II - Lecture 12 (video)
- Liste von einzelnen DP Problemen (jedes Problem ist klein): Dynamic Programming (video)
- Yale Vorlesungsnotizen:
- Coursera:
-
- Optional: UML 2.0 Series (video)
- Object-Oriented Software Engineering: Software Dev Using UML and Java (21 videos):
- kann man überspringen wenn man gutes Wissen über OO und OO Design Patterns hat
- OOSE: Software Dev Using UML and Java (video)
- SOLID OOP Prinzipien:
- Bob Martin SOLID Principles of Object Oriented and Agile Design (video)
- SOLID Principles (video)
- S - Single Responsibility Principle | Eine einzige Zuständigkeit für jedes Objekt
- O - Open/Closed Principal | Darüber dass Objekte bereit zur Erweiterung aber zur Veränderung sind
- L - Liskov Substitution Principal | Basisklasse und erbende Klasse folgen dem "IST EIN(E)"-Prinzip
- I - Interface segregation principle | Verbraucher sollten nicht dazu gezwungen werden ein Interface zu implementieren, dass sie nicht benutzen
- D -Dependency Inversion principle | Reduziere Abhängigkeiten beim Zusammenbau von Objekten.
-
- Quick UML review (video)
- Lerne diese Muster:
- Strategy
- Singleton
- Adapter
- Prototype
- Decorator
- Visitor (Besucher)
- Factory (Fabrik), abstract factory (abstrakte Fabrik)
- Facade
- Observer (Beobachter)
- Proxy
- Delegate
- Command
- State
- Memento
- Iterator
- Composite
- Flyweight (Fliegengewicht)
- Chapter 6 (Part 1) - Patterns (video)
- Chapter 6 (Part 2) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (video)
- Chapter 6 (Part 3) - Adapter, Facade, Immutable, Read-Only Interface, Proxy (video)
- Series of videos (27 videos)
- Head First Design Patterns
- Ich weiß das legitime Buch ist "Design Patterns: Elements of Reusable Object-Oriented Software", aber Head First ist großartig wenn man mit OO einsteigt.
- Handy reference: 101 Design Patterns & Tips for Developers
- Design patterns for humans
-
- Math Skills: How to find Factorial, Permutation and Combination (Choose) (video)
- Make School: Probability (video)
- Make School: More Probability and Markov Chains (video)
- Khan Academy:
- Kursstruktur:
- Nur die 41 Videos (jedes ist kurz und leicht zu verstehen):
-
- Kenne die bekanntesten NP-vollständigen Probleme, wie z.B. Traveling Salesman und das Rucksackproblem, und sei in der Lage die zu erkennen, wenn ein Interviewer heimlich danach fragt.
- Wissen was NP-vollständig bedeutet.
- Computational Complexity (video)
- Simonson:
- Skiena:
- Complexity: P, NP, NP-completeness, Reductions (video)
- Complexity: Approximation Algorithms (video)
- Complexity: Fixed-Parameter Algorithms (video)
- Peter Norvig beschreibt annähernd optimale Lösungen für das Traveling Salesman Problem:
- Seite 1048 - 1140 in CLRS falls man es besitzt.
-
- Computer Science 162 - Operating Systems (25 videos):
- für Prozesse und Threads siehe Videos 1-11
- Operating Systems and System Programming (video)
- What Is The Difference Between A Process And A Thread?
- behandelt:
- Prozesse, Threads, Concurrency issues (Probleme von Parallelität)
- Unterschied zwischen Prozessen und Threads
- Prozesse
- Threads
- Locks
- Mutexe
- Semaphoren
- Monitore
- wie sie funtionieren
- Deadlock
- Livelock
- CPU Äktivität, Interrupts, Kontextwechsel
- Moderne Parallelität mit Multicore Prozessoren
- Paging, segmentation and virtual memory (video)
- Interrupts (video)
- Scheduling (video)
- Prozess-Ressourcenverwaltung (Speicher: Code, statischer Speicher, Stack, Heap, und auch Datei-Handle, I/O)
- Thread-Ressourcenverwaltung (teilt sich das obere (minus Stack) mit anderen Threads in selben Prozess aber jeder mit einzelnen Befehlszähler, Stackzähler, Registern, und Stack)
- Forking ist einfach Copy on Write (nur lesend) bis der neue Prozess in den Speicher schreibt, dann wird eine komplette Kopie erstellt.
- Kontextwechsel
- Wie wird Kontextwechsel vom Betriebssystem und der zugrunde liegenden Hardware gehandhabt
- Prozesse, Threads, Concurrency issues (Probleme von Parallelität)
- threads in C++ (series - 10 videos)
- Parallelität in Python (Videos):
- Computer Science 162 - Operating Systems (25 videos):
-
- zu behandeln:
- wie Unit Tests funktionieren
- was sind Mockobjekte
- was ist ein Integration Test
- Was ist Dependency Injection
- Agile Software Testing with James Bach (video)
- Open Lecture by James Bach on Software Testing (video)
- Steve Freeman - Test-Driven Development (that’s not what we meant) (video)
- TDD is dead. Long live testing.
- Is TDD dead? (video)
- Video series (152 videos) - not all are needed (video)
- Test-Driven Web Development with Python
- Dependency Injection:
- How to write tests
- zu behandeln:
-
- in einem Betriebssystem, wie funktioniert es
- kann von Betriebssystem Videos gelernt werden
-
- Sedgewick - Suffix Arrays (video)
- Sedgewick - Substring Search (videos)
- Search pattern in text (video)
Wer noch mehr Details zu diesem Thema erfahren möchte, sollte sich den "String Matching" Abschnitt unter Weitere Details zu ausgewählten Themen ansehen
-
- Achtung, es gibt mehrere Arten von Tries. Manche haben Präfixe, manche nicht, und manche benutzen Strings anstelle von Bits, um den Pfad zu markieren.
- Ich habe mir den Code durchgelesen, aber werde es nicht selber implementieren.
- Sedgewick - Tries (3 Videos)
- Notes on Data Structures and Programming Techniques
- Kurze Kursvideos:
- The Trie: A Neglected Data Structure
- TopCoder - Using Tries
- Stanford Lecture (real world use case) (video)
- MIT, Advanced Data Structures, Strings (can get pretty obscure about halfway through) (video)
-
- Big And Little Endian
- Big Endian Vs Little Endian (video)
- Big And Little Endian Inside/Out (video)
- Sehr technischer Vortrag für Kernel-Devs. Keine Sorge wenn du das meiste nicht verstehst.
- Die erste Hälfte ist ausreichend.
-
- Wenn man Erfahrungen mit Netzwerken hat, oder Reliability Engineer oder Operations Engineer werden will, erwartet Fragen dazu
- ansonsten, ist es nur gut zu wissen
- Khan Academy
- UDP and TCP: Comparison of Transport Protocols (video)
- TCP/IP and the OSI Model Explained! (video)
- Packet Transmission across the Internet. Networking & TCP/IP tutorial. (video)
- HTTP (video)
- SSL and HTTPS (video)
- SSL/TLS (video)
- HTTP 2.0 (video)
- Video Series (21 videos) (video)
- Subnetting Demystified - Part 5 CIDR Notation (video)
- Sockets:
Systementwurf, Skalierbarkeit, Datenverarbeitung
Man kann mit Fragen über Systementwurf rechnen, falls man 4+ Erfahrung hat.
- Skalierbarkeit und Systementwurf sind sehr große Themengebiete mit vielen verschiedenen Themen und Quellen, weil es so viel zu beachten gibt, wenn man eine Software/Hardware baut, die skalierbar ist. Erwarte viel Zeit damit zu verbringen.
- Überlegungen:
- Skalierbarkeit
- vereinfache große Datenmengen zu Einzelwerten
- Transformiere einen Datensatz in einen anderen
- gehe mit absurd großen Datenmengen um
- Systementwurf
- Feature Sets
- Schnittstellen
- Klassenhierarchien
- entwerfe System unter bestimmte Vorgaben
- Einfachheit und Robustheit
- Kompromisse
- Performance Analyse und Optimierung
- Skalierbarkeit
- HIER ANFANGEN: The System Design Primer
- System Design from HiredInTech
- How Do I Prepare To Answer Design Questions In A Technical Inverview?
- 8 Things You Need to Know Before a System Design Interview
- Algorithm design
- Database Normalization - 1NF, 2NF, 3NF and 4NF (video)
- System Design Interview - Es gibt hier viele Quellen. Sieh dir Artikel und Beispiele an. Ich habe ein paar davon unten hingeschrieben.
- How to ace a systems design interview
- Numbers Everyone Should Know
- How long does it take to make a context switch?
- Transactions Across Datacenters (video)
- A plain English introduction to CAP Theorem
- Consensus Algorithmen:
- Consistent Hashing
- NoSQL Patterns
- Skalierbarkeit:
- Das braucht man nicht alles. Sucht euch einfach die paar Themen raus, die euch interessieren.
- Great overview (video)
- Kurzreihen:
- Scalable Web Architecture and Distributed Systems
- Fallacies of Distributed Computing Explained
- Pragmatic Programming Techniques
- Jeff Dean - Building Software Systems At Google and Lessons Learned (video)
- Introduction to Architecting Systems for Scale
- Scaling mobile games to a global audience using App Engine and Cloud Datastore (video)
- How Google Does Planet-Scale Engineering for Planet-Scale Infra (video)
- The Importance of Algorithms
- Sharding
- Scale at Facebook (2012), "Building for a Billion Users" (video)
- Engineering for the Long Game - Astrid Atkinson Keynote(video)
- 7 Years Of YouTube Scalability Lessons In 30 Minutes
- How PayPal Scaled To Billions Of Transactions Daily Using Just 8VMs
- How to Remove Duplicates in Large Datasets
- A look inside Etsy's scale and engineering culture with Jon Cowie (video)
- What Led Amazon to its Own Microservices Architecture
- To Compress Or Not To Compress, That Was Uber's Question
- Asyncio Tarantool Queue, Get In The Queue
- When Should Approximate Query Processing Be Used?
- Google's Transition From Single Datacenter, To Failover, To A Native Multihomed Architecture
- Spanner
- Machine Learning Driven Programming: A New Programming For A New World
- The Image Optimization Technology That Serves Millions Of Requests Per Day
- A Patreon Architecture Short
- Tinder: How Does One Of The Largest Recommendation Engines Decide Who You'll See Next?
- Design Of A Modern Cache
- Live Video Streaming At Facebook Scale
- A Beginner's Guide To Scaling To 11 Million+ Users On Amazon's AWS
- How Does The Use Of Docker Effect Latency?
- A 360 Degree View Of The Entire Netflix Stack
- Latency Is Everywhere And It Costs You Sales - How To Crush It
- Serverless (very long, just need the gist)
- What Powers Instagram: Hundreds of Instances, Dozens of Technologies
- Cinchcast Architecture - Producing 1,500 Hours Of Audio Every Day
- Justin.Tv's Live Video Broadcasting Architecture
- Playfish's Social Gaming Architecture - 50 Million Monthly Users And Growing
- TripAdvisor Architecture - 40M Visitors, 200M Dynamic Page Views, 30TB Data
- PlentyOfFish Architecture
- Salesforce Architecture - How They Handle 1.3 Billion Transactions A Day
- ESPN's Architecture At Scale - Operating At 100,000 Duh Nuh Nuhs Per Second
- Siehe "Messaging, Serialization und Queueing Systems" weiter unten für Infos über manche Technologien die Services miteinander verbinden können
- Twitter:
- Für sogar noch mehr, siehe "Mining Massive Datasets" Videoreihen im Videoreihen Abschnitt.
- Übe den Prozess des Systementwurfs: Hier sind ein paar Ideen, die man auf Papier durchspielen kann, jede mit einer Dokumentation wie es in der echten Welt umgesetzt wurde:
- Review: The System Design Primer
- System Design from HiredInTech
- Spickzettel
- Ablauf:
- Verstehe das Problem und den Umfang:
- definiere den Anwendungsfall, was dem Interviewer helfen wird
- schlage zusätzliche Funktionen vor
- entferne Elemente die laut Interviewer nicht zum Umfang passen
- nimme an das hohe Erreichbarkeit gefordert ist, füge das zu den Anwendungsfällen hinzu
- Denke über Beschränkungen nach:
- frag wie viele Anfragen im Monat es gibt
- frag wie viele Anfragen in der Sekunde es gibt (sie sagen es entweder freiwillig oder du solltest es selbst ausrechnen)
- schätze prozentuales Verhältnis zwischen Lese- und Schreibzugriffe
- denk an die 80/20 Regel bei der Schätzung
- wie viel Daten pro Sekunde geschrieben werden
- absoluter Speicherverbrauch für 5 Jahre
- wie viele Daten pro Sekunde gelesen werden
- Abstrakter Entwurf:
- Ebenen (Service, Daten, Caching)
- Infrastruktur: Load Balancing, Messaging
- grobe Übersicht einiger Schlüsselalgorithmen die den Service antreiben
- berücksichtige Flaschenhälse und finde Lösungen
- Verstehe das Problem und den Umfang:
- Übungen:
- Entwerfe ein CDN Netzwerk: alter Artikel
- Entwerfe ein System um zufällige einmalige IDs zu generieren
- Entwerfe ein Online Multiplayer Kartenspiel
- Entwerfe eine Key-Value Datenbank
- Entwerfe einen System um Bilder zu teilen
- Entwerfe ein Empfehlungssystem
- Entwerfe ein URL-Shortener System: von oben kopiert
- Entwerfe ein Cache System
Finaler Rückblick
Dieser Abschnitt enthält kürzere Videos, die man sich ziemlich schnell anschauen kann, um die wichtigsten Konzepte noch mal zu wiederholen.
Das ist ganz gut, falls man sein Wissen öfter mal auffrischen möchte.
- Reihe mit kurzen 2-3 Minuten Videos (23 videos)
- Reihe mit kurzen 2-5 Minuten Videos - Michael Sambol (38 videos):
- Sedgewick Videos - Algorithms I
- Sedgewick Videos - Algorithms II
Übungen zu Programmieraufgaben
Jetzt da ihr alle Informatikfragen von oben kennt, wird es Zeit Antworten auf Codingfragen zu üben.
Bei den Übungen geht es nicht darum sich die Antworten zu merken.
Warum du üben musst Programmieraufgaben zu lösen:
- Probleme wiedererkennen, und welche Datenstrukturen und Algorithmen sich dazu eignen
- Anforderungen an das Problem sammeln
- das Problem zu besprechen wie man es im Vorstellungsgespräch tun würde
- auf der Tafel oder dem Papier zu entwickeln, nicht auf den Computer
- die Zeit- und Speicherkomplexität zu ermitteln
- seine Lösung zu testen
Es gibt eine großartige Einführung für das methodische, kommunikative Problem lösen in einem Vorstellungsgespräch. Das kann man auch von Büchern über Vorstellungsgespräche lernen, aber das fand ich herausragend: Algorithm Design Canvas
Keine Tafel zu Hause? Macht Sinn. Ich bin ein Spinner und habe eine große Tafel. Anstelle einer Tafel hol dir ein großes Zeichenbrett aus dem Kunstladen. Du kannst auf dem Sofa sitzen und üben. Das ist meine "Sofatafel". Ich habe auf den Foto ein Stift dazu gelegt, um die Größenverhältnisse darzustellen. Wenn man mit Stift schreibt, wünscht man sich, man könnte löschen. Wird schnell sehr unordentlich.
Zusatz:
Lese und löse Programmieraufgaben (in dieser Reihenfolge):
- Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
- Antworten in C, C++ und Java
- Cracking the Coding Interview, 6th Edition
- Antworten in Java
Siehe Literaturliste oben
Programmieraufgaben/Wettbewerbe
Nachdem du dir die grauen Zellen weg gelernt hast, lass die grauen Zellen arbeiten. Nimm jeden Tag eine Herausforderung an, so viele wie du kannst.
Videos über Codingfragen im Vorstellungsgespräch:
Wettbewerbsseiten:
- LeetCode
- TopCoder
- Project Euler (math-focused)
- Codewars
- HackerEarth
- HackerRank
- Codility
- InterviewCake
- Geeks for Geeks
- InterviewBit
- Sphere Online Judge (spoj)
- Codechef
Wettbewerbsrepos:
Mock Interviews:
- Gainlo.co: Mock interviewers from big companies - Das habe ich benutzt und es hat mir dabei geholfen vor den Telefon- und Vor-Ort-Gesprächen besser zu entspannen.
- Pramp: Mock interviews from/with peers - peer-to-peer Modell um Vorstellungsgespräche zu üben
- Refdash: Mock interviews and expedited interviews - hilft auch Kandidaten den Prozess zu beschleunigen indem mehrere Vorstellungsgespräche bei Techfirmen übersprungen werden.
- Cracking The Coding Interview Teil 2 (videos):
- Siehe Lebenslaufvorbereitung in Cracking The Coding Interview und den hinteren Teil von Programming Interviews Exposed
Rechne mit 20 Interviewfragen die dir gestellt werden, zusammen mit den unteren Zeilen. Bereite 2 - 3 Antworten für jede vor. Bereite eine Geschichte vor, nicht nur ein paar Infos, über etwas das du erreicht hast.
- Warum möchtest du den Job?
- Was ist ein schweres Problem das du gelöst hast?
- Die größte Herausforderung vor der du standest?
- Bester/schlechtester Entwurf den du gesehen hast?
- Ideen um ein bestehendes Produkt zu verbessern.
- Wie arbeitest du am Besten, als Individuum und als Teil eines Teams?
- Welche deiner Fertigkeiten und Erfahrungen würden dir in der Rolle helfen und warum?
- Was hat dir am meisten Spaß gemacht an [Job x / Projekt y]?
- Was war die größte Herausforderung im [Job x / Projekt y]?
- Was war der schwerste Bug den du bearbeitet hast in [Job x / Projekt y]?
- Was hast du in [Job x / Projekt y] gelernt?
- Was hättest du gerne besser gemacht in [Job x / Projekt y]?
Einige von meinen (ich weiß vielleicht schon die Antwort aber möchte gerne ihre Meinung oder die Meinung des Teams hören):
- Wie groß ist das Team?
- Wie sieht der Entwicklungszyklus aus? Macht ihr Wasserfall/Sprints/agil?
- Wird oft zu Abgabeterminen gehetzt? Oder seid ihr flexibel?
- Wie werden Entscheidungen in eurem Team getroffen?
- Wie viele Meetings habt ihr pro Woche?
- Hilft dir die Arbeitsumgebung dich zu konzentrieren?
- Woran arbeitet ihr gerade?
- Was gefällt dir daran?
- Wie ist das Arbeitsleben so?
Gratulation!
Lerne weiter.
Man ist nie wirklich fertig.
*****************************************************************************************************
*****************************************************************************************************
Alles unterhalb hiervon ist optional.
Wenn man das studiert, bekommt man mehr Wissen zu Informatikkonzepten, und wird besser auf
einen Softwareingenieur Job vorbereitet.
Man ist dann ein abgerundeterer Softwareingenieur.
*****************************************************************************************************
*****************************************************************************************************
Zusätzliche Bücher
-
The Unix Programming Environment
- alt aber gut
-
The Linux Command Line: A Complete Introduction
- eine moderne Variante
-
- eine behutsame Einführung zu Design Patterns
-
Design Patterns: Elements of Reusable Object-Oriented Software
- auch bekannt als das "Gang Of Four" Buch, oder GOF
- das anerkannte Buch zu Design Patterns
-
Algorithm Design Manual (Skiena)
- Als ein Rückblick und zur Problemerkennung
- Der Katalog an Algorithmen ist weit über den Schwierigkeitsgrad, den man in Vorstellungsgesprächen hat.
- Dieses Buch besteht aus 2 Teilen:
- Textbuch über Datenstrukturen und Algorithmen
- Vorteile:
- guter Rückblick wie jedes Algorithmen Textbuch es wäre
- nette Erfahrungsberichte wie er Probleme gelöst hat aus der Industrie oder in der akademischen Welt
- Codebeispiele in C
- Nachteile:
- kann so vollgestopft und unzugänglich sein wie CLRS, und bei einigen Themen wäre CLRS die bessere Wahl
- Kapitel 7, 8, 9 sind extrem schwer zu folgen, weil einige Dinge nicht gut erklärt werden oder ich einfach zu dumm bin
- versteh mich nicht falsch: Ich mag Skiena, seine Art zu unterrichten, seine Eigenheiten, aber ich mag nicht das Stony Brook Material.
- Vorteile:
- Algorithmenkatalog:
- Das ist der eigentliche Grund, weswegen ich dieses Buch gekauft habe.
- muss mich noch einlesen. Werde das hier ergänzen, sobald ich durch bin.
- Textbuch über Datenstrukturen und Algorithmen
- kann man auf den Kindle ausleihen
- Antworten:
- Korrekturverzeichnis
-
- Wichtig: Das Buch zu lesen ist nur eingeschränkt von Nutzen. Das Buch ist ein toller Rückblick auf Algorithmen und Datenstrukturen, aber man lernt dadurch nicht guten Code zu schreiben. Man muss in der Lage sein effizient vernünftigen Code zu schreiben.
- aka CLR, manchmal CLRS, weil Stein erst später dazu kam
-
Computer Architecture, Sixth Edition: A Quantitative Approach
- Für eine tiefere, aktuellere (2017), aber auch längere Behandlung
-
- Die ersten paar Kapitel beinhalten clevere Lösungen auf Programmieraufgaben (einige sehr alte mit Datenkasetten) aber es reicht aus für eine Einführung. Das ist ein Ratgeber zu Programmentwurf und -architektur, vergleichbar mit Code Complete, aber viel kürzer.
Zusätzliches Wissen
Diese Themen werden vermutlich nicht in einen Vorstellungsgespräch aufkommen, aber ich habe sie trotzdem hinzugefügt um euch dabei zu helfen ein vollständiger Softwareingenieur zu werden und damit ihr über bestimmte Technologien und Algorithmen Bescheid wisst, sodass ihr eine größere Auswahl an Werkzeugen habt.
-
- macht euch bekannt mit Unix-basierten Code Editoren
- vi(m):
- emacs:
-
- Khan Academy
- mehr über Markov-Prozesse:
- für mehr, siehe "MIT 6.050J: Information and Entropy" weiter unten.
-
- Intro
- Parity
- Hamming Code:
- Error Checking
-
- siehe Videos unten
- stell sicher, dass du zuerst die Informationstheorie Videos gesehen hast
- Information Theory, Claude Shannon, Entropy, Redundancy, Data Compression & Bits (video)
-
- siehe Videos unten
- stell sicher, dass du zuerst die Informationstheorie Videos gesehen hast
- Khan Academy Series
- Cryptography: Hash Functions
- Cryptography: Encryption
-
- stell sicher, dass du zuerst die Informationstheorie Videos gesehen hast
- Computerphile (videos):
- Compressor Head videos
- (optional) Google Developers Live: GZIP is not enough!
-
- Gegeben ein Bloom Filter mit m Bits und k Hashingfunktionen, beides insertion und membership-Tests sind O(k)
- Bloom Filters (video)
- Bloom Filters | Mining of Massive Datasets | Stanford University (video)
- Tutorial
- How To Write A Bloom Filter App
-
- wird benutzt um die Ähnlichkeit von Dokumenten zu bestimmen
- Das Gegenteil von MD5 oder SHA, die benutzt werden, um festzustellen ob 2 Dokumente/Strings genau gleich sind.
- Simhashing (hopefully) made simple
-
-
mind. 1 Art von Balancierten Suchbäumen kennen (und wissen wie es implementiert wird)
-
"Among balanced search trees, AVL and 2/3 trees are now passé, and red-black trees seem to be more popular. A particularly interesting self-organizing data structure is the splay tree, which uses rotations to move any accessed key to the root." - Skiena
-
Ich habe mich dazu entschieden einen Splay Tree zu implementieren. Von dem was ich gelesen habe, wird man kein balancierten Suchbaum in einem Vorstellungsgespräch implementieren. Aber ich wollte die Erfahrung machen selber einen zu coden und seien wir mal ehrlich, Splay Trees sind Alleskönner. Ich habe eine Menge Code für Rot-Schwarz Bäume gelesen.
- Splay Tree: insert, search, delete Funktionen Falls man mit einen Rot-Schwarz Baum endet, versuch das:
- search und insertion Funktionen, delete überspringen
-
Ich möchte mehr über B-Bäume lernen, da sie so weit verbreitet sind bei riesigen Datenmengen.
-
AVL Trees
- In der Praxis: Meines Wissens nach werden sie nicht so oft in der Praxis verwendet, aber ich könnte mir vorstellen wo sie verwendet werden: Der AVL Tree ist eine weitere Datenstruktur die O(log n) Suchen, Einfügen und Löschen unterstützt. Sie sind strenger balanciert als Rot-Schwarz Bäume, was das Einfügen und Löschen verlangsamt aber das Auslesen beschleunigt. Das macht sie attraktiv für Datenstrukturen die nur einmal aufgebaut und geladen werden ohne Umbau, so wie Wörterbücher für Sprachen (oder für Programme, wie z.B. der Opcode eines Assemblers oder Interpreters).
- MIT AVL Trees / AVL Sort (video)
- AVL Trees (video)
- AVL Tree Implementation (video)
- Split And Merge
-
Splay Trees
- In der Praxis: Splay Trees werden typischerweise bei der Implementierung von Caches, Speicherverwaltung, Routers, Garbage Collectoren, Datenkompression, Ropes (Ersatz für String, gebraucht für lange Texte), in Windows NT (im virtuellen Speicher, Netzwerk und Dateisystem Code) etc. verwendet
- CS 61B: Splay Trees (video)
- MIT Vorlesung: Splay Trees:
- Wird sehr mathematisch, aber man sollte sich auf jeden Fall die letzten 10 Minuten ansehen.
- Video
-
Red/black trees (Rot-Schwarz Bäume)
- sind eine umgewandelte Form von 2-3 Bäumen (siehe unten)
- In der Praxis: Rot-Schwarz Bäume bieten eine worst-case Laufzeitgarantie für Einfügen, Löschen und suchen. Das macht sie nicht nur wertvoll für zeitkritische Anwendungen wie Echtzeitanwendungen, sondern es macht sie auch zu wertvollen Bausteinen in andere Datenstrukturen mit worst-case Garantien. Z.B. viele Datenstrukturen aus der algorithmischen Geometrie können auf Rot-Schwarz Bäumen basieren, und der Completely Fair Scheduler der in aktuellen Linux Kernels verwendet wird benutzt Rot-Schwaz Bäume. In Java 8 wurde die Collection Hashmap so angepasst, dass anstelle einer verketteten Listen ein Rot-Schwarz Baum benutzt wird, um identische Elemente mit schlechten Hashwerten zu speichern.
- Aduni - Algorithms - Lecture 4 (Link springt direkt zum Anfang) (video)
- Aduni - Algorithms - Lecture 5 (video)
- Red-Black Tree
- An Introduction To Binary Search And Red Black Tree
-
2-3 Bäume
- In der Praxis: Bei 2-3 Suchbäumen kann man schneller einfügen zu Lasten von langsameren Suchen (weil die Höhe größer ist verglichen mit AVL Trees).
- Man würde einen 2-3 Tree nur sehr selten verwenden, weil deren Implementierung mehrere verschiedene Arten von Knoten umfasst. Stattdessen benutzt man Rot-Schwarz Bäume.
- 23-Tree Intuition and Definition (video)
- Binary View of 23-Tree
- 2-3 Trees (student recitation) (video)
-
2-3-4 Bäume (aka 2-4 Bäume)
- In der Praxis: Für jeden 2-4 Baum existiert ein Rot-Schwarz Baum mit Datenelementen in derselben Reihenfolge. Das Einfügen und Löschen auf 2-4 Bäumen ist äquivalent zum Farbwechsel und Rotation im Rot-Schwarz Baum. Das macht 2-4 Bäume zu einem wichtigen Werkzeug, um die Logik hinter Rot-Schwarz Bäumen zu verstehen. Und deswegen führen viele Algorithmen Bücher für Einsteiger 2-4 Bäume direkt vor Rot-Schwarz Bäumen ein selbst obwohl 2-4 Trees nicht oft in der Praxis benutzt werden.
- CS 61B Lecture 26: Balanced Search Trees (video)
- Bottom Up 234-Trees (video)
- Top Down 234-Trees (video)
-
N-fache (K-fache, M-fache) Bäume
- Notiz: das N oder K ist der Verzweigungsgrad (max. Zweige)
- Binärbäume sind 2-fache Bäume, mit Verzweigungsgrad = 2
- 2-3 Trees sind 3-fache
- K-Ary Tree
-
B-Bäume
- Fun Fact: Es ist ein Mysterium, aber das B könnte für Boeing, Balanciert, oder Bayer (Co-Erfinder) stehen
- In der Praxis: B-Bäume sind weit verbreitet in Datenbanken. Die meisten modernen Dateisysteme sind B-Bäume (oder Varianten davon). Zusätzlich zum Einsatz in Datenbanken werden B-Bäume auch in Dateisystemen benutzt, um schnellen Zugriff auf einen beliebigen Block in einer bestimmten Datei zu ermöglichen. Das Grundproblem ist es die Adresse eines Dateiblockes in die Adresse eines Diskblocks (oder eines Zylinder-Kopf-Sektors) zu verwandeln.
- B-Tree
- Introduction to B-Trees (video)
- B-Tree Definition and Insertion (video)
- B-Tree Deletion (video)
- MIT 6.851 - Memory Hierarchy Models (video) - behandelt cache-oblivious B-Bäume, sehr interessante Datenstrukturen - die ersten 37 Minuten sind sehr technisch, können übersprungen werden (B ist Blockgröße, Cache Zeilen Länge)
-
-
- großartig um mehrere Punkte in einem Rechteck oder höherdimensionalen Objekten zu finden
- gut geeignet für k-nearest neighbors
- Kd Trees (video)
- kNN K-d tree algorithm (video)
-
- "These are somewhat of a cult data structure" - Skiena
- Randomization: Skip Lists (video)
- For animations and a little more detail
-
- Kombination eines binären Suchbaums mit einem Heap
- Treap
- Data Structures: Treaps explained (video)
- Applications in set operations
-
- siehe Videos unten
-
- Warum ML?
- Google's Cloud Machine learning tools (video)
- Google Developers' Machine Learning Recipes (Scikit Learn & Tensorflow) (video)
- Tensorflow (video)
- Tensorflow Tutorials
- Practical Guide to implementing Neural Networks in Python (using Theano)
- Kurse:
- Great starter course: Machine Learning - nur Videos - siehe Videos 12-18 für eine Auffrischung zu Linearer Algebra (14 und 15 sind Duplikate)
- Neural Networks for Machine Learning
- Google's Deep Learning Nanodegree
- Google/Kaggle Machine Learning Engineer Nanodegree
- Self-Driving Car Engineer Nanodegree
- Quellen:
Weitere Details zu ausgewählten Themen
Ich habe das hinzugefügt, um einige Ideen weiter oben zu verstärken, aber ich wollte sie nicht
oben hinzufügen, weil es sonst zu viel wäre. Es ist leicht es mit einen Thema zu übertreiben.
Ihr wollt doch noch in diesem Jahrhundert eingestellt werden, oder?
-
Union-Find
-
Mehr Dynamische Programmierung (Videos)
- 6.006: Dynamic Programming I: Fibonacci, Shortest Paths
- 6.006: Dynamic Programming II: Text Justification, Blackjack
- 6.006: DP III: Parenthesization, Edit Distance, Knapsack
- 6.006: DP IV: Guitar Fingering, Tetris, Super Mario Bros.
- 6.046: Dynamic Programming & Advanced DP
- 6.046: Dynamic Programming: All-Pairs Shortest Paths
- 6.046: Dynamic Programming (student recitation)
-
Fortgeschrittene Graphbearbeitung (Videos)
-
MIT Wahrscheinlichkeit (mathematisch, es wird langsam angegangen, was gut bei Mathe ist) (Videos):
-
String Matching
- Rabin-Karp (videos):
- Knuth-Morris-Pratt (KMP):
- Boyer–Moore string search algorithm
- Coursera: Algorithms on Strings
- fängt großartig an, wird aber nach KMP viel schwieriger als es sein müsste
- gute Erklärung von Tries
- kann übersprungen werden
-
Sortierung
- Stanford Vorlesungen über Sortierung:
- Shai Simonson, Aduni.org:
- Steven Skiena Vorlesungen über Sortierung:
Zurücklehnen und genießen. "Netflix and skill" :P
Videoreihen
-
Liste einzelnen Dynamische Programmierung Probleme (jedes ist kurz)
-
Excellent - MIT Calculus Revisited: Single Variable Calculus
-
Computer Science 70, 001 - Spring 2015 - Discrete Mathematics and Probability Theory
-
CSE373 - Analysis of Algorithms (25 videos)
-
UC Berkeley CS 152: Computer Architecture and Engineering (20 videos) -
Carnegie Mellon - Computer Architecture Lectures (39 videos)
-
MIT 6.042J: Mathematics for Computer Science, Fall 2010 (25 videos)
-
MIT 6.050J: Information and Entropy, Spring 2008 (19 videos)
Paper (Wissenschaftliche Veröffentlichtungen)
- Liebst du klassische Paper?
- 1978: Communicating Sequential Processes
- 2003: The Google File System
- ersetzt durch Colossus in 2012
- 2004: MapReduce: Simplified Data Processing on Large Clusters
- größtenteils ersetzt durch Cloud Dataflow?
- 2006: Bigtable: A Distributed Storage System for Structured Data
- 2006: The Chubby Lock Service for Loosely-Coupled Distributed Systems
- 2007: Dynamo: Amazon’s Highly Available Key-value Store
- Das Dynamo Paper hat die NoSQL Revolution ausgelöst.
- 2007: What Every Programmer Should Know About Memory (very long, and the author encourages skipping of some sections)
- 2010: Dapper, a Large-Scale Distributed Systems Tracing Infrastructure
- 2010: Dremel: Interactive Analysis of Web-Scale Datasets
- 2012: Google's Colossus
- Paper nicht verfügbar
- 2012: AddressSanitizer: A Fast Address Sanity Checker:
- 2013: Spanner: Google’s Globally-Distributed Database:
- 2014: Machine Learning: The High-Interest Credit Card of Technical Debt
- 2015: Continuous Pipelines at Google
- 2015: High-Availability at Massive Scale: Building Google’s Data Infrastructure for Ads
- 2015: TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
- 2015: How Developers Search for Code: A Case Study
- 2016: Borg, Omega, and Kubernetes