Practice
1. You are given a list of words sorted lexicographically in an unknown language. Your task is to determine the order of characters in this alien language. Which algorithmic approach guarantees an optimal solution to infer the character order from these constraints?
easy
Solution
Step 1: Understand problem constraints
The problem requires inferring a partial order of characters based on lexicographical ordering of words, which naturally forms a directed graph of precedence relations.Step 2: Identify suitable algorithm
Topological sort is the standard algorithm to find a linear order of nodes in a directed acyclic graph (DAG), which fits perfectly to infer character order from precedence edges.Final Answer:
Option A -> Option AQuick Check:
Topological sort handles partial orders and cycles correctly [OK]
Hint: Partial order inference -> topological sort [OK]
Common Mistakes:
- Assuming greedy approach works without cycle detection
- Confusing longest common subsequence with order inference
- Using brute force frequency counts which ignore order
2. Consider the following buggy code snippet for topological sort positions. Which line contains the subtle bug that can cause incorrect matrix construction?
medium
Solution
Step 1: Identify how in-degree is updated
In-degree should count incoming edges; incrementing in_degree[u] is incorrect because u is the source, not the target.Step 2: Understand impact of bug
Incorrect in-degree counts cause wrong zero in-degree nodes, breaking topological order and matrix correctness.Final Answer:
Option D -> Option DQuick Check:
Correct in-degree update is critical for cycle detection and ordering [OK]
Hint: In-degree counts incoming edges, not outgoing [OK]
Common Mistakes:
- Mixing source and target when updating in-degree
- Assuming graph edges are undirected
3. What is the time complexity of Kahn's Algorithm for finding a topological order in a graph with
V vertices and E edges?medium
Solution
Step 1: Identify operations on vertices and edges
Each vertex is enqueued and dequeued once; each edge is visited once to decrement in-degree.Step 2: Sum total work
Processing all vertices and edges once leads to O(V + E) time complexity.Final Answer:
Option C -> Option CQuick Check:
Linear time in graph size is standard for BFS topological sort [OK]
Hint: Each edge and vertex processed once -> O(V + E) [OK]
Common Mistakes:
- Assuming nested loops cause O(V*E)
- Confusing in-degree updates as scanning all vertices
- Thinking priority queues are used by default
4. The following code attempts to compute the minimum semesters to complete all courses using BFS topological sort. Identify the bug that causes incorrect results or infinite loops.
from collections import deque, defaultdict
def min_semesters_buggy(n, relations):
graph = defaultdict(list)
indegree = [0] * (n + 1)
for u, v in relations:
graph[u].append(v)
indegree[v] += 1
queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
semester = 0
processed = 0
while queue:
semester += 1
course = queue.popleft() # Bug here: processing one course per semester
processed += 1
for nei in graph[course]:
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return semester if processed == n else -1
medium
Solution
Step 1: Identify how courses are processed per semester
The code processes only one course per semester by popping one element from the queue.Step 2: Understand impact on semester count
Since multiple courses with zero indegree can be taken in parallel, processing one at a time inflates semester count incorrectly.Final Answer:
Option B -> Option BQuick Check:
Correct BFS processes all zero indegree nodes per semester [OK]
Hint: Process all zero indegree courses per semester, not one [OK]
Common Mistakes:
- Incrementing semester inside inner loop
- Not processing all available courses in one semester
- Incorrect indegree updates causing infinite loops
5. Examine the following buggy code snippet for sequence reconstruction using DFS postorder topological sort. Which line contains the subtle bug that can cause incorrect results when
seqs is missing some elements from org?medium
Solution
Step 1: Identify missing validation
The code does not check if all elements in org appear in seqs, which can cause false positives.Step 2: Confirm other lines are correct
Graph construction, cycle detection, and stack reversal are implemented correctly.Final Answer:
Option A -> Option AQuick Check:
Missing node presence check leads to incorrect true when seqs incomplete [OK]
Hint: Always verify all org nodes appear in seqs [OK]
Common Mistakes:
- Ignoring node presence check
- Misplacing cycle detection flags