Coding

Shortest path in undirected graph with unit weights

Asked at

BitGo

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a Undirected Graph of N vertices from 0 to N-1 and M edges and a 2D Integer array edges, where there is a edge from vertex edges[i][0] to vertex edges[i][1] of unit weight.

Find the shortest path from the source to all other nodes in this graph. In this problem statement, we have assumed the source vertex to be ‘0’. If a vertex is unreachable from the source node, then return -1 for that vertex.

Input: n = 9, m = 10, edges = [[0,1],[0,3],[3,4],[4,5],[5, 6],[1,2],[2,6],[6,7],[7,8],[6,8]]

Output: 0 1 2 1 2 3 3 4 4

Explanation: The above output array shows the shortest path to all the nodes from the source vertex (0), Dist[0] = 0, Dist[1] = 1 , Dist[2] = 2 , …. Dist[8] = 4.Where Dist[node] is the shortest path between src and the node. For a node, if the value of Dist[node]= -1, then we conclude that the node is unreachable from the src node.

Input: n = 8, m = 10, edges =[[1,0],[2,1],[0,3],[3,7],[3,4],[7,4],[7,6],[4,5],[4,6],[6,5]]

Output: 0 1 2 1 2 3 3 2

Explanation: The above output list shows the shortest path to all the nodes from the source vertex (0), Dist[0] = 0, Dist[1] = 1, Dist[2] = 2,.....Dist[7] = 2.

Input: n = 3, m = 1, edges = [[1,2]]

1<=n,m<=104
0<=edges[i][j]<=n-1

cpp

class Solution {
  public:
    vector<int> shortestPath(vector<vector<int>>& edges, int N,int M){
   
    }
};

java

class Solution {
    public int[] shortestPath(int[][] edges, int N, int M) {
 
    }
}

python

class Solution:
    def shortestPath(self, edges, N, M):

javascript

class Solution {
    shortestPath(edges, N, M) {
   
    }
}

csharp

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public List<int> shortestPath(List<List<int>> edges, int N, int M)
    {
      
    }
}

func shortestPath(edges [][]int, N int, M int) []int {
	
}

Stuck? Show a way to structure it+

01Build an undirected adjacency list
02Initialize all distances as unvisited
03Enqueue the source and mark it immediately
04Visit each neighbor once and assign distance plus one

Reference answer

Start by restating the input contract for Shortest path in undirected graph with unit weights and testing the smallest boundary case before choosing the algorithm. Every edge costs one, so BFS explores vertices in nondecreasing distance. Start with the source at distance zero; when first discovering a neighbor, assign current distance plus one and enqueue it. Those first assignments are shortest distances. Explain the invariant while coding, then show how each update preserves it. BFS is O(V + E) time and O(V) auxiliary space for the queue, distances, and visited state. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How do you return the actual shortest path?
Tests: implementation extension
What changes when edges have weights?
Tests: constraint adaptation

Hiring now

BitGo has 44 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer - Mobile Backend
Toronto, Ontario, Canada
Backend Engineer E3 - India
India
Backend Engineer E3 - Ecosystem
India

Or practice this question first

Next question