Algorithms

Question 1

What is Breadth-First Search (BFS)

Answer 1

A graph traversal algorithm that explores all neighbors of a node before moving on to the next level of neighbors.

Question 2

Space and Time Complexity of BFS?

Answer 2

O ( V + E )

O ( V ) - Each node is visited once
O ( E ) - Each edge is explored once

Question 3

Key Steps of BFS

Answer 3

1. Initialization
   - Queue containing starting node
   - Mark the starting node as visited
2. Main Loop
   - While the queue is not empty..
   – 1. dequeue front node of queue
   – 2. process current node
   – 3. for each unvisited neighbor of current node, A. mark neighbor visited, B. add neighbor to queue
3. Termination
   - The algo ends when all reachable nodes have been visited

Question 4

What is DFS ( Depth First Search ) ?

Answer 4

A graph traversal algorithm that explores each branch before backtracking.

Question 5

DFS Space/Time complexity

Answer 5

O ( E + V )

Question 6

Key Steps of DFS

Answer 6

1. Start at a node ( Root or Arbitrary
2. Mark Node as visited
3. Explore Neighbors ( recursively, with same method )
4. Backtrack, when all neighbors have been visited, explore other unexplored paths.

IE. The way water might fill a hollowed out root system. The water travels to the absolute depth first, and then begins to fill in the branches from the furthest bottom first working its way to the top.

Question 7

What is Sliding Window Algorithm?

Answer 7

Technique used for finding a contiguous subarray (or sublist) of a fixed size in an array.

Question 8

What is the Space/Time complexity of the Sliding Window Algorithm?

Answer 8

Time

O(n) traverses once for each shift.

Space

O(1) No additional space is required besides the initial input

Question 9

Key Steps of the Sliding Window Algorithm?

Answer 9

Initialization :
- Setup the first window by [ performing window function ]

Sliding: Add the next element, remove the last element to keep window fixed size.

Update Result After each slide, update the result (min, max, etc. )

Question 10

What is the Quick Sort Algo?

Question 11

What are the Key Steps of the Quick Sort

Answer 11

1. Picking a pivot element from the array.
2. Partitioning the remaining elements into two groups: those less than the pivot and those greater than the pivot.
3. Recursively sorting both groups.
4. Finally, combining the sorted groups and the pivot into a single sorted array.

Question 12

Space/Time complexity of Quick Sort

Answer 12

O(n log n) on average, but can degrade to O(n^2) if the pivot isn’t well chosen.