Solve Data Structure Challenges with Python Algorithms
Company: Yahoo
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
You are given coding challenges in Python to manipulate simple data structures.
##### Question
Remove duplicates from a list of integers while preserving the original order. 2. Given a list of lowercase words, iteratively merge them into one long word by overlapping the last character of the current word with the first character of the next word when they are the same. Example: ['abc','rgn','ctr'] ➜ 'abctrgn'. Handle edge cases such as no overlap or multiple possible overlaps.
##### Hints
For Q1, collections.OrderedDict keeps insertion order; for Q2, simulate building the string and carefully update indices.
Quick Answer: This question evaluates proficiency in fundamental data structure manipulation and string-processing algorithms, specifically preserving insertion order during list deduplication and performing iterative overlap-based word merging.
You are given a list of non-empty lowercase words. Build a single string by consuming all words exactly once using this process: (1) Start with the first word in the list. (2) At each step, among the unused words, if there is any whose first character equals the current result's last character, choose the one that appears earliest in the original list and append it without duplicating the overlapping character (i.e., append word[1:]). (3) If no such word exists, append the earliest unused word in the original list as-is. (4) Continue until all words are used. Return the final string. If the list is empty, return an empty string.
Constraints
- 0 <= n <= 200000 where n is the number of words
- 1 <= len(words[i]) and words[i] consists only of lowercase letters 'a'..'z'
- Sum of lengths of all words <= 200000
- Only a 1-character overlap (last of current with first of next) is used
- Tie-breaker: always pick the earliest valid unused word by original index
Examples
Input:
Expected Output: abctrgn
Input:
Expected Output: abcdef
Input:
Expected Output: axaxb
Input:
Expected Output: a
Input:
Expected Output: hello
Hints
- Maintain, for each starting character, a queue of indices of words that start with that character.
- Track a pointer to the earliest unused index for the fallback case.
- When overlapping, append only word[1:] to avoid duplicating the shared character.
- Use a used[] array and lazily discard used indices from character queues.