CareerCup

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.

//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;
}

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

LC 2092. Find All People With Secret