Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
//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<>();
addConnected(firstToKnowNode, -1, result);
}
//T: O(N+M), S: O(N+M)
void addConnected(Node next, int currentTime, Set<Integer> result) {
if (result.contains(next.id)) return;
result.add(next.id); //visit node
for (Edge e : next.edges) {
if (e.timestamp >= currentTime) {
addConnected(e.next, e.timestamp, result);
}
//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);
n1.edges.add(new Edge(n2, m.time));
n2.edges.add(new Edge(n1, m.time));
}
return nodes.get(idFirstToKnow);
}
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)
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)) {
theyKnow.add(pair.right);
}
}
}
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<>());
listOfKnowers.add(Pair.of(triple.source, triple.dest));
result.put(triple.timestamp, listOfKnowers);
}
return result;
}
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
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())
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]
#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;
}
#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;
}
Generate a graph of the form
- aksa June 28, 2021