0
0
DSA Typescriptprogramming~20 mins

Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript - Practice Problems & Challenges

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Challenge - 5 Problems
🎖️
Kruskal MST Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate
2:00remaining
Output of MST edges after Kruskal's algorithm
What is the output of the edges included in the MST after running Kruskal's algorithm on the given graph?
DSA Typescript
interface Edge {
  src: number;
  dest: number;
  weight: number;
}

const edges: Edge[] = [
  {src: 0, dest: 1, weight: 10},
  {src: 0, dest: 2, weight: 6},
  {src: 0, dest: 3, weight: 5},
  {src: 1, dest: 3, weight: 15},
  {src: 2, dest: 3, weight: 4}
];

// After running Kruskal's MST, print edges in MST as array of [src, dest]
// in the order they are added.

// Assume vertices are 0 to 3.
A[[2,3],[0,3],[0,1]]
B[[0,3],[2,3],[1,3]]
C[[0,2],[2,3],[0,1]]
D[[0,1],[1,3],[2,3]]
Attempts:
2 left
💡 Hint
Sort edges by weight and pick edges that don't form a cycle.
🧠 Conceptual
intermediate
1:00remaining
Number of edges in MST for a graph with V vertices
For a connected graph with V vertices, how many edges will the Minimum Spanning Tree (MST) contain?
AV - 1
BV
CV + 1
DV * 2
Attempts:
2 left
💡 Hint
Think about how many edges connect all vertices without cycles.
🔧 Debug
advanced
2:00remaining
Identify the error in this Kruskal's algorithm snippet
What error will this TypeScript code produce when running Kruskal's algorithm?
DSA Typescript
class DisjointSet {
  parent: number[];
  constructor(n: number) {
    this.parent = Array(n).fill(-1);
  }
  find(x: number): number {
    if (this.parent[x] < 0) return x;
    return this.find(this.parent[x]);
  }
  union(a: number, b: number): void {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) {
      this.parent[rootB] = rootA;
    }
  }
}

// Usage omitted for brevity
ARuntime error due to union method missing return statement
BTypeError because parent array is not initialized
CNo error, code runs correctly
DStack overflow due to missing path compression in find()
Attempts:
2 left
💡 Hint
Consider what happens if find() calls itself repeatedly without optimization.
🚀 Application
advanced
3:00remaining
Minimum cost to connect all cities using Kruskal's MST
Given the weighted edges between cities, what is the minimum total cost to connect all cities using Kruskal's algorithm?
DSA Typescript
const edges = [
  {src: 0, dest: 1, weight: 7},
  {src: 0, dest: 3, weight: 5},
  {src: 1, dest: 2, weight: 8},
  {src: 1, dest: 3, weight: 9},
  {src: 1, dest: 4, weight: 7},
  {src: 2, dest: 4, weight: 5},
  {src: 3, dest: 4, weight: 15},
  {src: 3, dest: 5, weight: 6},
  {src: 4, dest: 5, weight: 8},
  {src: 4, dest: 6, weight: 9},
  {src: 5, dest: 6, weight: 11}
];

// Cities numbered 0 to 6
// Calculate total weight of MST
A35
B40
C39
D37
Attempts:
2 left
💡 Hint
Sort edges by weight and pick edges without cycles until all cities connected.
📝 Syntax
expert
1:30remaining
Identify the syntax error in this TypeScript Kruskal's implementation snippet
Which option correctly identifies the syntax error in the following code snippet?
DSA Typescript
const edges = [
  {src: 0, dest: 1, weight: 4},
  {src: 1, dest: 2, weight: 8},
  {src: 2, dest: 3, weight: 7},
];

edges.sort((a, b) => a.weight - b.weight)

for (const edge of edges) {
  if (disjointSet.find(edge.src) !== disjointSet.find(edge.dest)) {
    disjointSet.union(edge.src, edge.dest)
    mstEdges.push(edge)
  }
}
AArrow function in sort() missing curly braces
BdisjointSet is not declared or initialized
CmstEdges is not declared or initialized
DMissing semicolon after sort() call
Attempts:
2 left
💡 Hint
Check if all variables used are declared before use.