Micro-questions over the BFS pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
This bank is about recognising the problem shape. The mechanics are in the BFS bank.
A. The shape
1. What phrasing almost always means BFS?
Answer
“Minimum steps / levels / time to reach X” in an unweighted setting.
2. Give the physical metaphor.
Answer
Ripples expanding outward from a pebble dropped in water.
3. Give the social-network illustration.
Answer
Finding the shortest connection path between two people — check all paths of length 1, then length 2, and so on.
B. Level-order
4. What is the key trick that turns plain BFS into level-order BFS?
Answer
level_size = len(queue) — a snapshot of exactly how many nodes are in this level, taken before processing any of them.
5. What happens without it?
Answer
You process the nodes but lose track of which level each one belonged to.
6. Why is len(queue) exactly the level width at that moment?
Answer
Because at the top of the iteration the queue holds every node of the current level and nothing else — the previous level has all been popped and the next level has not been enqueued yet.
C. Multi-source BFS
7. What is multi-source BFS?
Answer
Starting BFS from all initial sources simultaneously — putting all of them in the queue at distance 0 before the loop begins.
8. What does it compute?
Answer
For every cell, the distance to the nearest source — in one pass, at the same cost as a single-source run.
9. Give the canonical problem.
Answer
Rotting Oranges — every rotten orange starts in the queue at once, and they spread simultaneously.
10. Why would running single-source BFS from each source be wrong as well as slow?
Answer
Slow because it is passes — and you would then have to take the minimum across all of them per cell, which multi-source gives you for free by construction.
11. What must you check at the end of Rotting Oranges?
Answer
Whether any fresh oranges remain — if so, they were unreachable and the answer is , not the elapsed minutes.
D. Trade-offs
12. What does BFS guarantee that DFS does not?
Answer
Shortest paths in unweighted graphs.
13. Why does BFS guarantee that?
Answer
It exhausts distance entirely before touching , so the first time it reaches a node it has done so by the fewest possible edges.
14. What is BFS’s memory cost, and on what shape is it worst?
Answer
The queue can grow to — worst on wide graphs, where DFS would use far less.
15. Summarise the pattern in one sentence.
Answer
If the question is “how few steps”, expand in rings with a queue — snapshot the level size when levels matter, and seed every source at once when the answer is a distance to the nearest of many.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- BFS Pattern — the pattern
- Breadth-First Search — Question Bank — the mechanics
- DFS Pattern — Question Bank
- Matrix Traversal — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering