Bird
Raised Fist0

Identify the subtle bug that causes incorrect results on some inputs.

medium🐞 Bug Identification Q7 of Q15
Topological Sort - Longest Path With Different Adjacent Characters
The following code attempts to find the longest path with different adjacent characters in a DAG. Identify the subtle bug that causes incorrect results on some inputs. ```python from collections import defaultdict, deque def longest_path_buggy(n, edges, s): graph = defaultdict(list) indegree = [0] * n for u, v in edges: graph[u].append(v) indegree[v] += 1 queue = deque([i for i in range(n) if indegree[i] == 0]) topo_order = [] while queue: node = queue.popleft() topo_order.append(node) for nei in graph[node]: indegree[nei] -= 1 if indegree[nei] == 0: queue.append(nei) dp = [1] * n for node in topo_order: for nei in graph[node]: dp[nei] = max(dp[nei], dp[node] + 1) # BUG: missing character check return max(dp) ```
ANot detecting cycles before processing topological order
BMissing check that adjacent nodes have different characters before updating dp
CIncorrect initialization of dp array with zeros instead of ones
DNot handling disconnected graph components
Step-by-Step Solution
Solution:
  1. Step 1: Review dp update line

    dp[nei] is updated without verifying s[nei] != s[node], violating problem constraint.
  2. Step 2: Consequence of missing check

    Paths with same adjacent characters are counted, leading to incorrect longest path length.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Character difference check is essential in dp update [OK]
Quick Trick: Check character difference before dp update [OK]
Common Mistakes:
MISTAKES
  • Forgetting adjacency character constraint
  • Assuming topological order alone suffices
Trap Explanation:
PITFALL
  • Candidates often overlook the character difference condition in dp updates, causing subtle bugs.
Interviewer Note:
CONTEXT
  • Tests attention to problem constraints and correctness in DP updates.
Master "Longest Path With Different Adjacent Characters" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes