## Google Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

Generate a graph of the form

```
Map<Integer, Pair<Integer, Integer>> graph = new HashMap<>();
// Each Pair<Integer, Integer> is the vertex and the time stamp of meeting
// Current node being processed.
Deque<Pair<Integer,Integer>> q= new ArrayDeque<>();
// Enque the root node and the time when it heard the story.
q.offer(new Pair<>(1, 0));
// Perform Level order/ BFS traversal starting at node 1.
// And keep track of the time w.r.t to root node and the time stamp of iteraction between
// node being processed and it's childern.
```

```
private List<Integer> whoKnows(int[][] meetings, Integer personId) {
HashMap<Integer, LinkedList<Integer[]>> map = new HashMap<>();
int[] actualPerson = meetings[0];
for(int[] meeting: meetings) {
map.put(meeting[0], map.getOrDefault(meeting[0], new LinkedList<>()));
map.get(meeting[0]).add(new Integer[]{meeting[1],meeting[2]});
}
Queue<Integer[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new Integer[]{meetings[0][0],meetings[0][2]});
visited.add(meetings[0][0]); //adding the actual person
while(!queue.isEmpty()) {
Integer[] meeting = queue.poll();
LinkedList<Integer[]> children = map.getOrDefault(meeting[0], new LinkedList<>());
for(Integer[] child: children) {
Integer id = child[0];
Integer time = child[1];
if(time >= meeting[1] ) {
queue.offer(child);
visited.add(id);
}
}
}
return new ArrayList<>(visited);
}
```

```
def findlist(input):
dictn={}
for pair in input:
dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
queue=[(0, 1)]
ans=[1]
while queue:
tmstmp, person = queue.pop(0)
if dictn.get(person) is not None:
for neighbour in dictn[person]:
if neighbour[0]>=tmstmp:
queue.append((neighbour[0], neighbour[1]))
ans.append(neighbour[1])
return ans
```

```
def findlist(input):
dictn={}
for pair in input:
dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
queue=[(0, 1)]
ans=[1]
while queue:
tmstmp, person = queue.pop(0)
if dictn.get(person) is not None:
for neighbour in dictn[person]:
if neighbour[0]>=tmstmp:
queue.append((neighbour[0], neighbour[1]))
ans.append(neighbour[1])
return ans
```

```
def findlist(input):
dictn={}
for pair in input:
dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
queue=[(0, 1)]
ans=[1]
while queue:
tmstmp, person = queue.pop(0)
if dictn.get(person) is not None:
for neighbour in dictn[person]:
if neighbour[0]>=tmstmp:
queue.append((neighbour[0], neighbour[1]))
ans.append(neighbour[1])
return ans
```

```
import os
def userInput():
items = []
noofelements = int(input('Enter range : '))
for rangeIndex in range(0, noofelements):
lst=[]
for rowIndex in range(0, 3):
print("***********Intiating information share list***********")
person1 = int(input("Enter First Person Id in this list >"))
person2 = int(input("Enter Second Person Id in this list >"))
timestamp = int(input("Enter the timestamp when the information was shared >"))
print("***********IInformation is saved lets continue for next item iteration in the list **********")
screen_clear()
lst.append(person1)
lst.append(person2)
lst.append(timestamp)
items.append(tuple(lst))
break
return items
def screen_clear():
# for mac and linux(here, os.name is 'posix')
if os.name == 'posix':
os.system('clear')
else:
# for windows platfrom
os.system('cls')
def personsSharingSameInformation(input):
dictn=[]
dictInd = 0
for index, tuple in enumerate(input):
tindex = 0
#first persons to know from the list
if (index ==0 ):
dictn.append(tuple[tindex])
dictn.append(tuple[tindex + 1])
continue
if (tuple[tindex] in dictn):
dictn.append(tuple[tindex])
dictn.append(tuple[tindex + 1])
final_list = list(dict.fromkeys(dictn).keys())
return final_list
if __name__ == '__main__':
items = userInput()
sortedByTimestamp = sorted(items, key=lambda tup: tup[2])
print("Information we are going to process >> ", sortedByTimestamp)
final_list = personsSharingSameInformation(sortedByTimestamp)
print(final_list)
```

class Node:

def __init__(self, val):

self.val = val

self.nodes = list()

def bfs(m , i, val, res):

node = m[i]

if i not in res:

res.add(i)

for n in node.nodes:

if n[0] >= val:

bfs(m, n[1].val, n[0], res)

if __name__ == '__main__':

m = {}

l = [ (2, 3, 100), (4, 5, 100), (1, 2, 100)]

for i in l:

if i[0] in m:

node = m[i[0]]

else:

node = Node(i[0])

m[i[0]] = node

if i[1] in m:

n = m[i[1]]

else:

n = Node(i[1])

m[i[1]] = n

node.nodes.append(tuple([i[2], n]))

res = set()

bfs(m, 1, 0, res)

print(res)

```
class Node:
def __init__(self, val):
self.val = val
self.nodes = list()
def bfs(m , i, val, res):
node = m[i]
if i not in res:
res.add(i)
for n in node.nodes:
if n[0] >= val:
bfs(m, n[1].val, n[0], res)
if __name__ == '__main__':
m = {}
l = [ (2, 3, 100), (4, 5, 100), (1, 2, 100)]
for i in l:
if i[0] in m:
node = m[i[0]]
else:
node = Node(i[0])
m[i[0]] = node
if i[1] in m:
n = m[i[1]]
else:
n = Node(i[1])
m[i[1]] = n
node.nodes.append(tuple([i[2], n]))
res = set()
bfs(m, 1, 0, res)
print(res)
```

simple steps to solve

1. sort the list by timestamps.

2. keep one hashmap of people who knows the story. initially put 1 person as true in the map.

3. go through the list.

a. check if the person_id_1 is in hashmap

b. if person_id_1 is in hashmap then put person_id_2 also in hashmap.

4. count all the persons in the hashmap.

5. return the list

complexity is O(nlogn) + O(n) + O(n) -> O(nlogn)

```
import heapq
def story_teller_seqeunce(meeting_list):
meetings = []
for meeting in meeting_list:
heapq.heappush(meetings, (meeting[2],
[meeting[0], meeting[1]])
final_meeting_sequence = []
while meetings:
current_meeting = heapq.heappop(q)
if current_meeting[0] in final_meeting_sequence:
current_meeting.append(meeting(1))
return final_meeting_sequence
```

```
space complexity = O(nlogn)
time complexity = O(n)
Can I make a tree out of it?
import heapq
def story_teller_seqeunce(meeting_list):
meetings = []
for meeting in meeting_list:
heapq.heappush(meetings, (meeting[2],
[meeting[0], meeting[1]])
final_meeting_sequence = []
while meetings:
current_meeting = heapq.heappop(q)
if current_meeting[0] in final_meeting_sequence:
current_meeting.append(meeting(1))
return final_meeting_sequence
```

- juliccr July 11, 2021