Mastering Must-Know Algorithms for Interview Prep

Understanding algorithms and their complexities is crucial for coding interviews. Here’s a quick guide
to help you grasp essential algorithms, their use cases, and their complexities.
The following semantic shows different types of algorithms that you must know to become a master
at coding algorithms.

DFS
Graph BFS
Algorithms Dijkstra’s Algo
Connected Components

Huffman Coding
Greedy
Algorithms Prim’s Algorithm
Rabin Karb Algorithm

Longest Common Substring

Must Know Dynamic Memoization
Algorithms Programming Tabulation
Fibonacci

Backtracking N-Queens

Merge Sort
Divide and Quick Sort
Conquer Matrix-chain Multiplication
Binary Search

Here’s a quick overview of different Big-O classes that you’ll find helpful while going through this cheat
sheet.

Worse:
O(n!) Exponential - O(2n) Quadratic - O(n2)

Log-Linear - O(n log(n))

)...
(n 3

Linear - O(n)
-O
#computations

ial
om
lyn
Po

Logarithmic - O(log(n))

Constant - O(1)

Input Size n
Mastering Must-Know Algorithms for Interview Prep

Sorting Algorithms
1. Bubble Sort
Definition: Repeatedly swaps adjacent elements if they are in the wrong order.
Complexity Analysis:
• Time complexity:
◦ Best: O(n)
◦ Average: O(n2)
◦ Worst: O(n2)
• Space complexity: O(1)

4 2 1 3 2 4 1 3

First swap Second swap

2 1 4 3 2 1 3 4

Third swap Fourth swap

1 2 3 4

Sorted array

2. Selection Sort
Definition: Selects the smallest element from an unsorted list and swaps it with the
beginning of the list.
Complexity Analysis:
• Time complexity:
◦ Best: O(n2)
◦ Average: O(n2)
◦ Worst: O(n2)
• Space complexity: O(1)

3 1 2 3 1 2 3 1 2

Current Min

1 3 2 1 3 2 1 3 2

Current Min New Min

1 3 2 1 2 3

Swap
Mastering Must-Know Algorithms for Interview Prep

3. Insertion Sort
Definition: Builds the final sorted array one item at a time.
Complexity Analysis:
• Time complexity:
◦ Best: O(n)
◦ Average: O(n2)
◦ Worst: O(n2)
• Space complexity: O(1)

Initially 3 2 1 3 2 1

First pass 3 2 1 2 3 1

Second pass 2 3 1 2 1 3

Third pass 2 1 3 1 2 3

4. Heap Sort
Definition: Converts the list into a heap, then repeatedly extracts the maximum and
rebuilds the heap.
Complexity Analysis:
• Time complexity:
◦ Best: O(n log n)
◦ Average: O(n log n)
◦ Worst: O(n log n)
• Space complexity: O(1)

5. Merge Sort
Definition: Divides the array into halves, sorts them, and merges them back.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity:
◦ Best: O(n log n)
◦ Average: O(n log n)
◦ Worst: O(n log n)
• Space complexity: O(n)

2 4 3 1

2 4 3 1

2 4 3 1

2 4 1 3

1 2 3 4
Mastering Must-Know Algorithms for Interview Prep

6. Quick Sort
Definition: Divides the array into partitions based on a pivot and recursively sorts
them.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity:
◦ Best: O(n log n)
◦ Average: O(n log n)
◦ Worst: O(n2)
• Space complexity: O(n)

10 15 1 2 6 12 5 7

1 2 6 5 7 12 15 10
<7 pivot >7

1 2 5 6 10 12 15
<5 pivot >5 pivot >10

Searching Algorithms
1. Linear Search
Definition: Searches each element sequentially.
Complexity Analysis:
• Time complexity: O(n)
• Space complexity: O(1)

Find ‘20’

0 1 2 3 4 5 6 7 8

10 15 30 70 80 60 20 90 40

2. Binary Search
Definition: Searches a sorted array by dividing the search interval in half.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity: O(log n)
• Space complexity: O(1)
Target: 63 L M R

15 22 34 36 51 63 75
L M R

15 22 34 36 51 63 75

15 22 34 36 51 63 75
Mastering Must-Know Algorithms for Interview Prep

Tree Algorithms
1. Binary Search Tree
Definition: A tree structure where each node has at most two children, with the left
child having a smaller value and the right child a larger value.
Algorithmic Technique: Divide and Conquer
Complexity Analysis:
• Time complexity:
◦ Insertion/Deletion/Search: O(h) (h is the height of the tree)
• Space complexity:
◦ Iterative: O(1)
◦ Recursive: O(n)

Root

Root 45
Item = 20
(Item) < (root data)
Root = Root left 15 79

10 20 55 90

12 50

2. Depth-First Search
Definition: A traversal method that explores the tree by traveling as far as possible
along a branch before exploring the other branches.
◦ In-order: Left, Root, Right
◦ Pre-order: Root, Left, Right
◦ Post-order: Left, Right, Root
Complexity Analysis:
• Time complexity: O(n)
• Space complexity: O(h)

DFS - Pre-order

1 1 1

2 3 2 3 2 3

4 5 4 5 4 5
1 1 2 1 2 4

1 1

2 3 2 3

4 5 4 5
1 2 4 5 1 2 4 5 3
Mastering Must-Know Algorithms for Interview Prep

3. Breadth-First Search
Definition: Visits each level of the tree node by node.
Complexity Analysis:
• Time complexity: O(n)
• Space complexity: O(w), where w is the maximum width of the tree.

Layer 0 0 Source Node

1 2 3 Layer 1

4 5 6 7 Layer 2

Output: 0, 1, 2, 3, 4, 5, 6, 7

4. Heap (Min/Max)
Definition: A min/max heap is a complete binary tree and it is either an empty tree,
or the value at the root node is less/greater than the value at its children, and each
child (subtree) is a min/max heap.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity:
◦ Insert: O(log n)
◦ Remove: O(log n)
• Space complexity: O(1)

2 25
0 0

5 8 20 16
1 2 1 2

9 16 20 25 9 8 5 2
3 4 5 6 3 4 5 6
Min Heap Max Heap

Divide and Conquer

Definition: This technique involves breaking a problem into smaller subproblems,
solving each subproblem independently, and then combining the results. Common
examples include Merge Sort and Quicksort.
1. Merge Sort
Definition: Divides the array into halves, sorts them, and merges them back.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity: O(n log n)
• Space complexity: O(n)
Mastering Must-Know Algorithms for Interview Prep

2. Quick Sort
Definition: Divides the array into partitions based on a pivot and recursively sorts
them.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity:
◦ Best: O(n log n)
◦ Average: O(n log n)
◦ Worst: O(n2)
• Space complexity: O(log n)
3. Binary Search
Definition: Searches a sorted array by dividing the search interval in half and repeat
until the target value is found.
Algorithmic Technique: Divide and conquer
Complexity Analysis:
• Time complexity: O(log n)
• Space complexity: O(1)

4. Binary Search Tree

Definition: A tree structure where each node has at most two children, with the left
child having a smaller value and the right child a larger value.
Algorithmic Technique: Tree traversal, Graph algorithms
Complexity Analysis:
• Time complexity:
◦ Insertion/Deletion/Search: O(h) (h is the height of the tree)
• Space complexity: O(n)

Graph Algorithms
1. Algorithm Name: DFS
Definition: Explores as far as possible along each branch before backtracking.
Complexity Analysis:
• Time complexity: O(V + E)
• Space complexity: O(V)

2 5 2 5

Source
Node
1 3 6 1 3 6

4 4
Step 1: We start from Step 2: Node 1 and Node 2
node 1 and traverse to it’s are traversed. Go for
neighbor neighbor of Node 2
Mastering Must-Know Algorithms for Interview Prep

2. Algorithm Name: BFS

Definition: Explores all nodes at the present depth before moving on to nodes at
the next depth level.
Complexity Analysis:
• Time complexity: O(V + E)
• Space complexity: O(V)

2 5 2 5

Source
Node
1 3 6 1 3 6

4 4

Step 1: We start from Step 2: Node 1 and Node 2

node 1 and traverse to it’s are traversed
neighbor

3. Algorithm Name: Connected Components

Definition: Finds all connected components in an undirected graph.
Complexity Analysis:
• Time complexity: O(V + E)
• Space complexity: O(V)

0 1 4 0 1 4

6 6

3 2 5 3 2 5

Graph
Component 1 Component 2

4. Algorithm Name: Dijkstra’s Algorithm

Definition: Finds the shortest path from a source node to all other nodes in a graph
with non-negative weights.
Complexity Analysis:
• Time complexity: O((V + E) log V) using a priority queue
• Space complexity: O(V)

5
B A
7
2 8

1
D
C 6
Mastering Must-Know Algorithms for Interview Prep

5. Algorithm Name: Prim’s Algorithm

Definition: A greedy algorithm that finds the minimum spanning tree of a graph by
continuously adding the smallest edge that connects a new vertex to the growing
tree.
Algorithmic Technique: Greedy technique
Complexity Analysis:
• Time complexity:
◦ Using an adjacency matrix and simple arrays: O(V²).
◦ Using an adjacency list and a priority queue (min-heap): O((V + E) log V), where V
is the number of vertices and E is the number of edges.
• Space complexity: O(V + E), due to storing the graph representation.

5
4 3 4 3
9 8

3
5 1 3 6 5 1 3 6

4 7 4 7
1 2 1 2
2 2

6. Algorithm Name: Rabin-Karp Algorithm

Definition: A string-search algorithm that uses hashing to find patterns in a text by
comparing hash values of the pattern and substrings of the text for fast matching.
Complexity Analysis:
• Time complexity:
◦ Average case: O(n + m), where n is the length of the text and m is the length of
the pattern.
◦ Worst case: O(n * m) due to hash collisions.
• Space complexity: O(m), for storing the hash of the pattern and temporary
variables for hash computations.

Repeated DNA Sequences

Input

k 3

2 2

dna A G T C A G T T C A

1 1

Output

Sequence 1 A G T

Sequence 2 T C A
Mastering Must-Know Algorithms for Interview Prep

Dynamic Programming
1. Memoization
Definition: In this approach, the smallest problem is solved first, the results are
saved, and then larger subproblems are computed based on the evaluated results.
Take a Fibonacci series as an example.
Complexity Analysis:
• Time complexity: Reduces from exponential to linear in many cases
• Space complexity: Depends on the problem

F4

F3 F2

F2 F1 F1 F0

F1 F0

2. Tabulation
Definition: This approach uses recursion to break down a larger problem into
smaller subproblems. The bottom-up approach starts by solving the smallest
subproblem and then iterates progressively through larger subproblems to reach
the overall solution.
Complexity Analysis:
• Time complexity: Same as memoization
• Space complexity: Depends on the problem

i 0 1 2 3 4 5
lookup_table 0 0 0 0 0 0

i 0 1 2 3 4 5
lookup_table 0 1 0 0 0 0

i 0 1 2 3 4 5
lookup_table 0 1 1 2 3 0

i 0 1 2 3 4 5
lookup_table 0 1 1 2 3 5

3. Longest Common Substring

Definition: Finds the longest substring in two strings, used in dynamic programming
to solve problems like text comparison.
Complexity Analysis:
• Time complexity: O(n * m)
Mastering Must-Know Algorithms for Interview Prep

• Space complexity: O(n * m)

string1 C O D I N G I S F U N

string1 I S C O D I N G J O Y

4. Matrix-Chain Multiplication
Definition: A dynamic programming algorithm determining the most efficient way
to multiply a chain of matrices by minimizing the number of scalar multiplications.
Complexity Analysis:
• Time complexity: O(n3)
• Space complexity: O(n2)

m
6 6
15,125
5 5
11,875 10,500
4 4
9,375 7,125 5,375
3 3
7,875 4,375 2,500 3,500
2 2
15,750 2625 750 1000 5,000
1 1
0 0 0 0 0 0

A1 A2 A3 A4 A5 A6

Miscellaneous
1. Greedy Algorithms
Definition: Makes the locally optimal choice at each stage with the hope of finding
a global optimum.
Huffman Coding: A greedy algorithm used for lossless data compression.
Complexity Analysis:
• Time complexity: O(n log n)
• Space complexity: O(n)

A - 00
11
B - 01
0 1 C -1

5 6
0 1 C

2 3
A B
Mastering Must-Know Algorithms for Interview Prep

2. Mathematical Algorithms
Euclidean Algorithm (GCD): Finds the greatest common divisor of two integers.
Complexity Analysis:
• Time complexity: O(log(min(a, b)))
• Space complexity: O(1)

GCD Example of 136 and 600

600 = 4 x 136 + 56

136 = 2 x 56 + 24

56 = 2 x 24 + 8 GCF!

24 = 3 x 8 + 0 Done!

3. Backtracking
Definition: The process incrementally builds candidates to solutions and abandons
a candidate (backtracks) when it determines the candidate cannot lead to a valid
solution.
Complexity Analysis:
• Time complexity: Highly problem-dependent; often exponential
• Space complexity: Depends on recursion depth
N-Queens problem

Places queens on a chessboard individually and backtracks whenever it finds a

conflict.
Complexity Analysis:
• Time complexity: O(N!)
• Space complexity: O(N)

X X V
Mastering Must-Know Algorithms for Interview Prep

Permutations and Combinations

Recursively generates all permutations or combinations of a set and backtracks to

explore all possibilities.
Complexity Analysis:
• Time complexity:
◦ Permutations: O(N • N!)
◦ Combinations: O(n2)
• Space complexity: O(N)

Permutations Combinations A B C D
The number of ways The number of ways
Using 2 out of 4 boxes in a set
to arrange things to choose things
Possible selections of distinct
Order matters Order doesn’t matters Possible arrangements: 12 items: 6
AB BA CA AC AB = BA BC = CB
These are for lists These are for groups
BC CB DB BD AC = CA BD = DB
AD DA CD DC AD = DA CD = DC
Permutations Combinations