Hi Everyone!↵
↵
I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:↵
↵
<spoiler summary="Problem">↵
Given a dictionary of words, find the longest Chain of words↵
↵
A chain is formed when a string's last character is the same as any other string's first character.↵
↵
eg , {abd , csa , cdd , dxd , nmk}↵
Longest Chain : csa->abd->dxd↵
</spoiler>↵
↵
`I confirmed with the interviewer that there is a formation of the cycle in this, he told me that cycle formation is possible and whenever it happens you have to break the chain there since you don't want to repeat the same elements`↵
↵
As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.↵
↵
I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? So I wanted to ask what is the best possible complexity answer for this. ↵
↵
Thanks!↵
↵
↵
I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:↵
↵
<spoiler summary="Problem">↵
Given a dictionary of words, find the longest Chain of words↵
↵
A chain is formed when a string's last character is the same as any other string's first character.↵
↵
eg , {abd , csa , cdd , dxd , nmk}↵
Longest Chain : csa->abd->dxd↵
</spoiler>↵
↵
`I confirmed with the interviewer that there is a formation of the cycle in this, he told me that cycle formation is possible and whenever it happens you have to break the chain there since you don't want to repeat the same elements`↵
↵
As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.↵
↵
I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? So I wanted to ask what is the best possible complexity answer for this. ↵
↵
Thanks!↵
↵
