People who know story by time stamp -code

People who know story by time stamp is to simulate social network with graph data structure. This interview questions came from Google. Based on who tell who the story, find the people who know the story by the end. The graph can be represented as adjacent list. Here we use HashMap, in which the key is the person1, the value is the list of its neighbors. To build the graph, we add bi-directional edges between person1 and person2. To find all people is simply traversal of the graph. Similar to get suggested friend, we solve the question by depth first search and memoization.


graph dfs

The twist of this question is that there is a time stamp associated with the neighbor node. 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 time is 0. It is used as the input of the dfs recursion methods. In the loop of the all adjacent nodes of the current node, we use input time to compare with the adjacent node’s time stamp. If the input time is smaller, we can add this adjacent node as the output group who know the story. Otherwise, it is excluded. Then use the adjacent node’s timestamp as input to call dfs for its neighbor.

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

JavaScript

Python

Doodle

graph dfs 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)
Java coding interview questions(YouTube)

Comments are closed