Coding

Find The Closest Marked Node

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

The number of nodes in a 0-indexed **directed **weighted graph, represented by the positive integer n, and the edges of a 0-indexed 2D array, where edges[i] = [ui, vi, wi], show that there is an directed edge from node ui to node vi with weight wi, are provided to you.

A node s and a node array **marked **are also provided to you; your job is to determine the smallest distance between s and any of the nodes in marked.

If there are no paths from s to any of the marked nodes, return -1; otherwise, return an integer representing the minimum distance between s and any node in marked.

Input : n = 5, s = 0, edges = [ [0, 1, 3], [0, 2, 4], [0, 3, 1], [0, 4, 2] ], marked = [1, 2, 3] **Output : **1 Explanation : The paths from node s (0) to marked nodes is as below : 0 to 1 -> 3 0 to 2 -> 4 0 to 3 -> 1 So the smallest distance is 1 i.e. from 0 to node 3.

Input : n = 5, s = 1, edges = [ [0, 1, 5], [0, 2, 4], [0, 3, 1], [0, 4, 2], [1, 2, 1], [2, 3, 1] ], marked = [3, 4] **Output : **2 Explanation : The paths from node s (1) to marked nodes is as below : 1 to 3 -> 1 + 1 -> 2. 1 to 4 -> -1 ( There is no path from 1 to 4). So the smallest distance is 2 i.e. from 1 to node 3.

Input : n = 5, s = 1, edges = [ [0, 1, 3], [0, 2, 4], [0, 3, 1], [0, 4, 2] ], marked = [2, 3, 4]

2 <= n <= 500
1 <= edges.length <= 104
edges[i].length = 3
0 <= edges[i][0], edges[i][1] <= n - 1
1 <= edges[i][2] <= 106
1 <= marked.length <= n - 1
0 <= s, marked[i] <= n - 1
s != marked[i]
marked[i] != marked[j] for every i != j
The graph might have repeated edges.
The graph is generated such that it has no self-loops.

cpp

class Solution {
    public:
        int minimumDistance(int n, vector<vector<int>>& edges, int s, vector<int>& marked) {
            //your code goes here
        }
};

java

class Solution{
    public static int minimumDistance(int n, List<int[]> edges, int s, List<Integer> marked) {
        //your code goes here
    }
}

python

class Solution:
    def minimum_distance(n, edges, s, marked):
        #your code goes here

javascript

class Solution{
    minimumDistance(n, edges, s, marked) {
        //your code goes here
    }
}

csharp

class Solution {
    public int minimumDistance(int n, List<int[]> edges, int s, int[] marked) {
        //your code goes here
    }
}

func minimumDistance(n int, edges [][]int, s int, marked []int) int {
	// your code goes here
}

Stuck? Show a way to structure it+

01Clarify directedness, source, and whether there are many queries
02Build an adjacency list and a boolean marked array
03Run BFS in the direction that supports the query pattern
04Return the first target distance or -1

Reference answer

Start by restating the input contract for Find The Closest Marked Node and testing the smallest boundary case before choosing the algorithm. Given an unweighted graph, find the minimum number of edges from a start node to any node marked as a target. Run a multi-source BFS from all marked nodes when queries ask distances to targets; otherwise BFS from the source and stop at the first marked node dequeued. Explain the invariant while coding, then show how each update preserves it. With an adjacency list, BFS takes O(V + E) time and O(V) auxiliary space for the queue, visited set, and distances. 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 would this change for weighted edges?
Tests: constraint adaptation
How would you answer many source queries?
Tests: follow-up reasoning

Hiring now

Get the Microsoft interview, not just the prep

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.

Or practice this question first

Next question