Data Structures

Data Structures	Key Points
Primitive types	Know how `int`, `char`, `double`, etc. are represented in memory and the primitive operations on them.
Arrays	Fast access for element at an index, slow lookups (unless sorted) and insertions. Be comfortable with notions of iteration, resizing, partitioning, merging, etc.
Strings	Know how strings are represented in memory. Understand basic operators such as comparison, copying, matching, joining, splitting, etc.
Lists	Understand trade-offs with respect to arrays. Be comfortable with iteration, insertion, and deletion within singly and doubly linked lists. Know how to implement a list with dynamic allocation, and with arrays.
Stacks and queues	Recognize where last-in first-out (stack) and first-in first-out (queue) semantics are applicable. Know array and linked list implementations.
Binary trees	Use for representing hierarchical data. Know about depth, height, leaves, search path, traversal sequences, successor/pre-decessor operations.
Heaps	Key benefit: O(1) lookup find-max, O(logn) insertion, and O(logn) deletion of max. Node and array representations. Min-heap variant.
Hash tables	Key benefits: O(1) insertions, deletions, lookups; good for comparison of unordered date.
	Key disadvantages: not suitable for order-related queries; need for resizing; poor worst-case performance.
	Understand implementation using array of buckets and collision chains. Know hash functions for integers, strings, objects.

Algorithms

Algorithm type	Key points
Sorting	Uncover some structure by sorting the input.
Recursion	If the structure of the input is defined in a recursive manner design, a recursive algorithm that follows the input definition.
Divide-and-conquer	Divide the problem into two or more smaller independent sub-problems and solve the original problem using solutions to the sub-problems.
Dynamic programming	Compute solutions for smaller instances of a given problem and use these solutions to construct a solution to the problem. Cache for performance.
Greedy algorithms	Compute a solution in stages, making choices that are locally optimum at each step; these choices are never undone.
Invariants	Identify an invariant and use it to rule out potential solutions that are sub-optimal or dominated by other solutions.
Graph modeling	Describe the problem using a graph and solve it using an existing graph algorithm.

Principle	Key points
Concrete Examples	Manually solve concrete instance and then build a general solution. Start with small inputs (e.g., few elements) and extremal inputs (e.g., sorted)
Case analysis	Split the input/execution into a number of cases and solve each case in isolation.
Iterative refinement	Most problems can be solved using a brute-force approach. Find such a solution and improve upon it.
Reduction	Use a known solution to some other problem as a sub-routine.