Challenge - 5 Problems
Kahn's Algorithm Mastery
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Kahn's Algorithm on a Simple DAG
What is the output of the following Rust code implementing Kahn's Algorithm for topological sorting on the given graph?
DSA Rust
use std::collections::{VecDeque, HashMap};
fn kahn_topological_sort(graph: &HashMap<char, Vec<char>>) -> Vec<char> {
let mut in_degree = HashMap::new();
for &node in graph.keys() {
in_degree.insert(node, 0);
}
for edges in graph.values() {
for &v in edges {
*in_degree.entry(v).or_insert(0) += 1;
}
}
let mut queue = VecDeque::new();
for (&node, °) in &in_degree {
if deg == 0 {
queue.push_back(node);
}
}
let mut topo_order = Vec::new();
while let Some(u) = queue.pop_front() {
topo_order.push(u);
if let Some(neighbors) = graph.get(&u) {
for &v in neighbors {
let deg = in_degree.get_mut(&v).unwrap();
*deg -= 1;
if *deg == 0 {
queue.push_back(v);
}
}
}
}
topo_order
}
fn main() {
let mut graph = HashMap::new();
graph.insert('A', vec!['C']);
graph.insert('B', vec!['C', 'D']);
graph.insert('C', vec!['E']);
graph.insert('D', vec!['F']);
graph.insert('E', vec!['H', 'F']);
graph.insert('F', vec!['G']);
graph.insert('G', vec![]);
graph.insert('H', vec![]);
let result = kahn_topological_sort(&graph);
println!("{:?}", result);
}Attempts:
2 left
💡 Hint
Remember that nodes with zero incoming edges are processed first, and neighbors' in-degree is decreased accordingly.
✗ Incorrect
The algorithm starts with nodes having zero in-degree: 'A' and 'B'. It processes 'A' first (due to queue order), then 'B'. The order respects dependencies, so 'A' comes before 'C', 'B' before 'C' and 'D', and so on. The output is a valid topological order.
🧠 Conceptual
intermediate1:30remaining
Detecting Cycles with Kahn's Algorithm
What does it mean if Kahn's Algorithm finishes and the topological order contains fewer nodes than the graph?
Attempts:
2 left
💡 Hint
Think about what prevents nodes from having zero in-degree.
✗ Incorrect
If some nodes never reach zero in-degree, it means they are part of a cycle. Kahn's Algorithm cannot process nodes in cycles, so the output list is shorter than the total nodes.
🔧 Debug
advanced2:00remaining
Identify the Bug in Kahn's Algorithm Implementation
Given this Rust code snippet for Kahn's Algorithm, what is the bug causing incorrect topological order?
DSA Rust
use std::collections::{VecDeque, HashMap};
fn kahn_sort_bug(graph: &HashMap<char, Vec<char>>) -> Vec<char> {
let mut in_degree = HashMap::new();
for &node in graph.keys() {
in_degree.insert(node, 0);
}
for edges in graph.values() {
for &v in edges {
*in_degree.entry(v).or_insert(0) += 1;
}
}
let mut queue = VecDeque::new();
for (&node, °) in &in_degree {
if deg > 0 {
queue.push_back(node);
}
}
let mut topo_order = Vec::new();
while let Some(u) = queue.pop_front() {
topo_order.push(u);
if let Some(neighbors) = graph.get(&u) {
for &v in neighbors {
let deg = in_degree.get_mut(&v).unwrap();
*deg -= 1;
if *deg == 0 {
queue.push_back(v);
}
}
}
}
topo_order
}Attempts:
2 left
💡 Hint
Check the condition used to add nodes to the initial queue.
✗ Incorrect
The bug is that nodes with in-degree greater than zero are added to the queue initially, which is incorrect. Only nodes with zero in-degree should be enqueued first.
🚀 Application
advanced1:30remaining
Number of Possible Topological Orders
Given a DAG with nodes A, B, C where A points to C and B points to C, how many different valid topological orders exist?
Attempts:
2 left
💡 Hint
Consider the order constraints and which nodes can be swapped.
✗ Incorrect
Nodes A and B have no dependencies between them, so they can appear in any order before C. The valid orders are [A, B, C] and [B, A, C], so 2 in total.
❓ Predict Output
expert2:00remaining
Output of Kahn's Algorithm on a Graph with Cycle
What is the output of the following Rust code implementing Kahn's Algorithm on a graph containing a cycle?
DSA Rust
use std::collections::{VecDeque, HashMap};
fn kahn_topological_sort(graph: &HashMap<char, Vec<char>>) -> Vec<char> {
let mut in_degree = HashMap::new();
for &node in graph.keys() {
in_degree.insert(node, 0);
}
for edges in graph.values() {
for &v in edges {
*in_degree.entry(v).or_insert(0) += 1;
}
}
let mut queue = VecDeque::new();
for (&node, °) in &in_degree {
if deg == 0 {
queue.push_back(node);
}
}
let mut topo_order = Vec::new();
while let Some(u) = queue.pop_front() {
topo_order.push(u);
if let Some(neighbors) = graph.get(&u) {
for &v in neighbors {
let deg = in_degree.get_mut(&v).unwrap();
*deg -= 1;
if *deg == 0 {
queue.push_back(v);
}
}
}
}
topo_order
}
fn main() {
let mut graph = HashMap::new();
graph.insert('A', vec!['B']);
graph.insert('B', vec!['C']);
graph.insert('C', vec!['A']); // cycle A->B->C->A
let result = kahn_topological_sort(&graph);
println!("{:?}", result);
}Attempts:
2 left
💡 Hint
If a cycle exists, no node will have zero in-degree to start the process.
✗ Incorrect
Because of the cycle, all nodes have in-degree 1, so the initial queue is empty. The algorithm returns an empty vector indicating no valid topological order.