Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Find if two people in a family tree are blood-related.
Solution:
- do a BFS from two sources, use one queue for it
- limit the search depth to max_generations to prevent
exploring too many people
the last point is a common problem with social network graphs and the
k'th degree relationships.
the frontier of first generation is 2^1, the 2nd generation is 2^2, if we explore
theoretically 20 generation we will visit 1 Mio people.
from collections import deque
def blood_related(a, b, max_generations=5):
generation = 0 # generation
queue = deque([(a, 0), (b, 1), (None, None)])
visited = [set(), set()]
while queue:
cur, src = queue.popleft()
if cur is None: # use none to indicate next generation in queue
generation += 1
if not queue or generation > max_generations:
break
queue.append((None, None))
elif cur in visited[src^1]:
return True
else:
visited[src].add(cur)
for parent in cur.parents:
if parent not in visited[src]:
queue.append((parent, src))
return False
class Person:
def __init__(self, name, mother = None, father = None):
self.parents = [mother, father]
self.name = name
g = Person('g', Person('h'), Person('i'))
f = Person('f')
d = Person('d')
e = Person('e')
c = Person('c', e, d)
a = Person('a', g, c)
b = Person('b', e, f)
print(blood_related(a,b))
print(blood_related(a,g))
print(blood_related(b,g))
class LinkedListNode:
def __init__(self, initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self, newdata):
self.data = newdata
def setNext(self, newnext):
self.next = newnext
node1 = LinkedListNode(1);
node2 = LinkedListNode(2);
node3 = LinkedListNode(3);
node4 = LinkedListNode(4);
node5 = LinkedListNode(5);
node6 = LinkedListNode(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
def countGroups(list, head):
nodes = set(list);
count = 0;
while not head == None:
if head.data in nodes:
count += 1;
while not head == None and head.data in nodes:
nodes.remove(head.data);
head = head.next;
if not head == None:
head = head.next;
return count;
print(countGroups([1,2, 3, 4, 5, 6], node1));
@NoOne:
this articles essence is "to find out if two people are blood-related only consider parent relationships because then your graph grows only by 2^generations whereas if you would navigate the children as well you would grow it by (2+#children)^generations ..."
when I solved the problem, I drew the graph on a paper and it was clear that only the parents are relevant, so I didn't even mention it ;-) nor did I have child relationships in the graph... of course, navigate the parents only... because it limits the growth of the frontier
I think one could even extend the algorithm by considering the birth date and only grow the youngest nodes upwards (using a prio-queue instead of a queue), so the frontier covers about the same birth years assuming our common anccestor children will not be too far apart (between 2 and 20 years, maybe extremes have 60 years (but only with common fathers ... :-)) ...
cool thanks for inspiring to think that way, not so much for the articles content ;-)
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
- aonecoding August 09, 2017