People who know story by time stamp is to simulate social network using graph data structure. The individual person is a node. The edge is from one person to another person when one tells another a story. The edge is bi-directional since both people know the story.
The graph can be represented as adjacent list. HashMap is used, in which the keys are all people who tell or be told the story. The value is the edge from the person (in key) to its neighbors. The value also contains a value of timestamp which marks when the story is told. The timestamp can be seen as “weight” in a weighted graph. At the end, we should find out all people who know the story by certain timestamp. The question can be solved with depth first search and memoization.
In this question, the timestamp associated with the neighbor node should be the driven factor. We have to compare the timestamp along the traversal path. Some people may not know the story if time sequence is not right. The initial timestamp value is 0.
The timestamp is transferred as a parameter in the DFS utility method. It should be compared with all the adjacent nodes’ timestamp. If the input time is smaller than the neighbor’s timestamp, that means these two people have the opportunity to tell the story when they meet. We add this adjacent node as the output group who know the story. Otherwise, he is excluded. At the end, we can find all people who know the story.
Google Interview Question (CareerCup):
When a person who knows it meets any other person, they immediately share the story with them. Initially, only person 1 knows the story. Given a list of meetings between people in a form of (person_1_id, person_2_id, timestamp) construct a list of the persons who will know the story at the very end.
Example: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 // The events could be out of order.
Person 2 will learn the story at the moment 100, person 3 — at the moment 300, person 5 — in the moment 400. Person 4 will never learn the story. So the answer is [1, 2, 3, 5].
Eg2: [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2
where the first parameter is array of the Persons meet at particular timestamp, second parameter is the PersonId who knows the story first.
Output: [1, 2, 3].
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import java.util.*; class Graph<T> { static class GraphNode<T> { T person2; int timestamp; //Time O(1), Space O(1) public GraphNode(T val, int ts) { person2 = val; this.timestamp = ts; } //Time O(1), Space O(1) public String toString() { return person2 + " " + timestamp; } } private Map<T, ArrayList<GraphNode<T>>> adj = new HashMap<>(); //Add edges, bi-direction, Time O(1), Space O(1) public void tellFriend(T src, T dest, int ts) { //add edge from src to dest adj.putIfAbsent(src, new ArrayList<GraphNode<T>>()); GraphNode<T> newNode = new GraphNode<>(dest, ts); adj.get(src).add(newNode); //add edge from dest to src adj.putIfAbsent(dest, new ArrayList<GraphNode<T>>()); newNode = new GraphNode<>(src, ts); adj.get(dest).add(newNode); } //DFS wrapper, call dfsUtil, Time O(V+E), Space O(V) //V is total number of people, E is number of connections public void dfs(T src) { Map<T, Boolean> visited = new HashMap<>();//memoization for (T key: adj.keySet()) visited.put(key, false); Set<T> group = new HashSet<>(); //output result group.add(src); dfsUtil(src, visited, 0, group); System.out.println("People who know story: " + group); } //DFS + memoization, recursion, Time O(V+E), Space O(V) private void dfsUtil(T v, Map<T,Boolean> visited, int time1, Set<T> group) { visited.put(v, true); for(GraphNode<T> ne: adj.get(v)) { T dest = ne.person2; int time2 = ne.timestamp; if (time1 <= time2 ) group.add(dest); if (!visited.get(dest)) dfsUtil(dest, visited, time2, group); } } //print graph in adjacency list, Time O(n) Space O(1) public void printGraph() { System.out.println("graph:"); for (T key: adj.keySet()) { System.out.println(key + "-" + adj.get(key)); } } } public class PeopleWhoKnowStoryByTimeStamp { public static void main(String args[]) { //case1: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 Graph<Integer> g = new Graph<>(); g.tellFriend(1, 2, 100); g.tellFriend(3, 4, 200); g.tellFriend(1, 3, 300); g.tellFriend(2, 5, 400); g.printGraph(); g.dfs(1); //case 2 [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2 Graph<Integer> g2 = new Graph<>(); g2.tellFriend(1, 2, 100); g2.tellFriend(2, 3, 100); g2.tellFriend(4, 5, 100); g2.printGraph(); g2.dfs(2); } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
class GraphNode { //Time O(1), Space O(1) constructor(val, ts) { this.person2 = val; this.timestamp = ts; } //Time O(1), Space O(1) toString() { return this.person2 + " " + this.timestamp; } } class Graph { //Time O(1), Space O(1) constructor() { this.adj = new Map(); } //add edge, bi-direction, Time O(1), Space O(1) tellFriend(src, dest, ts) { //add edge from src to dest if (!this.adj.has(src)) this.adj.set(src, new Array()); var newNode = new GraphNode(dest, ts); this.adj.get(src).push(newNode); //add edge from dest to src if (!this.adj.has(dest)) this.adj.set(dest, new Array()); newNode = new GraphNode(src, ts); this.adj.get(dest).push(newNode); } //DFS wrapper, call dfsUtil, Time O(V+E), Space O(V) //V is total number of people, E is number of connections dfs(src) { var visited = new Map();//memoization for (let key of this.adj.keys()) visited.set(key, false); var group = new Set(); //output result group.add(src); this.dfsUtil(src, visited, 0, group); console.log("People who know story: " + Array.from(group.values())); } //DFS + memoization, recursion, Time O(V+E), Space O(V) dfsUtil(v, visited, time1, group) { visited.set(v, true); for(let ne of this.adj.get(v)) { let dest = ne.person2; let time2 = ne.timestamp; if (time1 <= time2 ) group.add(dest); if (!visited.get(dest)) this.dfsUtil(dest, visited, time2, group); } } // print graph in adjacency list, Time O(n) Space O(1) printGraph() { console.log("graph:"); for (let key of this.adj.keys()) { console.log(key + "-" + this.adj.get(key)); } } } //case1: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 let g = new Graph(); g.tellFriend(1, 2, 100); g.tellFriend(3, 4, 200); g.tellFriend(1, 3, 300); g.tellFriend(2, 5, 400); g.printGraph(); g.dfs(1); //case 2 [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2 let g2 = new Graph(); g2.tellFriend(1, 2, 100); g2.tellFriend(2, 3, 100); g2.tellFriend(4, 5, 100); g2.printGraph(); g2.dfs(2); |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
class GraphNode : #Time O(1), Space O(1) def __init__(self, val, ts): self.person2 = val self.timestamp = ts #Time O(1), Space O(1) def __str__(self): return str(self.person2) + " " + str(self.timestamp) class Graph : #Time O(1), Space O(1) def __init__(self): self.adj = {} #add edge, bi-direction, Time O(1), Space O(1) def tellFriend(self, src, dest, ts) : #add edge from src to dest if src not in self.adj: self.adj[src]= [] newNode = GraphNode(dest, ts) self.adj[src].append(newNode) #add edge from dest to src if dest not in self.adj: self.adj[dest]= [] newNode = GraphNode(src, ts) self.adj[dest].append(newNode) #DFS wrapper, call dfsUtil, Time O(V+E), Space O(V) #V is total number of people, E is number of connections def dfs(self, src) : visited = {} # memoization for key in self.adj: visited[key]= False group = set() # output result group.add(src) self.dfsUtil(src, visited, 0, group) print("People who know story: " + str(group)) #DFS + memoization, recursion, Time O(V+E), Space O(V) def dfsUtil(self, v, visited, time1, group) : visited[v] = True for ne in self.adj[v]: dest = ne.person2 time2 = ne.timestamp if time1 <= time2 : group.add(dest) if visited[dest] == False: self.dfsUtil(dest, visited, time2, group) # print graph in adjacency list, Time O(n) Space O(1) def printGraph(self) : print("graph:") for key in self.adj: line = str(key) +"-" array = self.adj[key] for i in array: line += str(i) +", " print (line) # case1: [(1, 2, 100), (3,4, 200), (1,3, 300), (2,5, 400)], 1 g = Graph(); g.tellFriend(1, 2, 100) g.tellFriend(3, 4, 200) g.tellFriend(1, 3, 300) g.tellFriend(2, 5, 400) g.printGraph() g.dfs(1) #case 2 [(1, 2, 100), (2, 3, 100), (4, 5, 100)], 2 g2 = Graph(); g2.tellFriend(1, 2, 100) g2.tellFriend(2, 3, 100) g2.tellFriend(4, 5, 100) g2.printGraph() g2.dfs(2) |
Doodle
Output:
graph:
1-[2 100, 3 300]
2-[1 100, 5 400]
3-[4 200, 1 300]
4-[3 200]
5-[2 400]
People who know story: [1, 2, 3, 5]
graph:
1-[2 100]
2-[1 100, 3 100]
3-[2 100]
4-[5 100]
5-[4 100]
People who know story: [1, 2, 3]
O Notation:
Time complexity: O(V+E)
Space complexity: O(V)
V is total number of people, E is number of connections
Download PeopleWhoKnowStoryByTimeStamp.java
Download PeopleWhoKnowStoryByTimeStamp.js
Download PeopleWhoKnowStoryByTimeStamp.py
Java Coding Interview Pocket Book (2nd Edition)
Weighted graph implementation
