Samsung Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
coded using backtracking approach
int vist(vector< pair<int , int > > cust,pair<int ,int > home,vector<bool> vis,int i){
int max=9999;
int flag=1;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
flag=0;
vis[j]=true;
int temp = abs(cust[j].first,cust[i].first)+abs(cust[j].second,cust[i].second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
if(flag==1){
return abs(cust[i].first,home.first)+abs(cust[i].second,home.second);
}
else return max;
}
int location (pair<int ,int > off ,vector< pair<int , int > > cust ,pair<int ,int > home){
vector<bool> vis(cust.size(),false);
int max=9999;
for(int j=0;j<vis.size();j++){
if(!vis[j]){
vis[j]=true;
int temp = abs(cust[j].first,off.first)+abs(cust[j].second,off.second)+vist(cust,home,vis,j);
vis[j]=false;
if(temp<max) max=temp;
}
}
return max;
}
int main(){
pair<int ,int > off (88,81);
pair<int ,int > home (85,80);
vector<pair<int ,int > > cust;
cust.push_back(make_pair(19,22));
cust.push_back(make_pair(31,15));
cust.push_back(make_pair(27,29));
cust.push_back(make_pair(30,10));
cust.push_back(make_pair(20,26));
cust.push_back(make_pair(5,14));
cout<<location(off,cust,home);
}
int main(){
pair<int ,int > off (88,81);
pair<int ,int > home (85,80);
vector<pair<int ,int > > cust;
cust.push_back(make_pair(19,22));
cust.push_back(make_pair(31,15));
cust.push_back(make_pair(27,29));
cust.push_back(make_pair(30,10));
cust.push_back(make_pair(20,26));
cust.push_back(make_pair(5,14));
cout<<location(off,cust,home);
}
#include<iostream>
using namespace std;
int abs(int aa)
{
if(aa<0)
return -1*aa;
return aa;
}
int x[12],y[12],ox,oy,hx,hy,vis[12],ans,n,ct;
void solve(int xx,int yy,int visited,int curr_cost,int idx)
{
int cost = 0;
if(idx!=-1)
vis[idx]=1;
if(visited==n){
//cout<<ct++<<endl;
curr_cost += abs(xx-hx)+abs(yy-hy);
ans = min(ans,curr_cost);
return;
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
cost = curr_cost + abs(xx-x[i]) + abs(yy-y[i]);
solve(x[i],y[i],visited+1,cost,i);
vis[i]=0;
}
}
if(idx!=-1)
vis[idx]=0;
}
int main()
{
ct=0;
cin>>n;
ans = INT_MAX;
cin>>ox>>oy;
cin>>hx>>hy;
for(int i=0;i<n;i++)
{
vis[i]=0;
cin>>x[i]>>y[i];
}
solve(ox,oy,0,0,-1);
cout<<ans;
}
// Mr KIM by Himani ma'am on GFG
#include<iostream>
using namespace std;
int abs(int aa)
{
if(aa<0)
return -1*aa;
return aa;
}
int x[12],y[12],ox,oy,hx,hy,vis[12],ans,n,ct;
void solve(int xx,int yy,int visited,int curr_cost,int idx)
{
int cost = 0;
if(idx!=-1)
vis[idx]=1;
if(visited==n){
//cout<<ct++<<endl;
curr_cost += abs(xx-hx)+abs(yy-hy);
ans = min(ans,curr_cost);
return;
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
cost = curr_cost + abs(xx-x[i]) + abs(yy-y[i]);
solve(x[i],y[i],visited+1,cost,i);
vis[i]=0;
}
}
if(idx!=-1)
vis[idx]=0;
}
int main()
{
ct=0;
cin>>n;
ans = INT_MAX;
cin>>ox>>oy;
cin>>hx>>hy;
for(int i=0;i<n;i++)
{
vis[i]=0;
cin>>x[i]>>y[i];
}
solve(ox,oy,0,0,-1);
cout<<ans;
}
Looks like a TSP, which is a O(2^n) problem.
This is why I created a greedy algorithm:
- akmo75 January 09, 2016