Google Phone Screen

Anonymous User
2044
Jul 20, 2021
Jul 21, 2021

Given a list of words. Two words w1 and w2 are said to form a chain w1->w2 if w1 is prefix of w2 and len(w2) = len(w1) +1. Eg. abc -> abcd would form a chain. Find the longest chain from the list of words. Print the length as well as the chain.
Eg. ["den","ben", "dent", "dew", "dents"]
Here the longest chain is "den" -> "dent" -> "dents"

I came up with an approach of constructing a graph, where an edge would be present between w1 and w2 if w1 is proper prefix of w2. This graph would be a DAG. Do a toposort after constructing the DAG and find the longest chain.

I was able to code up the above solution, but interviewer did not tell me to dry run it on any test cases. He just went through the code.

Post coding up, he asked if we can optimize further and I suggested a trie approach. (Feeling silly I came up with Trie after the DAG one). The trie approach basically meant to insert all the words in the trie and then find the longest length of (isWord=True) among the nodes. Let me know if you would need more clarifications on this.

Interviewer seemed happy after the interview, but who knows what was under the facade of praise. I think I could have come up with Trie approach first and then coded it up, but I was scared to have less time for coding up the solution.

Comments (9)