Samsung Interview Question
Backend DevelopersCountry: India
Interview Type: Written Test
#include<bits/stdc++.h>
using namespace std;
//dt duration to stop in a division
void bfs(vector<pair<int,double> > g[],int n,int dt,int lm)
{
queue<int> que;
int division=1;
double maxprob=0;
double prob[n];
bool visited[n];
for(int i=0;i<n;i++)
{
prob[i]=0;
visited[i]=false;
}
que.push(0);
prob[0]=1;
visited[0]=true;
int limit=0;
while(!que.empty())
{
int size=que.size();
division=1,maxprob=0;
while(size--)
{
int u=que.front();
que.pop();
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].first;
double w=g[u][i].second;
if(u!=v)
{
prob[v]+=prob[u]*w;
if(maxprob<prob[v])
{
maxprob=prob[v];
division=v+1;
}
}
if(visited[v]==false)
{
que.push(v);
visited[v]=true;
}
}
}
limit+=dt;
if(limit>=lm)
break;
}
cout<<std::setprecision(6)<<std::fixed;
cout<<division<<" "<<maxprob;
}
int main()
{
int t,n,e,ed;
int sd=10;
while(cin>>t)
{
cin>>n>>e>>ed;
vector<pair<int,double> > g[n];
int x,y;
double p;
for(int i=0;i<e;i++)
{
cin>>x>>y>>p;
g[x-1].push_back(make_pair(y-1,p));
}
cout<<t<<" ";
bfs(g,n,sd,ed);
cout<<"\n";
}
}
#include<iostream>
using namespace std;
int main()
{
float pm[100][100] = {0};
float rm[100][100] = {0};
int nodes, e, t;
cin >> nodes>>e>>t;
int x, y;
for (int i = 0; i < e; i++)
{
cin >> x >> y;
cin >> pm[x-1][y-1];
}
rm[0][0] = 1;
for (int i = 0; i < t/10; i++) // time
{
for (int j = 0; j < nodes ; j++) // nodes
{
if (rm[i][j] > 0)
{
for (int k = 0; k < nodes; k++)
{
rm[i+1][k] += rm[i][j]*pm[j][k];
}
}
}
}
float ans = 0;
int res;
for (int i = 0; i < nodes; i++)
{
if (rm[t / 10][i] > ans)
{
ans = rm[t / 10][i];
res = i;
}
}
cout << res+1 <<" "<< ans << endl;
return 0;
}
/*
6 10 40
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1 6 3 0.5 6 6 0.5
*/
- Samurai July 26, 2019