Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
of 3 vote

Looking for interview experience sharing and coaching?

Visit 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 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)) {
                    node =;
                } else {
        return cnt;

- aonecoding August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote

Find if two people in a family tree are blood-related.

- 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: 
            queue.append((None, None))
        elif cur in visited[src^1]: 
            return True
            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]    = 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)

- Chris August 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 2 vote

class LinkedListNode:
    def __init__(self, initdata): = initdata = None

    def getData(self):

    def getNext(self):

    def setData(self, newdata): = newdata

    def setNext(self, newnext): = newnext
node1 = LinkedListNode(1);
node2 = LinkedListNode(2);
node3 = LinkedListNode(3); 
node4 = LinkedListNode(4);
node5 = LinkedListNode(5); 
node6 = LinkedListNode(6); = node2; = node3; = node4; = node5; = node6;            
def countGroups(list, head):
    nodes = set(list);
    count = 0;
    while not head == None:
          if in nodes:      
             count += 1;
          while not head == None and in nodes:
                head =;
          if not head == None:      
             head =;
    return count;       
print(countGroups([1,2, 3, 4, 5, 6], node1));

- koustav.adorable August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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

- NoOne August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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

- Chris August 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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

- Alex August 29, 2017 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More