CareerCup

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!

//get the number of connected components in a list
    public int numberOfGroups(Set<Node> nodes) {
        Set<Node> visited = new HashSet<>();
        int cnt = 0;
        for(Node node: nodes) {
            while(!visited.contains(node)) {
                if(nodes.contains(node)){
                    visited.add(node);
                    node = node.next;
                } else {
                    cnt++;
                    break;
                }
            }
        }
        return cnt;
    }

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));

Duplicate from : question?id=4812957531766784
Bidirectional search is a terribly bad idea - due to this.
[ arxiv.org/pdf/1001.1819.pdf ]
Lookup " Parent Bidirectional Breadth Algorithm. ".
It is very very fast, and reasonably new in the market - 2009.

@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 ;-)

int GroupsCount(vector<Node const *> const &nodes)
{
	unordered_map<Node const *, int> counts;
	for (auto n : nodes) {
		++counts[n];
		++counts[n->next_];
	}
	int dups = 0;
	for (auto count : counts) {
		dups += count.second - 1;
	}
	return nodes.size() - dups;
}