Merge words by head-tail chaining

Q: Merge words by head-tail chaining

This question evaluates graph-theoretic reasoning and string-manipulation skills, focusing on the ability to reason about ordering constraints, edge cases like self-loops and multiple identical relationships, and traversal over relationships between items.

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

Overview

Comments (0)