# Mandatory Algorithms for Coding Interview

Basic algorithms that you must know if you want to crack your coding interview. In case you are starting to prepare for coding practice then make sure you learn all of these important algorightms. Get the source code for basic algorithms in JavaScript here

## Binary Search in Sorted Array

**O(log(n) time | O(1) space** |

See the Pen Binary Search Tree Implementation by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Kadane’s Algorithm

See the Pen Kadane's Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Moore’s Voting Algorithm

See the Pen Moore's Voting Algorithm | Majority Sum | Array by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Reverse Linked List

**O(n) time | O(1) space** |

See the Pen Reverse Linked List Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Flyod’s Cycle Detection Algorithm

See the Pen Untitled by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Sorting Algorithms

### Merge sort

In Merge sort since I need 2 Aux arrays. And it requires more space to solve merge sorting problem. Therefore, I will prefer

Linked Listdatastructure. Because, in linkedlist to store values, I do not need contigous memory slots. Hence optimizing memory usage.

**O(n log (n)) time | O(1) space** |

See the Pen Merge Sort Algorithm by Rupesh Tiwari (@rupeshtiwari) on CodePen.

### Quick Sort

**O(n log (n)) time | O( log (n) ) and wrost case O(n) space** |

Quicksort is best fit for sorting

Arrayssince it is completely in-place sorting. No auxilary arrays are requried. So no need to store contigous memory slots on computer.

See the Pen Quick Sort In-place Implementation: Answer by Rupesh Tiwari (@rupeshtiwari) on CodePen.

### Partition Logic

- All the element lesser than pivot are pushed to the left of the partition index (use swap)

## Tree Traversal

### Breadth-First Traversal(BFT)

**Whenever tree is Sparse use BFT**

**O(n) time | O(n) space** |

See the Pen Breadth First Traversal | Binary Tree by Rupesh Tiwari (@rupeshtiwari) on CodePen.

### Depth-First Traversal (DFT)

**O(n) time | O(n) space** |

See the Pen Depth-First Traversal | Binary Tree by Rupesh Tiwari (@rupeshtiwari) on CodePen.

## Binary Search Tree (BST)

See the Pen Binary Search Tree Implementation by Rupesh Tiwari (@rupeshtiwari) on CodePen.

### Insert in Binary Search Tree (BST)

**O(Log(n)) time | Space O(1)** |

For 1 insert operation, avg case is O(lgn) and worst case is O(n) For n insert operations, avg case is O(nlgn) and worst case is O(n^2)

### Remove Node from BST

**O(log n) time | space O(1)** |

### Search in BST

**O(log(n)) time | O(1)**

### Min Max and Height in BST

## Heap implementation

In the interview no one will ask you to implement heap. This excercise is for your coding skills imporvement. In the interview, you can use array instead of heap and explain the concept.

See the Pen Heaps: Implement Heap by Rupesh Tiwari (@rupeshtiwari) on CodePen.

### Insert node in the Heap

**O(log(n) time | O(1) space** |

### Revove root node from the Heap

**O(log(n) time | O(1) space** |

## Reference

*Thanks for reading my article till end. I hope you learned something special today. If you enjoyed this article then please share to your friends and if you have suggestions or thoughts to share with me then please write in the comment box.*

**💖 Say 👋 to me!**

Rupesh Tiwari

Founder of Fullstack Master

Email: rupesh.tiwari.info@gmail.com

Website: RupeshTiwari.com