Question: Juspay Hackathon | 2023

Entering edit mode

Learn JS

JS newbie "A' wants to learn React from "B' and wants to know in his network who
can introduce him to B in the shortest time period

INPUT FORMAT

Total Members in UI Friend Network = N
Memberid1 = N1
Memberld2 = N2
Memberid3 = N3
MemberldN = Nn

Total Possible Edges = E
<Follower 1> <Following 1> <Time taken to send the message> = p1,q1t1l
<Follower 2> <Following 2><Time taken to send the message> = p2.q2.t2
<Follower 3> <Following 3> <Time taken to send the message> = p3.q3,t3
<Follower N> <Following N><Time taken to send the message = pn qn,tn
Follower (Ninja A) = A
Following (US expert B) = B

OUTPUT FORMAT

Shortest Time A takes to reach B

Sample Input
4
2
5
7
2 9 2
7 2 3
7 9 7
9 5 1
7
9
Sample Output

5

The Nagging React Newbie

The Nagging React newbie
A Nagging React newbie "B* is constantly troubling React expert "A'. React Expert 'A° needs to know the minimum set of people following him he needs to remove from his network to stop "B" from reaching out to him.

INPUT FORMAT

Total Members in UI Friend Network = N
Memberid1 = N1
Memberid2 = N2
Memberid3 = N3
MemberidN = Nn
Total Possible Edges = E
<Follower 1> <Following>
<Follower 2> <Following 2>
<Follower N> <Following N>

Set of mermaind "A" needs to be checked

Sample Input
4
2
5
7
9
4
2 9
7 2 
7 9 
9 5
7
9

Sample Output

2 7

Question 3

You are given a forest (it may contain a single tree or more than one tree) with N nodes.
Each node is given an integer value 0 to (N-1).
You have to find:
The depth of forest at which maximum number of nodes are present.
N can be very large. Aim for an algorithm with a time complexity of O(N).

INPUT FORMAT

An integer T, denoting the number of testcases, followed by 2T lines, as each testcase will
contain 2 lines.
First line or each testcase has the vale of N
Second line of each testcase has list of N values where the number at index i is the parent of
node i. The parent of root is -1. ( The index has the range (0, N-1]).

OUTPUT FORMAT

For each testcase given, output a single line that has the depth of forest at which maximum number of nodes are present. If multiple depths has same number of nodes, then deepest depth
should be selected.

SAMPLE INPUT
2

6

5 - 1 1 1 5 2

13

4 3 -1  -1  1 2 7  3 1 4 2 1 2 

SAMPLE OUTPUT

3

1

You are given a forest (it may contain a single tree or more than one tree) with N nodes. Each node is given an integer value 0 to (N-1).

You have to find:

Nearest common ancestor of two given nodes x1 and x2.

N can be very large. Aim for an algorithm with a time complexity of O(N).

INPUT FORMAT

An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines.

First line of each testcase has the value of N.
Second line of each testcase has list of N values where the number at index i is the parent of node i. The parent of root is -1. ( The index has the range (0, N-1]).
Third line for each testcase contains two integers within the range of (ON-1] whose common ancestor you have to find

SAMPLE INPUT

2
6
5-11 15 2
03
13
4 3 -1 -1 1 2 7 3 1 4 2 1 2
85
SAMPLE OUTPUT
1
-1

Converging Maze : Maximum Weight Node

Problem Description
You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie, entry/exit points are unidirectional doors like valves).
The cells are named with an integer value from 0 to N-1. You have to find:
Find the node number of maximum weight node (Weight of a node is the sum of node numbers of all nodes pointing to that node)

INPUT FORMAT

1. An integer T, denoting the number of testcases, followed by
2T lines, as each testcase will contain 2 lines.
2. The first line of each testcase has the number of cells N.
3. The second line of each testcase has a list of N values of the edge] array. edge(il contains the cell number that can be reached from of cell 'i' in one step. edge[i] is -I if the 'ith cell doesn't have an exit.

OUTPUT FORMAT

First line denotes the node number with maximum wight node.

Sample Input

1
23
4 4 1 4 13 8 8 8 0 8 14  9 15 11 -1 10 15  22 22 22 22 22 21


Sample Output 

22

ADD COMMENT • link

4

Entering edit mode

Solution for Question 1 using Djisktra Algorithm

using ll= long long int ;
int main() {
int n,m,src,destination;
cin>>n;
vector < ll > v(n);
map < ll ,ll > dis;
for (int i=0;i<n;i++) {
cin>>v[i];
dis[v[i]]=1e14;
}
cin>>m;
unordered_map < ll , vector <pair <ll,ll> > > g;
for (int i=0;i<m;i++) {
ll a,b,c;cin>>a>>b>>c;
g[a].push_back({b,c});

}
cin>>src>>destination;
dis[src]=0;
priority_queue < pair <ll,ll> , vector <pair <ll,ll> > , greater <pair <ll,ll> > > pq;
pq.push({0,src});
while (pq.size()) {
pair <ll,ll> tp=pq.top();pq.pop();
ll currV=tp.second,currD=tp.first;


for (auto &i:g[currV]) {

ll currN=i.first,wt=i.second;


if (dis[currN] > (currD+wt)) {

dis[currN]= currD+wt;
pq.push({dis[currN],currN});
}
}
}

cout<<dis[destination]<<endl;
return 0;

}