Computer Science Training

I suggest using this list as a warm-up for interview preperation. Follow it up with interview problems from HackerRank, LeetCode, Cracking the coding interview or Programming Interviews Exposed. Alternatively go old school with Project Euler.

It can help to practice using coderpad.io, since it is used for many coding interviews.

Concepts

Concept	Description	Status
Big O	Growth of run time and space complexity	✔
Divide and Conquer	Design paradigm based on multi-branched recursion	✔
Dynamic Programming	An optimization over plain recursion	✘
Memory (Stack vs Heap)	Memory allocation	✔
Bitwise Operations	Operations on ints and uints at the binary level	✔
Hashing	Map data of arbitrary size to fixed-size values	✔
Permutations and Combinations	Find all permutations or combinations	✔

Data Structures

Structure	Access^	Search^	Insertion^	Deletion^	Status
Stack	Θ(n)	Θ(n)	Θ(1)	Θ(1)	✔
Queue	Θ(n)	Θ(n)	Θ(1)	Θ(1)	✔
ArrayList	Θ(1)	Θ(n)	Θ(n)	Θ(n)	✔
Singly LinkedList	Θ(n)	Θ(n)	Θ(1)	Θ(1)	✔
Doubly LinkedList	Θ(n)	Θ(n)	Θ(1)	Θ(1)	✔
SkipList	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	✘
Set	Θ(n)	Θ(n)	Θ(1)	Θ(n)	✔
HashTable	N/A	Θ(1)	Θ(1)	Θ(1)	✔
Binary Search Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	✔
Trie					✘
Graph					✔
Red-Black Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	✘

^ = average

Sorting

Algorithm	Best	Average	Worst	Space (Worst)	Status
Bubble Sort (Exchange)	Ω(n)	Θ(n^2)	O(n^2)	O(1)	✔
Quick Sort (Exchange)	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(log(n))	✔
Insertion Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)	✔
Heap Sort (Selection)	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(1)	✔
Merge Sort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(n)	✔

Common Problems

Problem	Description	Status
Maximum subarray	Find a contiguous subarray with the largest sum	✔
Sliding window method	Find all anagrams in a string	✔
Binary search recursive	Find an item in a sorted array in log(n) time	✔
Rabin-Karp	Rolling hash algorithm used for string-matching	✔
Prime Numbers	Fermat, Pollard's rho, trial division	✔
Topological Sort	Sort nodes in a graph	✔
Permutations (Recursive)	Find all permutations	✔
Permutations (Iterative)	Find all permutations	✔
Permutations (Factorial)	Find all permutations	✔
Fibonacci iterative	Approximation in integers to the logarithmic spiral series	✔
Fibonacci recursive	,,	✔
Fibonacci dynamic programming	,,	✔

Creational Patterns

Pattern	Description	Status
Abstract Factory	Provides an interface for creating families of releated objects	✘
Builder	Builds a complex object using simple objects	✔
Factory Method	Defers instantiation of an object to a specialized function for creating instances	✔
Prototype	Co-opt one instance of a class for use as a breeder of all future instances	✘
Singleton	Restricts instantiation of a type to one object	✔

Structural Patterns

Pattern	Description	Status
Adapter	Wrap an existing class with a new interface	✔
Bridge	Decouples an interface from its implementation so that the two can vary independently	✘
Composite	Encapsulates and provides access to a number of different objects	✘
Decorator	Adds behavior to an object, statically or dynamically	✔
Facade	Uses one type as an API to a number of others	✘
Flyweight	Reuses existing instances of objects with similar/identical state to minimize resource usage	✘
Proxy	Provides a surrogate for an object to control it's actions	✔

Behavioral Patterns

Pattern	Description	Status
Chain of Responsibility	Avoids coupling sender and receiver	✘
Command	Bundles a command and arguments to call later	✘
Interpreter	Define a grammatical representation for a language	✘
Iterator	Access the elements of an aggregate object sequentially	✔
Mediator	Connects objects and acts as a proxy	✘
Memento	Generate an opaque token that can be used to go back to a previous state	✘
Observer	Provide a callback for notification of events/changes to data	✔
State	Encapsulates varying behavior for the same object based on its internal state	✘
Strategy	Enables an algorithm's behavior to be selected at runtime	✔
Template Method	Defines a skeleton class which defers some methods to subclasses	✘
Visitor	Separates an algorithm from an object on which it operates	✘

Acknowledgement

Got the table design and a bunch of pattern-definitions from this cool repo: https://github.com/tmrts/go-patterns