Algorithms cheat sheet

Important algorithms for coding interviews [Java]

1. Sorting

• Insertion Sort TC = O(n^2) | SC = O(1)
• Merge Sort TC = O(nlogn) | SC = O(n)
• Quick Sort TC = (Best Case = O(nlogn)), (Worst Case = O(n^2)) | SC = (Best Case = O(logn)), (Worst Case = O(n))
• Heap Sort TC = O(nlogn) | SC = O(1)
• Bubble Sort TC = O(n^2) | SC = O(1)

2. Heaps

• Building Max Heap TC = O(n) | SC = O(logn)

3. Searching

• Linear Search TC = O(n) | SC = O(1)
• Binary Search TC = O(logn) | SC = O(1)

4. Greedy Algorithms

• Fractional Knapsack TC = O(nlogn) | SC = O(n)
• Huffman Encoding TC = O(nlogn) | SC = O(n)
• Job Sequencing TC = O(n^2) | SC = O(n)
• Prims Algorithm[Adjacency Matrix] TC = O(v^2) | SC = O(v)
• Dijsktra Algorithm[Adjacency Matrix] TC = O(v^2) | SC = O(v)

5. Dynamic Programming

• Matrix Chain Multiplication [BU] TC = O(n^3) | SC = O(n^2)
• Matrix Chain Multiplication [TD] TC = O(n^3) | SC = O(n^2)
• Longest Common Subsequence TC = O(mn) | SC = O(mn)
• Multistage Graph TC = O(E) | SC = O(V)
• 0-1 Knapsack TC = O(nw) | SC = O(nw)
• Subset Sum TC = O(nw) | SC = O(nw)