Bird
Raised Fist0

Consider the following buggy code snippet for the alien dictionary problem. Which line contains the subtle bug that can cause incorrect results on inputs where a word is a prefix of the next word?

medium🐞 Bug Identification Q14 of Q15
Topological Sort - Alien Dictionary (Infer Character Order)
Consider the following buggy code snippet for the alien dictionary problem. Which line contains the subtle bug that can cause incorrect results on inputs where a word is a prefix of the next word?
from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        # BUG: Missing prefix invalid case check here
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)
ALine missing prefix invalid case check before edge addition
BLine initializing in_degree dictionary
CLine checking if w1[j] != w2[j] to add edge
DLine decrementing in_degree of neighbors in BFS loop
Step-by-Step Solution
Solution:
  1. Step 1: Identify prefix invalid case

    If a longer word is prefix of a shorter next word (e.g., "abc" before "ab"), the order is invalid and must return "".
  2. Step 2: Locate missing check

    The code lacks the check: if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]: return "" before adding edges.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing prefix check causes incorrect order or silent failure [OK]
Quick Trick: Prefix invalid case must be checked before edge addition [OK]
Common Mistakes:
MISTAKES
  • Ignoring prefix invalid case leads to wrong output
  • Misplacing in-degree initialization
  • Incorrectly decrementing in-degree in BFS
Trap Explanation:
PITFALL
  • The missing prefix check is subtle and often overlooked, causing silent logical errors.
Interviewer Note:
CONTEXT
  • Tests if candidate knows critical edge cases and where to place validation in code.
Master "Alien Dictionary (Infer Character Order)" 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