Merge words by head-tail chaining

Q: Merge words by head-tail chaining

This is a Coding & Algorithms interview question from Yahoo for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a list of lowercase words, merge them into a single string by repeatedly chaining words where the last character of the current string equals the first character of the next word. When chaining, do not duplicate the shared character. You may reorder the words arbitrarily. If multiple chains are possible, return any valid merged string; if no chain uses all words exactly once, return 'IMPOSSIBLE'. Example: ['abc','rgn','ctr'] -> 'abctrgn' because 'abc' + 'ctr' (c=c) -> 'abctr' and 'abctr' + 'rgn' (r=r) -> 'abctrgn'. Constraints: 1 <= n <= 1e5, 1 <= len(word) <= 50. Describe an algorithm that runs in near-linear time in total input size and implement it (hint: model words as edges in a 26-node directed multigraph and find an Eulerian path if in-/out-degree conditions and connectivity hold). Discuss edge cases such as multiple edges with identical endpoints, self-loops (e.g., 'aa'), and disconnected components.

Merge words by head-tail chaining

Comments (0)