Merge words by head-tail chaining
Company: Yahoo
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Overview: 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.