4 ms·
because they asked me to "say" a function for finding the longest common subsequence of a set of strings. That's rough, asking for a solution to an NP-hard pro
by blankity_blank 17y ago
because they asked me to "say" a function for finding the longest common subsequence of a set of strings.
That's rough, asking for a solution to an NP-hard problem over the phone? http://en.wikipedia.org/wiki/Longest_common_subsequence_problem http://en.wikipedia.org/wiki/Longest_common_subsequence_prob...
Or maybe they were just expecting you to say "for each combination of subsequences of each string, check if they are equal ..."
- mquander 17y agoWe may be mishearing their intended formulation, which could have been asking for the longest common substring (described here: difference is that subsequences don't have to be entirely contiguous, just in the same order.) http://en.wikipedia.org/wiki/Longest_common_substring_problem http://en.wikipedia.org/wiki/Longest_common_substring_proble... That's an interesting problem with some simple solutions worth understanding. I don't think it would be unrealistic to expect a high-quality programmer to be previously familiar with it, or, if not previously familiar, to be able to make progress toward the DP solution with some thought.
- plinkplonk 17y ago"We may be mishearing their intended formulation, which could have been asking for the longest common substring " Good Point. And asking a clarifying question would be a very strong positive in a candidate.
- deleted 17y ago[deleted]
- tocomment 17y agoNo, they wanted a working function. I used Python :-(