Hello Guys,

Could you share your thoughts on the following question:

Given an undirected graph with node values as string, and a path to follow, you have to find a path which is most similar to the input path.

For example, for the following graph:

Please note that the value in the input path could be completely different from any existing node. The task is to find out a path which resembles the most with the given path. There could be multiple possible outputs.

Input Path: ["KPG"->"DPS"->"SIN"->"AUH"]

Expected Output: ["KUL"->"DPS"->"CGK"->"AUH"]

In the above example, the least number of changes that you have to make is to replace KPG with KUL, and SIN with CGK.

Input Path: ["XXX", "TBS", "DME"]

Expected Output: ["ATH", "TBS", "DME"]

Update:

Pasting from comment for better explanation:

As you can see from the example, most similar path here means the actual path which deflects the least from the given path in the input. So, for the given example where input path is ["XXX"->"TBS"->"DME"], the starting node "XXX" is not there but the remaining nodes TBS and DME are there and they are in the same order, what I am trying to say here is that TBS->DME are already here, so I just need to replace "XXX" with something which connects to TBS. By replacing XXX, I am making only one change, which is the best that I could do in this case.

If the input would have been something like ["ATH"->"TBS"->"DME"], then as we can see that "ATH"->"TBS"->"DME" already exist in the graph and I don't need to make any change, so in this case output is same as input that is "ATH,TBS,DME".