Algorithms

Question 1

Difference between Depth first search (DFS) and Breadth first search (BFS) in graph traverse?

Answer 1

DFS - explores as far along each branch as possible before backtracking. It uses a stack (either explicitly or through recursion) and is memory efficient for deep graphs.

BFS - explores all neighbours at the present depth before moving on to nodes at the next depth level. It uses a queue and is memory efficient for wide graphs

Question 2

What are some common sorting algorithms and their time complexites

Answer 2

1. Quick sort - average time complexity is O(n log n), worst case is O(n^2)
2. Merge sort - time complexity is O(n log n) for all cases
3. Bubble sort - time complexity is O(n^2) for average and worst cases
4. Insertion sort - AV and worst case time complexity is O(n^2)