Google | Onsite | Longest Chain Words
Summary
I recently interviewed onsite at Google, where I encountered a challenging data structures and algorithms problem. The core task involved identifying the longest possible chain of words based on specific rules for word transformation.
Full Experience
I had the opportunity to interview with Google for an onsite position. My interview experience primarily focused on my problem-solving skills, and I was given a complex algorithmic challenge. The interviewer presented a problem about forming word chains, which required careful consideration of several constraints regarding word length and character differences. I was also expected to discuss test cases and the time/space complexity of my solution.
Interview Questions (1)
Given a set of words, find the longest chain of words that can be made out of those words with the following rules:
- Each word in the chain is one letter longer than the previous word.
- Each word in the chain differs from the previous word only by its last letter.
Write test case's. Also, mention the Time and Space complexity for the same.
Constraint Examples:
den -> dent-> dents is valid (meets all constraints)
den -> dew is not valid (same length: 3 characters)
den -> cent is not valid (differs by 1'st char ['d' != 'c'])
Example:
Input: {ben, bent, dew, dents, dent, bet, den}
Output: 3 ({den, dent, dents})