## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

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)){
node = node.next;
} else {
cnt++;
break;
}
}
}
return cnt;
}``````

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

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:
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))``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````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.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;

nodes = set(list);
count = 0;
count += 1;
return count;
print(countGroups([1,2, 3, 4, 5, 6], node1));``````

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

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.

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

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

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

``````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;
}``````

Name:

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

### Books

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

### Videos

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.

### 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.

### 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.