Facebook Interview Question
SDE1sCountry: United States
it's a duplicate question, but I feel honored, it was adapted with this map representation ;-)
Actually it is NP hard and constist of two parts:
- find the shortest distances among all "@", S and G --> all pair shortest path on a map.
- find the shortest route between S and G while visiting each "@". Think of all the "@" as cities and imagine the distances among the cities were already calculated. It's clear there are count(@)! (factorial) options. It's as well clear if you calculated the shortest path properly, the triangle inequality holds. There are many approximation algorithms to the problem you can use then. But the exact solution is NP-hard.
It is a NP-hard problem, which is a famous problem called TSP problem. The main idea is that find all the @, and construct distance 2D array to represent the distance between different @s, and then use backtracking algorithm to get the final answer. If we just use dfs, and the time complexity is O(N!), but if we add DP algorithm, and then the time complexity if O(2^N)
- sudip.innovates September 21, 2017