Competency asserted: Data Structures and Algorithms
Job title: Software Development Engineer (SDE II)
This problem is very similar to the Longuest Word problem of this best-seller interview book.
Problem Statement
Identify all combinations where one word can be composed of two or more words of the same list, and print them. You are given a (potentially large) list of words. Some of these are compounds, where all parts are also in the List. Example List:
Input: [rockstar, rock, stars, rocks, tar, star, rockstars, super, highway, high, way, superhighway]
Output: [[rock, star], [rocks, tar], [super, highway], [super, high, way],…]
Solution
See solution here.
Hints:
- Try simplifying this problem. What if you just needed to know the longest word made up of two other words in the list?
- If we wanted to know the longest word made up of other words in the list, then we could iterate over all words, from longest to shortest, checking if each could be made up of other words. To check this, we split the string in all possible locations.
- Extend the earlier idea to multiple words. Can we just break each word up in all possible ways?
- When you get recursive algorithms that are very inefficient, try looking for repeated subproblems!
See discussion in LeetCode.
Example feedback
Candidate 1
Vote: ? or ?
The candidate’s approach to coding a solution to identify composites (rockstar -> rock, star) from a list of words was below the SDE II bar. He quickly described the brute force approach but was reluctant to implement it because it was inefficient. He spent a bit of time trying to figure out a more efficient solution rather than following my coaching to implement brute force. I eventually simplified the problem to just pairs of words (rather than an arbitrary number) and solved that problem.
The candidate described a brute force exponential algorithm but did not want to implement it because it’s too inefficient. He then talked about a graph structure.
We simplified down to only focusing on compositions made of pairs of words, and he solved that using sets.
Learning
An interview is a problem-solving session with your interviewer(s). Follow your interviewer’s guidance. If she or he wants you to implement the brute force approach, just do it. But speak up your mind first. Clearly state that this is not the optimal solution but that you are willing to implement it. State that in real life, you would not implement a brute force solution first, as it may result in a waste of time.
Who knows what the interviewer has in mind. Maybe he is testing your ability to Deliver Results or your ability to make a decision quickly, Bias for Action. Or perhaps he wants you to challenge him, it’s hard to say, Have Backbone, Disagree and Commit. Clear any ambiguity.
