Practice
1. Consider the following Python code implementing Kahn's Algorithm for course scheduling. What is the return value of
canFinish(3, [[1,0],[2,1]]) after the while loop completes?easy
Solution
Step 1: Initialize graph and in-degree arrays
Graph: 0 -> [1], 1 -> [2], 2 -> []. In-degree: [0,1,1]. Queue starts with nodes having in-degree 0 -> [0].Step 2: Process queue and update count
Pop 0, count=1; decrement in-degree of 1 to 0, enqueue 1. Pop 1, count=2; decrement in-degree of 2 to 0, enqueue 2. Pop 2, count=3; queue empty.Final Answer:
Option B -> Option BQuick Check:
All courses processed, so return true [OK]
Hint: Count equals numCourses means no cycle [OK]
Common Mistakes:
- Off-by-one error in count increment
- Misunderstanding queue initialization
- Confusing in-degree decrement timing
2. You are given a directed acyclic graph with
n nodes and a list of edges. You want to find the smallest set of nodes such that starting a traversal from these nodes can reach every other node in the graph. Which approach guarantees finding this minimal set efficiently?easy
Solution
Step 1: Understand the problem constraints
The problem requires the minimal set of vertices from which all nodes are reachable. Nodes with zero in-degree are exactly those that no other node reaches, so they must be included.Step 2: Analyze approaches
Performing BFS from each node is inefficient. Dynamic programming counting paths is unnecessary. The minimal set is precisely all nodes with zero in-degree.Final Answer:
Option C -> Option CQuick Check:
Minimal set corresponds exactly to zero in-degree nodes [OK]
Hint: Minimal set corresponds exactly to zero in-degree nodes [OK]
Common Mistakes:
- Assuming BFS from each node is efficient
- Confusing zero in-degree nodes with minimal set without justification
- Using DP which is unnecessary here
3. What is the time complexity of the optimal approach using a single trust score array to find the town judge, given
n people and m trust pairs?medium
Solution
Step 1: Identify loops in the algorithm
The algorithm iterates once over all trust pairs (m) and then once over all people (n).Step 2: Combine complexities
Processing trust pairs is O(m), scanning people is O(n), total O(n + m).Final Answer:
Option D -> Option DQuick Check:
Single pass over trust and people arrays [OK]
Hint: Single pass over trust pairs and people yields O(n + m) [OK]
Common Mistakes:
- Assuming nested loops cause O(n*m)
- Confusing trust pairs count with people count
- Ignoring linear scans after trust processing
4. Examine the following buggy code snippet for bidirectional BFS to find the shortest path in a binary matrix. Which line contains the subtle bug that can cause infinite loops or incorrect results?
def visit(queue, visited, other_visited):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
if (nr, nc) in other_visited:
return visited[(r, c)] + other_visited[(nr, nc)]
if (nr, nc) not in visited:
queue.append((nr, nc)) # Bug here
# Missing visited marking here
return Nonemedium
Solution
Step 1: Identify visited marking usage
Visited must be marked when neighbor is enqueued to avoid revisiting.Step 2: Locate missing visited marking
Neighbor is appended to queue but not marked visited, causing possible infinite revisits.Final Answer:
Option D -> Option DQuick Check:
Marking visited on enqueue prevents infinite loops [OK]
Hint: Mark visited when enqueuing neighbors [OK]
Common Mistakes:
- Mark visited only when dequeuing
- Forgetting visited marking entirely
5. Suppose the Keys and Rooms problem is modified so that keys can be reused infinitely (i.e., you can revisit rooms multiple times). Which of the following changes to the algorithm is necessary to correctly determine if all rooms can be visited?
hard
Solution
Step 1: Understand infinite reuse of keys means cycles are possible
Without marking visited before enqueueing, BFS can enqueue the same room multiple times causing inefficiency or infinite loops.Step 2: Use BFS with visited marking on enqueue
Marking visited when enqueuing prevents multiple enqueues of the same room, ensuring termination and correctness.Step 3: Why other options fail
Removing visited causes infinite loops; resetting visited loses progress; limiting visits is inefficient and complex.Final Answer:
Option B -> Option BQuick Check:
BFS with visited marking on enqueue is standard for graphs with cycles [OK]
Hint: Mark visited when enqueuing in BFS to handle cycles [OK]
Common Mistakes:
- Removing visited causes infinite loops
- Resetting visited loses track of progress
- Counting visits is inefficient and unnecessary