## Google Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

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

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

``````//Graph of connections, can only navigate in ascending timestamp order, need to find the connections as long as the edges go in increasing order (timestamp). Do DFS and add any found node to the closure

class Meeting {
int id1;
int id2;
int time;
}

class Node {
int id;

List<Edge> edges = new ArrayList<>();

Node(int id) {
this.id = id;
}
}

@AllArgsConstructor
class Edge {
Node next;
int timestamp;
}

Set<Integer> findWillKnowStory(List<Meeting> meetings, int idFirstToKnow) {
Node firstToKnowNode = buildGraph(meetings, idFirstToKnow);

//DFS
Set<Integer> result = new HashSet<>();
}

//T: O(N+M), S: O(N+M)
void addConnected(Node next, int currentTime, Set<Integer> result) {
if (result.contains(next.id)) return;

for (Edge e : next.edges) {
if (e.timestamp >= currentTime) {
}
//else ignore, not valid transition
}
}

//S: O(N*M) N nodes, M edges, from input L, O(L^2)
//T: O(L)
Node buildGraph(List<Meeting> meetings, int idFirstToKnow) {
Map<Integer, Node> nodes = new HashMap<>();

for (Meeting m : meetings) {
Node n1 = nodes.computeIfAbsent(m.id1, Node::new);
Node n2 = nodes.computeIfAbsent(m.id2, Node::new);

}

return nodes.get(idFirstToKnow);
}``````

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

``````private List<Integer> whoKnows(int[][] meetings, Integer personId) {
HashMap<Integer, LinkedList<Integer[]>> map = new HashMap<>();
int[] actualPerson = meetings[0];
for(int[] meeting: meetings) {
}

Set<Integer> visited = new HashSet<>();

queue.offer(new Integer[]{meetings[0][0],meetings[0][2]});

while(!queue.isEmpty()) {
Integer[] meeting = queue.poll();
for(Integer[] child: children) {
Integer id = child[0];
Integer time = child[1];
if(time >= meeting[1] ) {
queue.offer(child);
}
}
}

return new ArrayList<>(visited);
}``````

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

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

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

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

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

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

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

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

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

``````private static class Triple implements Comparable<Triple> {
public final int source;
public final int dest;
public final Long timestamp;

public static Triple of(int source, int dest, long timestamp) {
return new Triple(source, dest, timestamp);
}

public Triple(int source, int dest, long timestamp) {
this.source = source;
this.dest = dest;
this.timestamp = timestamp;
}

@Override
public int compareTo(Triple o) {
return this.timestamp.compareTo(o.timestamp);
}
}

//This solution has O(n*log n) complexity, to build the timeline.
public static Collection<Integer> gossip(Collection<Triple> talks) {
Map<Long, List<Pair<Integer, Integer>>> timeline = constructTimeline(talks);
Set<Integer> theyKnow = new HashSet<>();
theyKnow.add(1); //the first one to know.

var it = timeline.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Long, List<Pair<Integer, Integer>>> next = it.next();
System.out.printf("%s-%s%n", next.getKey(), next.getValue());

for (Pair<Integer, Integer> pair : next.getValue()) {
if (theyKnow.contains(pair.left)) {
}
}
}
return theyKnow;
}

private static Map<Long, List<Pair<Integer, Integer>>> constructTimeline(Collection<Triple> talks) {
Map<Long, List<Pair<Integer, Integer>>> result = new HashMap<>();

for (Triple triple : talks) {
List<Pair<Integer, Integer>> listOfKnowers = result.getOrDefault(triple.timestamp, new LinkedList<>());
result.put(triple.timestamp, listOfKnowers);
}

return result;
}``````

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

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

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

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

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

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)

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

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

This logic may not work if incoming order is something like (3,4,100),(2,3,100),(1,3,100),(4,5,200). Sorting must also consider persion_id_1 for it to work.

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

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

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

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

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

