Shortest Distance to Solar Houses | Dataford Interview Questions

Undirected connected graph of n houses; a subset (solarPanels) have power. Every other house pulls electricity along unit-length wires to its nearest solar house. Return dist[i] = shortest path length from house i to any solar house (0 if it is one).

Asked in the DSA stage. Brute force BFS per house, then multi-source BFS; working code expected.

Contract

Implement shortest_distances(n, edges, solarPanels). Houses are numbered 0 through n - 1; edges contains undirected pairs [u, v]; solarPanels contains house indices. Return a list of length n.

Constraints

1 <= n <= 1000
0 <= len(edges) <= n * (n - 1) / 2
Each edge is an undirected pair [u, v] with 0 <= u, v < n and u != v
The graph is connected
solarPanels is non-empty and contains unique house indices
All wire lengths are one

Function Signature

def shortest_distances(n, edges, solarPanels):

Your question is Shortest Distance to Solar Houses. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem