swordx's blog

Most similar path in the graph
By swordx, history, 3 years ago, In English

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".

  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

What is "the most similar path"?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    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".

    I hope you got the idea.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      The reason this is being asked is that it is not clear what "deflects the least" or "most similar to" or "resembles the most" mean.

      What kind of changes are allowed? From your examples it's clear that I'm allowed to change the value of one of the elements.

      • Am I allowed to insert vertices between? For example, if the input is ATH -> TBS -> LED -> PRG and I output the path ATH -> TBS -> DME -> LED -> PRG, is it considered very similar, i.e. only one change apart?
      • Am I allowed to delete vertices?
      • Am I allowed to swap adjacent vertices, i.e. if I'm given TLV -> DME -> LCA and I output TLV -> LCA -> DME, is it counted as one change or more?

      Also, are the labels on the vertices unique? Can there be more than one TLV?

      To prevent such misunderstandings, I recommend to post the problem link (or if it is instead from real life or similar, you should have even more context to explain here).

      Also, there are no constraints or even rough estimates of "how many vertices", "how many edges", "how many queries", so it's really hard to help you here.

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

https://leetcode.com/problems/the-most-similar-path-in-a-graph/

this

There was another version which was asked in google interview. Also in amazon as far i remember.

https://leetcode.com/discuss/interview-question/751787/google-on-site-smallest-edit-distance-to-convert-path

→ Reply