Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Not that simple though. 'All stops in a cluster should be at a distance not greater than D' - is difficult to implement by using algorithm of connected components.
Instead, I think, one has to calculate shortest paths of 'all pairs' first and need to keep only those nodes in a cluster which can be accessible via all other nodes(in that cluster) with a distance <= D and spare other nodes for other clusters probably.
connected component problem
- Anonymous July 12, 2015