Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Assuming that there are no possible cycles, my idea would be to solve it using backtracking. The algorithm has a runtime of O(n^n) but due to the search pruning I think it would be ok. Please let me know if someone has a better idea or if I made a mistake.
public int findLongestTupleChain(final List<CharPair> input) {
int retVal = 0;
if (input != null && input.size() > 0) {
retVal = findLongestTupleChain(input, input.get(0), 0) + 1;
}
return retVal;
}
private int findLongestTupleChain(
final List<CharPair> input,
final CharPair levelPair,
int level) {
int maxChain = 0;
CharPair current = null;
for (int i = 0; i < input.size(); ++i) {
current = input.get(i);
if (levelPair != current && levelPair.getRight() == current.getLeft()) {
maxChain = Math.max(level, findLongestTupleChain(input, current, level+1));
}
}
return Math.max(level, maxChain);
}
- amit May 26, 2014