``````def whoKnowsTheStory(list_meetings,who_knows_first):
meetings = {who_knows_first: True}

list_meetings.sort(key=lambda tuple: tuple[2])

for p1,p2,timestamp in list_meetings:
if (meetings.get(p1) != None or meetings.get(p2) != None):
meetings[p1] = True
meetings[p2] = True

return list(meetings.keys())``````

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

Here is an algorithm that works correctly (Javascript)
*create a helper function, covertStrToArrays to convert the array of strings into an array of arrays,
making sure to remember the space after the comma in the string
* iterate over the array to convert each string element into an array
* sort the array ascending by the third element (the time)
* initialize an obj with the given number person as true
* initialize a timeElapsed and set it to 0
* use a while loop till array has length
*destructure the first element in the array as first, second, third
*if the third is less than the time elapsed then break the while loop
*if either of the person numbers are in the object
* add to the object the person not present in the object
* update time elapsed to the new time (third)
* delete this array element from the array
* return the keys of the object
*/

``````const convertStrToArray = (str) => {
let arr = str.slice(1, str.length - 1).split(', ');
return arr;
};

const personChain = (array, num) => {
// prepare the array

for (let i = 0; i < array.length; i++) {
let arr = convertStrToArray(array[i]);
array[i] = arr;
}
let numStr = num.toString(), obj = {};
obj[numStr] = true;

array.sort((a, b) => parseInt(a[2]) - parseInt(b[2]));
let timeElapsed = 0;
while (array.length > 0) {
let [first, second, third] = array[0];
if (third < timeElapsed) break;

if ((obj[first] || obj[second])) {
if (!obj[first]) obj[first] = true;
if (!obj[second]) obj[second] = true;
}
timeElapsed = third;
array.splice(0, 1);
}
return Object.keys(obj);
}
const arr1 = ["(1, 2, 100)", "(1, 3, 300)", "(2, 5, 400)", "(3, 4, 200)"];
console.log(personChain(arr1, 1));// [1, 2, 3, 5];

const arr2 = ["(1, 2, 100)", "(2, 3, 100)", "(4, 5, 100)"];
console.log(personChain(arr2, 2)); // [1, 2, 3]``````

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

``````#include<bits/stdc++.h>

using namespace std;

vector<int> ans;
void dfs(int s, int prev, vector<vector<pair<int, int>>> &g, vector<int> &vis) {
vis[s] = 1;
ans.push_back(s);
for(auto x: g[s]) {
if(!vis[x.first] && x.second>= prev) {
dfs(x.first, x.second, g, vis);
}
}
}

int main() {
int n;
cin>>n;

vector<vector<pair<int, int>>> g(2*n);

for(int i=0; i<n; i++) {
int u, v, wt;
cin>>u>>v>>wt;
g[u].push_back({v, wt});
}

vector<int> vis(2*n, 0);

dfs(1, 0, g, vis);

for(auto x: ans) cout<<x<<" ";
cout<<endl;
return 0;
}``````

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

``````#include<bits/stdc++.h>

using namespace std;

vector<int> ans;
void dfs(int s, int prev, vector<vector<pair<int, int>>> &g, vector<int> &vis) {
vis[s] = 1;
ans.push_back(s);
for(auto x: g[s]) {
if(!vis[x.first] && x.second>= prev) {
dfs(x.first, x.second, g, vis);
}
}
}

int main() {
int n;
cin>>n;

vector<vector<pair<int, int>>> g(2*n);

for(int i=0; i<n; i++) {
int u, v, wt;
cin>>u>>v>>wt;
g[u].push_back({v, wt});
}

vector<int> vis(2*n, 0);

dfs(1, 0, g, vis);

for(auto x: ans) cout<<x<<" ";
cout<<endl;
return 0;
}``````

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

lc-leetcode.com/problems/find-all-people-with-secret/

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

LC 2092. Find All People With Secret

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.