Currently, Relative Distance mentions that children can have one or two parents, but the test cases do not reflect the implications of this rule for the code.
I tried creating an issue on GitHub but it was closed automatically. How can I add the new test case?
A solution that currently passes all tests, but shouldn’t
A Java solution that only looks at a single branch of ancestors and therefore misses connections:
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
class RelativeDistance {
// <Child, Parent>
Map<String, String> parents;
RelativeDistance(Map<String, List<String>> familyTree) {
parents = new HashMap<>();
for (Map.Entry<String, List<String>> entry : familyTree.entrySet()) {
for (String child : entry.getValue())
parents.put(child, entry.getKey());
}
}
int degreeOfSeparation(String personA, String personB) {
List<String> ancestorsA = new ArrayList<>();
List<String> ancestorsB = new ArrayList<>();
String nextA = personA;
ancestorsA.add(nextA);
while (parents.containsKey(nextA)) {
nextA = parents.get(nextA);
ancestorsA.add(nextA);
}
String nextB = personB;
ancestorsB.add(nextB);
while (parents.containsKey(nextB)) {
nextB = parents.get(nextB);
ancestorsB.add(nextB);
}
if (ancestorsA.contains(personB)) {
return ancestorsA.indexOf(personB);
} else if (ancestorsB.contains(personA)) {
return ancestorsB.indexOf(personA);
} else {
for (String ancestor : ancestorsA) {
if (ancestorsB.contains(ancestor)) {
return ancestorsA.indexOf(ancestor) + ancestorsB.indexOf(ancestor) - 1;
}
}
}
return -1;
}
}
Counter example
┌──────────┐ ┌──────────┐ ┌──────────┐
│ Charles │ │ Andreas │ │ William │
└────┬─────┘ └──┬────┬──┘ └────┬─────┘
└──────┬───────┘ └──────┬──────┘
┌────┴─────┐ ┌─────┴─────┐
│ James │ │ Elizabeth │
└──────────┘ └───────────┘
The solution is not able to find the relative distance (1) between James and Elizabeth. Instead, it returns unrelated (-1).
Suggested test case
Family tree
Charles: [James]
Andreas: [James, Elizabeth]
William: [Elizabeth]
Expected output
degreeOfSeparation(James, Elizabeth) = 1
Relevance
The exercise appears to steer towards a BFS search algorithm. However, currently solutions that only check a single branch of ancestors pass all the tests.
