Compass Interview Question: Write a function that, given ... | Glassdoor

Interview Question

Software Engineer Interview New York, NY

Write a function that, given an inventory of titles (say

  movies), and a starting movie title, returns the longest list of titles (in which each title appears only once) where the first word of the next title in the list is equal to the last word of the preceding title.

Interview Answer

4 Answers


The solution the interview was looking for is a standard recursive approach but its performance is terrible, on the order of O(n!) But essentially you want to keep track of seen movies across recursive calls, for each call winnow the candidate titles down by filtering those without a matching start word, and then recurse, tracking the longest path as you do so.

Interview Candidate on Jan 30, 2016

Something like this:

[The removal of the movie from the seen list in the caller is yucky, though.]

Adam on Feb 4, 2016

Isn't this basically a longest path problem that can be represented with a directed graph? In that case the runtime would be O(n)

Alex on Feb 17, 2016

["End of time", "Time to go", "Go to end"] would be a cycle. And the longest path problem for a graph is an NP-hard problem which would mean this cannot be solved in polynomial time. This might have been a trick question to see if the interviewee would understand what question is being asked.

@Alex on Feb 17, 2016 on Jul 8, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.