Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA Typescript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize an adjacency list for a graph with 3 nodes.

DSA Typescript

const graph: number[][] = [[], [], []];
graph[0].push([1]);

Drag options to blanks, or click blank then click option'

A2

B1

C0

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using node numbers outside the graph range.

Confusing node indices with edge weights.

We add node 1 as a neighbor to node 0 to represent an edge from 0 to 1.

2fill in blank

medium

Complete the code to check if a node has been visited in a graph traversal.

DSA Typescript

const visited: boolean[] = [false, false, false];
if (!visited[[1]]) {
  visited[1] = true;
}

Drag options to blanks, or click blank then click option'

A1

B0

C2

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using an index outside the visited array.

Checking the wrong node index.

We check if node 1 is visited before marking it true.

3fill in blank

hard

Fix the error in the code that tries to find the shortest path in a graph using BFS.

DSA Typescript

const queue: number[] = [];
queue.push(0);
while (queue.length > 0) {
  const node = queue.shift()[1];
  // process node
}

Drag options to blanks, or click blank then click option'

A();

B[0]

C()

D;

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting parentheses after shift.

Using incorrect syntax for method calls.

shift() is a function and must be called with parentheses to remove the first element.

4fill in blank

hard

Fill both blanks to update distances and enqueue neighbors during BFS shortest path search.

DSA Typescript

for (const neighbor of graph[node]) {
  if (distances[neighbor] === [1]) {
    distances[neighbor] = distances[node] [2] 1;
    queue.push(neighbor);
  }
}

Drag options to blanks, or click blank then click option'

A-1

B+

C0

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of -1 for unvisited check.

Subtracting 1 instead of adding 1 to distance.

Distances start at -1 meaning unvisited. We add 1 to the current node's distance to update neighbor's distance.

5fill in blank

hard

Fill all three blanks to create a function that returns the shortest path length from start to end in a graph.

DSA Typescript

function shortestPath(graph: number[][], start: number, end: number): number {
  const distances = Array(graph.length).fill([1]);
  const queue: number[] = [];
  distances[start] = 0;
  queue.push(start);
  while (queue.length > 0) {
    const node = queue.shift()[2];
    if (node === end) return distances[node];
    for (const neighbor of graph[node]) {
      if (distances[neighbor] === [3]) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return -1;
}

Drag options to blanks, or click blank then click option'

A-1

B()

C0

D;

Attempts:

3 left

💡 Hint

Common Mistakes

Not initializing distances with -1.

Forgetting parentheses on shift.

Checking for 0 instead of -1 for unvisited.

Initialize distances with -1 for unvisited nodes, call shift() with parentheses, and check for -1 to find unvisited neighbors.