Interview Q&A / Data Structures & Algorithms

1. How do you detect a cycle in a linked list?

   Use Floyd's tortoise and hare method. Move a slow pointer one step and a fast pointer two steps at a time. If the fast pointer reaches null, there is no cycle. If the two pointers ever meet, there is a cycle. It runs in O(n) time with O(1) extra space.

   IntermediateIn-depthCoding4 min read
2. What is the difference between BFS and DFS, and when would you use each?

   BFS (breadth-first search) explores a graph level by level using a queue, so it finds the shortest path in an unweighted graph. DFS (depth-first search) goes as deep as possible along one path before backtracking, using a stack or recursion, and suits cycle detection, topological sort and exploring all paths. Both take O(V + E) time.

   IntermediateIn-depthCoding4 min read