Samsung Interview Question
Software EngineersCountry: United States
Can you please check if this code works on the given constraint or not?
Thanks!!
#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
int t; cin>>t;
while(t--)
{
int n,m,lim; cin>>n>>m>>lim;
vector<int> v,o;
queue<pair<int,int> > q;
for(int i=0;i<n;++i)
{
int x; cin>>x;
v.push_back(x);
q.push(make_pair(x,1));
}
for(int i=0;i<m;++i)
{
int x; cin>>x;
o.push_back(x);
}
int y; cin>>y;
pair<int,int> re;
while(!q.empty())
{
int x = q.front().first;
int l = q.front().second;
if(x==y)
{
re.first = y;
re.second = l;
break;
}
q.pop();
if(!vis[x])
{
for(int i=0;i<n;++i)
{
q.push(make_pair(x*10 + v[i],l+1));
}
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(o[i]==1)
{
q.push(make_pair(x+v[j],l+3));
}
else if(o[i]==2)
{
q.push(make_pair(x-v[j],l+3));
}
else if(o[i]==3)
{
q.push(make_pair(x*v[j],l+3));
}
else if(o[i]==4)
{
q.push(make_pair(x/v[j],l+3));
}
}
}
vis[x] = true;
}
}
cout<<re.second<<endl;
}
}
Can you please check if this code work on given constraints or not ?
Thanks!!
#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
int t; cin>>t;
while(t--)
{
int n,m,lim; cin>>n>>m>>lim;
vector<int> v,o;
queue<pair<int,int> > q;
for(int i=0;i<n;++i)
{
int x; cin>>x;
v.push_back(x);
q.push(make_pair(x,1));
}
for(int i=0;i<m;++i)
{
int x; cin>>x;
o.push_back(x);
}
int y; cin>>y;
pair<int,int> re;
while(!q.empty())
{
int x = q.front().first;
int l = q.front().second;
if(x==y)
{
re.first = y;
re.second = l;
break;
}
q.pop();
if(!vis[x])
{
for(int i=0;i<n;++i)
{
q.push(make_pair(x*10 + v[i],l+1));
}
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(o[i]==1)
{
q.push(make_pair(x+v[j],l+3));
}
else if(o[i]==2)
{
q.push(make_pair(x-v[j],l+3));
}
else if(o[i]==3)
{
q.push(make_pair(x*v[j],l+3));
}
else if(o[i]==4)
{
q.push(make_pair(x/v[j],l+3));
}
}
}
vis[x] = true;
}
}
cout<<re.second<<endl;
}
}
abe chutiye kis calculator ka output tune is tarah se(7+2=&81) 981 dekha hai. it will show 81 only in this case
Second Test Case for problem in wrong..
Correction
6 2 4 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28
Here it should be
6 3 5 // 2nd test case
0 1 3 5 7 9
1 2 4 // +, -, / allowed here
28
Try Solving it now...
If you are struck and need solution mail me on namit.pasrija@gmail.com
I got this question today at Samsung's NCR test : I was able to figure out the approach using backtracking but there were so many constraints and i felt emergy lost. My approach was to simple create a 1d array of Numers|operators as input. Then for each set recur after checking constraints .
- Anonymous October 28, 2018Before recurring use the lastOperator if present or simply append current digit to current number formed
After recurring reset current number formed
Keep updating click count in base condition