Algorithms

• Complexity Analysis
  • Big O Notation
  • Master Theorem
  • Amortized Analysis
  • Common complexity pattern
• NP-Completeness
  • NP-Completeness Approximation Algorithms
• Bit manipulation
  • Gray code
• Algorithm Design Paradigms
  • Complete Search
    • Iterative
    • Recursive
      • Backtracking
      • Branch and Bound
  • Divide and Conquer
  • Dynamic Programming
  • Greedy:
    • Activity selection problem
    • Huffman codes
• Sorting
  • Bubble sort
  • Insertion sort
  • Selection sort
  • Merge sort
  • Quick sort
  • Heap sort
  • Counting sort
  • Radix sort
  • Bucket sort
  • External sort
• Searching
  • Lineary search
  • Binary search
    • Binary search the answer
    • Exponential search.
  • Search with hashing (O(1) amortized)
• String
  • String manipulation
    • Split string: c++, java
  • String matching
    • Rabin-Karp
    • 2D Rabin-Karp
    • Finite automata
    • KMP (Knuth-Morris-Pratt): c++, java
    • String matching with gap characters.
• Math
  • Mathematical Background
  • Counting and Probability
  • Number theory
  • Factorization in O(sqrt(N))
  • Sieve Eratosthenes
  • Euclid's algorithm for finding Greatest Common Divisor (GCD)
  • Extended Euclid's algorithm for finding Modular Multiplicative Inverse
  • Primality testing
  • The Tortoise and Hare algorithm
  • Algebraic Expressions
    • Infix, Prefix, Postfix Expressions
• Probability
  • Medians and Order Statistics
    • Randomized order statistic / Quickselect
• Tree
  • Minimum spanning tree (MST)
    • Kruskal's algorihtm
    • Prim's algorithm
• Binary Tree:
  • Preorder traversal, recursive and iterative
  • Inorder traversal, recursive and iterative
  • Postorder traversal, recursive and iterative
  • Morris Inorder Tree Traversal
  • Morris Preorder Tree Traversal
  • Morris Postorder Tree Traversal
  • Binary Tree Iterator
• Graph
  • BFS
  • DFS
  • Flood fill
  • Topological sort
  • Bridges and Articulation Points of a undirected graph
  • Strongly connected components
  • Biconnected Components
  • Eulerian graph
  • Graph coloring
    • Interval-graph coloring problem
  • Bipartite graph checking
  • Shortest-paths
    • Single-source shortest-paths - Bellman Ford
    • Single-source shortest-paths on DAG
    • Single-source shortest-paths - Dijkstra
    • All pairs shortest-paths - Floyd
    • All pairs shortest-paths - Johnson
    • Transitive closure of a directed graph
  • Network flow
• Computational Geometry:
  • Determine if there exists any 3 points in a set of n points that are colinear
  • Determine if a point lies inside a simple polygon (not neccessary convex)
  • Find area of a simple polygon (not neccessary convex)
  • Determining whether any pair of segments intersects (Shamos–Hoey algorithm)
  • Determining whether any pair of circles intersects
  • Find all intersections of a set of segments (Bentley–Ottmann algorithm)
  • Finding the convex hull:
    • Graham's scan algorithm (nlogn)
    • Javis's march (nh)
  • Finding the farthest pair of points
  • Finding the closest pair of points (nlogn)
• Window Sliding
• Two pointers
• A*
• Bloom Filter
• Chvátal's greedy set-covering heuristic

Data structures

• Array: static and dynamic size.
  • BitSet: useful when size of an array of booleans is small (not more than 62 booleans).
• Linked list:
  • Singly Linked List
  • Doubly Linked List
• Hash Table
• Heap Need to read this before reading any heap related stuffs:
  • Binary heap
  • D-ary heap
  • Young Tableau
  • Mergeable heap
  • Fibonacci Heap
• String
  • Trie
  • Suffix Tree
  • Suffix Array
• Stack
• Queue
  • Priority Queue: java
  • Circular queue
• Deque
• Tree:
  • Binary Tree
  • Binary Search Tree
  • Balanced Search Tree (Java's TreeSet/TreeMap):
    • AVL Tree: balanced binary search tree.
    • Splay Tree: balanced binary search tree.
    • Red Black Tree: balanced binary search tree.
    • B-Trees: balanced binary search tree generalization.
  • Segment Tree (IT - Interval Tree)
  • Fenwick Tree (BIT - Binary Indexed Tree)
  • Radix Tree
• Disjoint-Set Forest
• Sparse Table
• Treap

Resources

• Book: Introduction to Algorithms, 3rd - CLRS. (Chapter 5, 26, 27, 35; Chapter 14, 17, 18, 19, 20, 28, 29, 30)
• Book: Competitive Programming 3, 4.1, 4.2
• Book: Clean Code - Robert C Martin
• E-Maxx Algorithms in English
• Tech Dev Guide With Google
• Project Euler
• Pramp

Advices

• "The truth is that you are never going to feel fully prepared."

• "Majority candidates know what DFS/BFS is. What makes a difference is to have a deep understanding of those concepts."

• "You should be clear about the definition of those basic data structures/algorithms. Most people did a good job in this part, but not perfect. For instance, a lot of people are confused about dynamic programming and recursion."

• "Try to compare relevant data structures/algorithms and understand their pros and cons. A good example is BFS and DFS."

• Which algorithm is better in what case?

Miscellaneous

• Vocabulary
• Questions
• Limited memory interview questions
• Online vs Offline algorithm