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.
| 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 | โ |
| 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
| 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) | โ |
| 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 | ,, | โ |
| 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 | โ |
| 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 | โ |
| 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 | โ |
Got the table design and a bunch of pattern-definitions from this cool repo: https://github.com/tmrts/go-patterns