Juspay Interview Question
Software DevelopersCountry: India
class path
{
public static void main(String [] args)
{
Scanner scnr=new Scanner(System.in);
int n=scnr.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=scnr.nextInt();
}
int path=-1;
int j;
for(int i=0;i<n;i++)
{ j=i;
int count=0;
while(true)
{
count++;
if(a[j]==-1)
{
break;
}
else if(i==a[j])
{
if(count>path)
path=count;
break;
}
else
{ int temp=j;
j=a[j];
a[temp]=-1;
}
}
}
System.out.println("my path: "+path);
}
}
class path
{
public static void main(String [] args)
{
Scanner scnr=new Scanner(System.in);
int n=scnr.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=scnr.nextInt();
}
int path=-1;
int j;
for(int i=0;i<n;i++)
{ j=i;
int count=0;
while(true)
{
count++;
if(a[j]==-1)
{
break;
}
else if(i==a[j])
{
if(count>path)
path=count;
break;
}
else
{ int temp=j;
j=a[j];
a[temp]=-1;
}
}
}
System.out.println("my path: "+path);
}
}
- Sangeet Moy August 07, 2017 | FlagReply
#include<bits/stdc++.h>
using namespace std;
int dist[23];
bool vis[23];
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
// adj[v].push_back(u);
}
void dfs(vector<int> adj[], int node, int d, int src)
{
vis[node] = true;
for (auto child : adj[node]) {
if (!vis[child])dfs(adj, child, d + 1, src);
else if (child == src)dist[child] = max(dist[child], d + 1);
}
vis[node] = false;
}
int main()
{
int V;
cin >> V;
// int V = 7;
memset(vis, false, sizeof(vis));
memset(dist, false, sizeof(dist));
vector<int> adj[V];
for (int i = 0; i < V; ++i)
{
int to; cin >> to;
if (to != -1)addEdge(adj, i, to);
}
for (int i = 0; i < V; ++i)
{
dfs(adj, i, 0, i);
}
int ans = INT_MIN;
for (int i = 0; i < V; ++i)
{
ans = max(ans, dist[i]);
}
cout << ans;
// printGraph(adj, V);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dist[23];
bool vis[23];
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
// adj[v].push_back(u);
}
void dfs(vector<int> adj[], int node, int d, int src)
{
vis[node] = true;
for (auto child : adj[node]) {
if (!vis[child])dfs(adj, child, d + 1, src);
else if (child == src)dist[child] = max(dist[child], d + 1);
}
vis[node] = false;
}
int main()
{
int V;
cin >> V;
// int V = 7;
memset(vis, false, sizeof(vis));
memset(dist, false, sizeof(dist));
vector<int> adj[V];
for (int i = 0; i < V; ++i)
{
int to; cin >> to;
if (to != -1)addEdge(adj, i, to);
}
for (int i = 0; i < V; ++i)
{
dfs(adj, i, 0, i);
}
int ans = INT_MIN;
for (int i = 0; i < V; ++i)
{
ans = max(ans, dist[i]);
}
cout << ans;
// printGraph(adj, V);
return 0;
}
function largestCycle(edges)
{
var result, visitedFrom, startCell, cell, cells;
result = [];
visitedFrom = Array(edges.length).fill(-1);
for (startCell = 0; startCell<edges.length; startCell++)
{
cells = [];
for
(cell=startCell;cell>-1&&visitedFrom[cell]===-1; cell = edges[cell])
{
visitedFrom[cell] = startCell;
cells.push(cell);
}
if (cell > -1 && visitedFrom[cell] ===startCell)
{
cells =cells.slice(cells.indexOf(cell));
if (cells.length > result.length) result= cells;
}
}
return result;
}
var input = document.querySelector('textarea');
var output = document.querySelector('span');
(input.oninput = function () {
varedges=input.value.trim().split(/\s+/).map(Number);
var cycle = largestCycle(edges);
output.textContent = cycle.length + ': ' + JSON.stringify(cycle); })();
This is complexity with O(N) runtime where each edge of which there's at most N nodes is followed at most 3 times in the graph and the cache is updated exactly once for each and every node in the graph. It's uses O(N) additional storage.
kaypeeoh72z and 79 more users found this answer helpful
THANKS
71
4.1
(8 votes)
Log in to add comment
Find Computer Science textbook solutions?
SEE ALL
Class Class 12
Class Class 11
Class Class 10
Class Class 9
Class Class 8
Class Class 7
Class Class 6
Computer Studies Class - 9
394 solutions
Computer Science Class 6 Englis…
183 solutions
Computer Science Class 7 Englis…
171 solutions
Computer Science Class 8 Englis…
149 solutions
CBSE: Information and Commun…
212 solutions
Computer Technology and Programmin…
238 solutions
Computer Science
278 solutions
CBSE: Computer Science C…
550 solutions
Sample Question Papers - C…
367 solutions
Computer Science Class 9 Englis…
128 solutions
SEE ALL
Advertisement
Answer
26
mounivijaya123
Helping Hand
1 answer
26 people helped
Answer:
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
9 2
sikringbp and 26 more users found this answer helpful
THANKS
26
0.0
(0 votes)
Unlocked badge showing two hands making the shape of heart over a pink circle
Found this answer helpful? Say thanks and unlock a badge.
Log in to add comment
Advertisement
Still have questions?
FIND MORE ANSWERS
Unlocked badge showing a round hole with a white rabbit’s paw and ears sticking out
Ready to dive into rabbit hole and unlock a badge.
ASK YOUR QUESTION
New questions in Computer Science
what will be the output of 10 and 3
Shusant has a keen interest in creating web pages. It is his friend Raunak's birthday and he wants to create a web page containing a few lines on thei …
How to increase ins tagram followers??
Give the regular expression for the set of string ending in 00
which type of system base is? a) spreadsheet b)presentation c)RDBMS D)WORD PROCESSOR
a computer is a can not be- a. compiler b. loader c.operating system d. aa
In this problem, 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.
The input is given as follows:
The first line is a number which is the number of people in the social network. The next following lines are the actual members of the social network whose names are written in separate lines. Following that is the number of connections, followed by a new line separated list of connections given as <follower> <following> Then on the next line is the id of the person who wants to our React Expert (A) and on the next line is the id of the person who is the newbie (B)
N=int(input())
dic={}
def addnode(u,v):
dic[u].append(v)
for i in range(N):
n1=int(input())
dic[n1]=[]
edge=int(input())
for i in range(edge):
u,v=map(int,input().split())
addnode(u,v)
start=int(input())
end=int(input())
tr=[]
tr.append(start)
def traverse(dic,start):
for i in dic[start]:
if(i==end):
return
if(len(dic[start])==0):
return
else:
tr.append(i)
traverse(dic,i)
traverse(dic,start)
tr=sorted(tr)
for i in tr:
print(i,end=" ")
The Malicious Haskeller
3 4
import sys
5 def soluti 6
7
In this problem, 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.
8
return
9 membersCour
10 memberIds 11 for in ra
12
The input is given as follows:
The first line is a number which is the number of people in the social network. The next following liner are the actual members of the social network whose names are written in separate lines. Following that is the number of connections, followed by a new line separated list of connections given as <follower> <following Then on the next line is the id of the person who wants to our React Expert (A) and on the next line is the id of the person who is the newbie (B)
13
memberl
14 edgesCount 15 edgeFrom 16 edgeTo []
17 for 18
19
INPUT FORMAT
s
- Anonymous January 18, 2017