CareerCup

{{public boolean getParentLst(Person child1, Person child2) {

if ((child1 == null && child2 != null) || (child1 != null && child2 == null)) {
return false;
}
List<Person> parent1 = child1.getParent();
List<Person> parent2 = child2.getParent();


Set<Person> child1Parent = bfsGraph(parent1);
Set<Person> child2Parent = bfsGraph(parent2);

return child1Parent.contains(child2Parent);
}

private Set<Person> bfsGraph(List<Person> personList) {
Set<Person> child1Parent = new HashSet<>();
if (!personList.isEmpty()) {
Queue<Person> bfsQueue1 = new LinkedList<>();
bfsQueue1.add(personList.get(0));
while (bfsQueue1.isEmpty()) {
Person p = bfsQueue1.poll();
if (p != null) {
child1Parent.add(p);
List<Person> grandParent = p.getParent();
for (Person gp : grandParent) {
bfsQueue1.add(gp);
}
}
}
}
return child1Parent;
}
}


class Person {
int id;
int parentID;
int relation;

public Person(int id, int parentID, int relation) {
this.id = id;
this.parentID = parentID;
this.relation = relation;
}

static List<Person> parent = new ArrayList<>();

static List<Person> getParent() {
return parent;
}
}}}

Better written code :

public class PersonRelation {


    public static boolean checkAreTheyRelated(String child1, String child2) {

        if ((child1 == null && child2 != null) || (child1 != null && child2 == null)) {
            return false;
        }
        List<Person> parent1 = Person.getParent(child1);
        List<Person> parent2 = Person.getParent(child2);

        Set<Person> child1Parent = bfsGraph(parent1);
        Set<Person> child2Parent = bfsGraph(parent2);

        if (!child1Parent.isEmpty() && !child2Parent.isEmpty()) {
            return child1Parent.contains(child2Parent);
        }
        return false;
    }

    private static Set<Person> bfsGraph(List<Person> personList) {
        Set<Person> child1Parent = new HashSet<>();
        Map<Person, Boolean> visited;
        Queue<Person> bfsQ;
        if (!personList.isEmpty()) {
            bfsQ = new LinkedList<>();
            bfsQ.add(personList.get(0));
            visited = new HashMap<>();
            visited.put(personList.get(0), true);
            while (!bfsQ.isEmpty()) {
                Person p = bfsQ.poll();
                if (p != null) {
                    child1Parent.add(p);
                    List<Person> grandParent = Person.getParent(p.parentID);
                    if (grandParent != null) {
                        for (Person gp : grandParent) {
                            if (!visited.containsKey(gp)) {
                                bfsQ.add(gp);
                            }
                        }
                    }
                }
            }
        }
        return child1Parent;
    }


    public static void main(String[] args) {
        System.out.println(checkAreTheyRelated("p1", "p2"));
    }
}


class Person {
    String id;
    String parentID;
    String relation;

    static Map<String, List<Person>> db = new LinkedHashMap<>();


    public Person(String id, String parentID, String relation) {
        this.id = id;
        this.parentID = parentID;
        this.relation = relation;
    }

    static {
        List<Person> l1 = new ArrayList<>();
        l1.add(new Person("1", "a", "parent"));
        db.put("p1", l1);

        List<Person> l2 = new ArrayList<>();
        l2.add(new Person("2", "c", "parent"));
        db.put("p2", l2);

        List<Person> l3 = new ArrayList<>();
        l3.add(new Person("3", "a1", "grandParent"));
        db.put("a", l3);

        List<Person> l4 = new ArrayList<>();
        l4.add(new Person("4", "a1", "grandParent"));
        db.put("c", l4);
    }

    static List<Person> getParent(String key) {
        if (key != null)
            return db.get(key);
        return null;
    }
}

/* 
In the current form, the problem is un-intelligible.
Formal problem should be as follows.
Let a list of persons be given in a format such that:
person -> parent_1, parent_2
item = [child, parent_1, parent_2]

where person, parent_1, parent_2 are (string/int) ids, 
and it means 'person' is a children of parent_1 & parent_2

Now, given two random parson p1, and p2 can we tell if they are related?
That also is not a formal statement.
Related, quite literally means if there is a path from p1 to p2.
Below is the code that sovles it:
*/

def are_related( person_1, person_2 , data ){
  def build_graph( parental_list ){}
    graph = dict()
    for ( item : parental_list ){
      #(child, p1, p2) = item
      if ( child !@ graph ){ graph[child] = set() }
      if ( p1 !@ graph ){ graph[p1] = set() }
      if ( p2 !@ graph ){ graph[p2] = set() }
      graph[child] += [ p1, p2 ]
      graph[p1] +=  child
      graph[p2] +=  child
    }
  }
  def path_exists( relation_graph, p1, p2 ){
   visited = set()
   queue = list()
   queue.enqueue(p1)
   while ( !empty(queue)){
     p = queue.poll()
     relations_of_p_order_1 = relation_graph[p]
     if ( p2 @  relations_of_p_order_1 ) return true
     unvisited = select( relations_of_p_order_1) where { $.o !@ visited }
     visited += p
     queue += unvisited
   }
   false // no path 
  }
  path_exists( build_graph(data), person_1, person_2 ) )
}