Google | Onsite | Longest Chain Words

Location
Onsite
Posted
8 Jul 2022
345 reads

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.

How it went

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.

Questions asked (1)

  1. 01

    Longest Word Chain with Single-Letter Suffix Difference

    Data Structures & Algorithms · Hard

    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})

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!