CareerCup

The data structure to store the generation tree will have nodes defined as

public class Person {
	String name;
	ArrayList<Person> children = null;
	Person parent1;
	Person parent2;

	public Person(String personName, Person personParent1, Person personParent2) {
		name = personName;
		children = new ArrayList<Person>();
		parent1 = personParent1;
		parent2 = personParent2;
	}
	public Person getParent() { return parent; }
}

For 2 persons to be blood related, perform a Breadth First Traversal with the person as root and the parents as child nodes and store in a ArrayList.
Then for both the persons search is there is a common parent in the ArrayList.
If common parent found then, the persons are related, else not related.

Let's call the first generation individuals root.
For each individual in the population, maintain a reference to the list of his/her ancestor roots.
If two individuals share an ancestor roots, then they are blood related (at the very least, they share the blood of their common root ancestor)
If two individuals are blood related, then any root ancestor of their LCA (Lowest Common Ancestor) is a shared ancestor root.

Space: N (population size) * K (roots population size)
Time: K (intersection of two sorted lists of size at most K)

it is a graph, because two parents ... depends on the assumption, there can be many solutions.

First anonymous has it right, except I think you can make it more efficient by performing a dual BFS concurrently, and checking at each stage whether the next element to be processed exists in the set of ancestors of the other person:

public class Person {
  Person[] parents;
}

// naming for cousins is: n th cousin m times removed
// where n is the min generations to a common ancestor and m is the number of generations difference between the 2 cousins
// so this is going to be O((2^n+m)+2) which is still more efficient than dfs assuming the num generations in the population is > n+m
public boolean bloodRelated(Person p1, Person p2) {
  // simple search would go down p1's children/grandchildren/etc and see if we find p2
  // then vice versa
  // then worry about cousin style relationships
  // here we'd go up the parent tree on both until we found a common node (or ran out of data)

  // we could take this last approach anyway and it would get us a parent-child match too
  Set<Person> p1Ancestors = new HashSet<Person>();
  Set<Person> p2Ancestors = new HashSet<Person>();

  // so ideally here we're going to do BFS, but we're going to do 2 at once to try to minimise the depth we have to go
  List<Person> p1Discovered = new LinkedList<Person>();
  p1Discovered.add(p1);
  List<Person> p2Discovered = new LinkedList<Person>();
  p2Discovered.add(p2);

  while (!p1Discovered.isEmpty() || !p2Discovered.isEmpty()) {
    Person nextP1 = p1Discovered.remove(0);
    if (nextP1 != null) {
      if (p2Ancestors.contains(nextP1)) {
        return true;
      }

      for (Person parent : nextP1.parents) {
        p1Discovered.add(parent);
      }
      p1Ancestors.add(nextP1);
    }

    Person nextP2 = p2Discovered.remove(0);
    if (nextP2 != null) {
      if (p1Ancestors.contains(nextP2)) {
        return true;
      }

      for (Person parent : nextP2.parents) {
        p2Discovered.add(parent);
      }
      p2Ancestors.add(nextP2);
    }
  }
  return false;
}

This is actually a "connected components" problem. The "family tee" is actually a DAG and If two persons belong to the same connected component they are blood relatives.

Just rephrased problem of finding common ancestor of two nodes in a tree (an easy version, since there is parent pointer). Don't believe that Google asks such an easy questions

In the worstcase wont the root of the tree be the "LCA (least common ancestor)" of any 2 nodes in the tree? Wouldn't that mean that 2 people are ALWAYS related somehow?

Since we have the liberty of making the data structure , I will go like this


struct {
node *par1;
node *par2;
int magicnumber;
} node;
par1,par2 are obvious. While filling in the data , who is child of whom etc, you leave magicnumber as 0;
No lets say you get n queries for siblings or not.


for(i=0;i<n;i++)
{
input(node1,node2);
findsiblingsornot(node1,node2,i);
}
in findsiblingsornot() i serves as the query number or the magic number. Do a BFS/DFS using node1 as you like and fill magicnumber=querynumber in nodes you meet;
Next try to do BFS/DFS with node2 and if you get any node with magicnumer=i , you are done :)

Space here is just the space required to create DS. (if you still are considering extra space then its O(n). Time is O(N) too.

You dont need to worry about clearing up after your calls to the function.
Next time you call, you call with bigger magic number.

Isn't this same as lowest common ancestor?

public Person {
	String name;
	Person[] bloodRelation; //includes parents, siblings and children.
	@Override
	public boolean equals(Object obj) {
		return this.name.equals(((Person)obj).name);
	}
}

public boolean find (Person p1, Person p2, Set<Person> visited) {
	if(visited.contains(p1)) return false;
	if(p1.equals(p2)) return true;
	visited.add(p1)
	for(Person p : p1.bloodRelation) {
		if(find(p, p2, visited)) return true;
	}
	return false;
}

Let's consider the trees starting from the two persons and going through their ancestors. We run a DFS (or BFS) on each and collect their leaf nodes. If there is at least one common leaf node, the two persons are related. This technique reduces the space complexity.

n = number of people
k = number of root ancestors

Time complexity: O(n)
Space complexity: O(k)