Samsung Interview Question for Software Engineers


Country: India




Comment hidden because of low score. Click to expand.
3
of 3 vote

#include <bits/stdc++.h>

using namespace std;

int dp[13][1 << 12];
int x[13], y[13];

int n;

int calc(int p, int mask) {
    if (p == 0) return (mask != 0) * 1e9;
    int &ret = dp[p][mask];
    if (ret != -1) return ret;
    ret = 1e9;
    for (int i = 0; i <= n; ++i) {
        if (mask & (1 << i)) {
            int dist = abs(x[p] - x[i]) + abs(y[p] - y[i]);
            ret = min(ret, calc(i, mask ^ (1 << i)) + dist);
        }
    }
    return ret;
}

int main() {
    for (int i = 0; i < 10; ++i) {
        scanf("%d", &n);
        scanf("%d %d", &x[n + 1], &y[n + 1]);
        scanf("%d %d", &x[0], &y[0]);
        for (int j = 1; j <= n; ++j) {
            scanf("%d %d", &x[j], &y[j]);
        }
        memset(dp, -1, sizeof dp);
        printf("#%d %d\n", i + 1, calc(n + 1, (1 << (n + 1)) - 1));
    }
    return 0;
}

- Anthony September 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

for 2nd case ans should be 328

- Abhishek November 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Solution written in Java

This is for only one test case. You can modify it for multiple test cases.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Point
{
	int xCord;
	int yCord;
	
	public Point(int x, int y)
	{
		this.xCord = x;
		this.yCord = y;
	}
}

class Ideone
{
	
	static int startX;
	static int startY;
	static int endX;
	static int endY;
	static int adjMatrix[][];
	static int arr[] ;
	static int minDist = Integer.MAX_VALUE;
	static int N;

	static void calculateDistance(int a[])
	{
		int dist = 0;
		int size = a.length;
		
		dist = adjMatrix[0][a[0]];
		
		for(int i=1; i<N; i++)
		{
			dist += adjMatrix[a[i]][a[i-1]];
		}

		dist += adjMatrix[a[N-1]][N+1];
		
		if(dist<minDist)
			minDist = dist;
	}

	static void findMinPath(int a[], int l, int r)
	{
		if(l==r)
		{
			calculateDistance(a);
		}
		else
		{
			for(int i=l; i<=r; i++)
			{
				a = swap(a, l, i);
				findMinPath(a, l+1, r);
				a = swap(a, l, i);
			}
		}
	}
	
	static int[] swap(int a[], int x, int y)
	{
		int temp = a[x];
		a[x] = a[y];
		a[y] = temp;
		return a;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		
		N = in.nextInt();
		
		startX = in.nextInt();
		startY = in.nextInt();
		endX = in.nextInt();
		endY = in.nextInt();
		
		Point pts[] = new Point[N+2];
		
		pts[0] = new Point(startX, startY);
		pts[N+1] = new Point(endX, endY);

		for(int i=1; i<N+1; i++)
		{
			int xLoc = in.nextInt();
			int yLoc = in.nextInt();
			pts[i] = new Point(xLoc, yLoc);
		}
		
		adjMatrix = new int[N+2][N+2];
		
		for(int x=0; x<N+2; x++)
		{
			for(int y=0; y<N+2; y++)
			{
				adjMatrix[x][y] = Math.abs(pts[x].xCord-pts[y].xCord) + Math.abs(pts[x].yCord-pts[y].yCord);
				adjMatrix[y][x] = adjMatrix[x][y];
			}
		}
		

		arr = new int[N];
		
		for(int count=0; count<N; count++)
		{
			arr[count] = count+1;
		}
		
		findMinPath(arr, 0, N-1);

		System.out.println(minDist);

	}
}

- Ashish Musani April 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

tester

- duskan September 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

are u sure last output is 366 or it is 368

- dxd September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

are u sure last output is 366??

i think it should be 368

- nothingelsematters September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't believe my bad luck :( !! I saw this problem but didn't care to solve it...and the exact same problem popped up in my exam!

- pokePy October 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

any other approach?

- any other approach? October 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain the logic?

- Avishek October 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

///////////////////////////////////////////////////////////////
// Author - Prakhar Pratyush
// IIT Roorkee, Final Year
// er.prakhar2b@gmail.com
//
////////////////////////////////////////////////////////////////

#include <bits/stdc++.h>

using namespace std;

int dp[12][1 << 11];  // bitmask with max 11 bits
int x[12], y[12];  //  5<= N <= 10 , home, office

int n;

int calc(int p, int mask) {
    if(p == 0 && mask == 0) return 0; // Base case - reached home and visited all customers
    else if(p == 0) return 1e9;

    // When recursion hits base case (home + all traversed), to eliminate other base 
    // case (home + not all traversed), we need to return higher value -- thus 1e9
    
     dp[p][mask]=1e9; 

    for (int i = n; i >=0 ; --i) {
        if (mask & (1 << i)) {                      // Check if ith bit is 1
            int dist = abs(x[p] - x[i]) + abs(y[p] - y[i]);
             dp[p][mask] = min( dp[p][mask], calc(i, mask ^ (1 << i)) + dist);    // toggle the ith bit to indicate this bit as visited
        }
    }
    return  dp[p][mask];
}

int main() {
    std::ios::sync_with_stdio(false);

    for (int i = 1; i <= 10; ++i) {

        cin>>n;
        cin>>x[0]>>y[0];
        cin>>x[n+1]>>y[n+1];

        for (int j = 1; j <= n; ++j) {
            cin>>x[j]>>y[j];
        }

        memset(dp, -1, sizeof dp);

        int mask = (1 << (n + 1)) - 1; // n+1 bits representing n customers and office- starting point

        cout<<"Case #"<< i <<": "<< calc(n + 1, mask); // Sending end point- home
        
    }
    return 0;
}


/* Proof Of Concept------------------------------------------------------------------------------

                     calc(n+1, 1111............1) // destination , initially all bit is 1- means not visited
                     /                      \
     min of |       calc(n,0111.......1)    calc(n-1,10111....1)   ....          calc(0,11......0)
                   /                   \
    min of |      calc(n-1, 0011....1)      ...  // If ith bit is not 1, recursive call won't take place
                     .
                     .
                     .
                   /  
    min of |     calc(0, 0000....0)  ...

*/

- Prakhar Pratyush October 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <stdio.h>
#define MAXIMUM 10000000
using namespace std;

int calculate_distance(pair<int, int> a, pair<int, int> b){
	int maxX = max(a.first, b.first);
	int minX = min(a.first, b.first);
	int maxY = max(a.second, b.second);
	int minY = min(a.second, b.second);
	return (maxX - minX + maxY - minY);
}

void print(int x){
	cout<<x<<" ";
}

int main(){
	int no_neighbour;
	cin>>no_neighbour;

	vector< pair<int, int> > coords;
	pair<int, int> temp;
	vector<int> nodes;
	int mat[no_neighbour+2][no_neighbour+2];
	for(int i=0; i<no_neighbour+2; i++){
		cin>>temp.first>>temp.second;
		coords.push_back(temp);
	}

	for(int i=0; i<no_neighbour+2; i++){
		for(int j=0; j<no_neighbour+2; j++){
			mat[i][j] = calculate_distance(coords[i],coords[j]);
			// printf("%4d", mat[i][j]);
		}
		if(i!=0 && i!=1)nodes.push_back(i);
		cout<<endl;
	}

	int mindistance = MAXIMUM;
	do{
		// for_each(nodes.begin(), nodes.end(), print);
		int distance = 0;
		int prev = 1;
		for(int i=0; i<no_neighbour; i++){
			distance+=mat[prev][nodes[i]];
			prev = nodes[i];
		}
		distance += mat[prev][0];
		// cout<<distance<<endl;
		if(distance < mindistance) mindistance = distance;
	}while(next_permutation(nodes.begin(), nodes.end()));

	cout<<mindistance<<endl;
	return 0;
}

I guess answer for the third case should be 352 not 368. I am certain because I have checked for all the possible combination. You can verify this by my code.

- Chandan Purbia November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

any one provide correct code plz

- Anonymous November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;





/* <Program description>
*
* Mr. Kim has to deliver samples to N costumer.
* Find the shortest way to deliver it and return his home
*
* Mr.Kim<Office>--> Costumer1-->....CustomerN--> His Home.
*
*
*
*/

/* <Idea --> Solution>
*
* find all possible path:
* There is N!-1 possible path
*
* for : earch path from 1----> N!-1
* (i)--> Corresponding sequence --> {Permuation}
* --> determine Shortest distance and print "the path sequence"
*
*/

/* <Result >
*
* Case #1: 200: path -> Office->[2-1-4-0-3]-->Home
* Case #2: 304: path-> Office->[1-3-5-0-4-2]-->Home
* Case #3: 366: path-> Office->[6-3-9-4-8-0-5-1-7-2]-->Home
*/


namespace ShortestPathDelivery
{
class Program
{
static void Main(string[] args)
{

// Test case:

// Case 1:
/*
const int N = 5;
int[,] xyLocation = {{ 70, 40 }, { 30, 10 }, { 10, 5 }, { 90, 70 }, { 50, 20 }};

int[,] xyOffice = { {0,0}};
int[,] xyHome = { { 100, 100 } };
*
*/

//case 2:
/*
const int N = 6;
int[,] xyLocation = { { 19, 22 }, { 31, 15 }, { 27, 29 }, { 30, 10 }, { 20, 26 },{5,14} };
int[,] xyOffice = { { 81, 88} };
int[,] xyHome = { { 85, 80 } };
*/


const int N = 10;
int[,] xyLocation = { {35,93 }, { 62,64 }, { 96,39}, { 36,36 }, { 5,59 },
{59,96},{61,7},{64,43},{43,58},{1,36} };

int[,] xyOffice = { {39,9}};
int[,] xyHome = { { 97, 61 } };




int[] pathseq = new int[N];
int[] finalPath = new int[N];
int[] shortestPath = new int[N];

double dis_Min = 10000 ;

// pathseq = GetPathsequence(2982, N);

//List allpath
for (int i = 0; i < GetNmul(N); i++)
{
pathseq = GetPathsequence(i, N);
// PrintPath(pathseq);
finalPath = Convertsequence(pathseq);
// PrintPath(finalPath);

// Calculate corresponding distance
double tempDis = CalDistance(finalPath, xyLocation, xyHome, xyOffice);

// System.Console.Write(" --Dis: {0} ", CalDistance(finalPath, xyLocation, xyHome, xyOffice));
if (i == 0)
{
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);

}
else
{
if (dis_Min > CalDistance(finalPath, xyLocation, xyHome, xyOffice))
{
shortestPath = finalPath;
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
}



}


PrintPath(shortestPath);
System.Console.WriteLine(" Shortest Dis: {0} ", dis_Min);


System.Console.ReadKey();

}


// This function return the sequence from n--> factorized sequence.
public static int[] GetPathsequence(int n, int Ncustom)
{
int[] aSequence = new int[Ncustom];

int divide = 0;
int remainder = 0;

for (int i = Ncustom-1; i >=0;i-- )
{


if(i==Ncustom-1)
{
divide = (int)n / GetNmul(Ncustom-1);
remainder = (int)n % GetNmul(Ncustom-1);
aSequence[Ncustom-1-i] = divide;
}
else

{
divide = remainder / GetNmul(i);
remainder = remainder % GetNmul(i);
aSequence[Ncustom-1-i] = divide;
}

}


return aSequence;
}

public static int GetNmul(int n)
{
if (n == 0)
return 1;
else
return n * GetNmul(n - 1);


}


public static void PrintPath(int [] aPath)
{
for (int i =0; i <aPath.Length; i++)
{
System.Console.Write("{0} :", aPath[i]);
}

System.Console.WriteLine("");
}

public static int[] Convertsequence(int [] inArray)
{
int[] decodeArray = new int[(int)inArray.Length];
List<int> naturalList = new List<int>();
for (int i = 0; i < inArray.Length;i++)
{
naturalList.Add(i);
}

// Decoding
for (int i = 0; i < inArray.Length; i++)
{
decodeArray[i] = naturalList[inArray[i]];
naturalList.Remove(decodeArray[i]);
}

return decodeArray;
}

public static double CalDistance(int[] iPath, int[,] XYLocation, int[,] xyHome, int[,] xyOffice)
{
double dis =0, dis_0,dis_N;
for (int i = 0; i < iPath.Length-1 ; i++)
{
dis = dis + Math.Abs(XYLocation[iPath[i], 0] - XYLocation[iPath[i+1], 0])
+ Math.Abs(XYLocation[iPath[i], 1] - XYLocation[iPath[i+1], 1]);

}
dis_0 = Math.Abs(xyOffice[0,0] - XYLocation[iPath[0], 0])
+ Math.Abs(xyOffice[0,1] - XYLocation[iPath[0], 1]);
dis_N = Math.Abs(XYLocation[iPath[iPath.Length - 1], 0] - xyHome[0,0])
+ Math.Abs(XYLocation[iPath[iPath.Length - 1], 1] - xyHome[0, 1]);
dis = dis + dis_0 + dis_N;

return dis;
}

}
}


}

- Nguyen Van Hien December 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;





/* <Program description>
*
* Mr. Kim has to deliver samples to N costumer.
* Find the shortest way to deliver it and return his home
*
* Mr.Kim<Office>--> Costumer1-->....CustomerN--> His Home.
*
*
*
*/

/* <Idea --> Solution>
*
* find all possible path:
* There is N!-1 possible path
*
* for : earch path from 1----> N!-1
* (i)--> Corresponding sequence --> {Permuation}
* --> determine Shortest distance and print "the path sequence"
*
*/

/* <Result >
*
* Case #1: 200: path -> Office->[2-1-4-0-3]-->Home
* Case #2: 304: path-> Office->[1-3-5-0-4-2]-->Home
* Case #3: 366: path-> Office->[6-3-9-4-8-0-5-1-7-2]-->Home
*/


namespace ShortestPathDelivery
{
class Program
{
static void Main(string[] args)
{

// Test case:

// Case 1:
/*
const int N = 5;
int[,] xyLocation = {{ 70, 40 }, { 30, 10 }, { 10, 5 }, { 90, 70 }, { 50, 20 }};

int[,] xyOffice = { {0,0}};
int[,] xyHome = { { 100, 100 } };
*
*/

//case 2:
/*
const int N = 6;
int[,] xyLocation = { { 19, 22 }, { 31, 15 }, { 27, 29 }, { 30, 10 }, { 20, 26 },{5,14} };
int[,] xyOffice = { { 81, 88} };
int[,] xyHome = { { 85, 80 } };
*/


const int N = 10;
int[,] xyLocation = { {35,93 }, { 62,64 }, { 96,39}, { 36,36 }, { 5,59 },
{59,96},{61,7},{64,43},{43,58},{1,36} };

int[,] xyOffice = { {39,9}};
int[,] xyHome = { { 97, 61 } };




int[] pathseq = new int[N];
int[] finalPath = new int[N];
int[] shortestPath = new int[N];

double dis_Min = 10000 ;

// pathseq = GetPathsequence(2982, N);

//List allpath
for (int i = 0; i < GetNmul(N); i++)
{
pathseq = GetPathsequence(i, N);
// PrintPath(pathseq);
finalPath = Convertsequence(pathseq);
// PrintPath(finalPath);

// Calculate corresponding distance
double tempDis = CalDistance(finalPath, xyLocation, xyHome, xyOffice);

// System.Console.Write(" --Dis: {0} ", CalDistance(finalPath, xyLocation, xyHome, xyOffice));
if (i == 0)
{
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);

}
else
{
if (dis_Min > CalDistance(finalPath, xyLocation, xyHome, xyOffice))
{
shortestPath = finalPath;
dis_Min = CalDistance(finalPath, xyLocation, xyHome, xyOffice);
}
}



}


PrintPath(shortestPath);
System.Console.WriteLine(" Shortest Dis: {0} ", dis_Min);


System.Console.ReadKey();

}


// This function return the sequence from n--> factorized sequence.
public static int[] GetPathsequence(int n, int Ncustom)
{
int[] aSequence = new int[Ncustom];

int divide = 0;
int remainder = 0;

for (int i = Ncustom-1; i >=0;i-- )
{


if(i==Ncustom-1)
{
divide = (int)n / GetNmul(Ncustom-1);
remainder = (int)n % GetNmul(Ncustom-1);
aSequence[Ncustom-1-i] = divide;
}
else

{
divide = remainder / GetNmul(i);
remainder = remainder % GetNmul(i);
aSequence[Ncustom-1-i] = divide;
}

}


return aSequence;
}

public static int GetNmul(int n)
{
if (n == 0)
return 1;
else
return n * GetNmul(n - 1);


}


public static void PrintPath(int [] aPath)
{
for (int i =0; i <aPath.Length; i++)
{
System.Console.Write("{0} :", aPath[i]);
}

System.Console.WriteLine("");
}

public static int[] Convertsequence(int [] inArray)
{
int[] decodeArray = new int[(int)inArray.Length];
List<int> naturalList = new List<int>();
for (int i = 0; i < inArray.Length;i++)
{
naturalList.Add(i);
}

// Decoding
for (int i = 0; i < inArray.Length; i++)
{
decodeArray[i] = naturalList[inArray[i]];
naturalList.Remove(decodeArray[i]);
}

return decodeArray;
}

public static double CalDistance(int[] iPath, int[,] XYLocation, int[,] xyHome, int[,] xyOffice)
{
double dis =0, dis_0,dis_N;
for (int i = 0; i < iPath.Length-1 ; i++)
{
dis = dis + Math.Abs(XYLocation[iPath[i], 0] - XYLocation[iPath[i+1], 0])
+ Math.Abs(XYLocation[iPath[i], 1] - XYLocation[iPath[i+1], 1]);

}
dis_0 = Math.Abs(xyOffice[0,0] - XYLocation[iPath[0], 0])
+ Math.Abs(xyOffice[0,1] - XYLocation[iPath[0], 1]);
dis_N = Math.Abs(XYLocation[iPath[iPath.Length - 1], 0] - xyHome[0,0])
+ Math.Abs(XYLocation[iPath[iPath.Length - 1], 1] - xyHome[0, 1]);
dis = dis + dis_0 + dis_N;

return dis;
}

}
}

- nguyenvanhiencdt49 December 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=10;
while(t--)
{
int n;
scanf("%d",&n);
vector< pair<int,int> > v;
int x1;
int y1;
cin>>x1>>y1;
int x2;
int y2;
cin>>x2;
cin>>y2;
v.push_back(make_pair(x1,y1));
for(int i=1;i<=n;i++)
{
int x;
int y;
cin>>x;
cin>>y;
v.push_back(make_pair(x,y));
}
int count=0;
v.push_back(make_pair(x2,y2));
//int dis=INT_MAX;
int k1=0;
sort(v.begin()+1,v.end()-1);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
while(next_permutation(v.begin()+1,v.end()-1))
{
int k=0;
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
if(k<k1)
{
k1=k;
}
}
// cout<<v.size()<<"\n";
cout<<k1<<endl;
}
return 0;
}

- Bandi April 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t=10;
	while(t--)
	{
		int n;
		scanf("%d",&n);
		vector< pair<int,int> > v;
		int x1;
		int y1;
		cin>>x1>>y1;
		int x2;
		int y2;
		cin>>x2;
		cin>>y2;
		v.push_back(make_pair(x1,y1));
		for(int i=1;i<=n;i++)
		{
			int x;
			int y;
			cin>>x;
			cin>>y;
			v.push_back(make_pair(x,y));
		}
		int count=0;
		v.push_back(make_pair(x2,y2));
		//int dis=INT_MAX;
		int k1=0;
		sort(v.begin()+1,v.end()-1);
		for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
		{
			k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
		}
		while(next_permutation(v.begin()+1,v.end()-1))
		{
			int k=0;
		for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
		{
			k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
		}
		if(k<k1)
		{
			k1=k;
		}
		}
	//	cout<<v.size()<<"\n";
		cout<<k1<<endl;
	}
	return 0;
}

- Bandi April 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t=10;
while(t--)
{
int n;
scanf("%d",&n);
vector< pair<int,int> > v;
int x1;
int y1;
cin>>x1>>y1;
int x2;
int y2;
cin>>x2;
cin>>y2;
v.push_back(make_pair(x1,y1));
for(int i=1;i<=n;i++)
{
int x;
int y;
cin>>x;
cin>>y;
v.push_back(make_pair(x,y));
}
int count=0;
v.push_back(make_pair(x2,y2));
//int dis=INT_MAX;
int k1=0;
sort(v.begin()+1,v.end()-1);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k1+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
while(next_permutation(v.begin()+1,v.end()-1))
{
int k=0;
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end()-1;it++)
{
k+=abs(it->first-(it+1)->first)+abs(it->second-(it+1)->second);
}
if(k<k1)
{
k1=k;
}
}
// cout<<v.size()<<"\n";
cout<<k1<<endl;
}
return 0;
}

- Bandi April 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

is there any code that will give me correct result according to question ?

- Anuj April 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
visited[pos]=1;

if(n==total+1 && pos==1)
{
if(ans==-1)
{
ans=s;
}
else
{
ans=min(ans,s);
}
}

for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
fun(i,total+1,s+sum);
}
}
visited[pos]=0;
}

int main()
{
int t;
cin>>t;
// cout<<t<<endl;
while(t--)
{
// int n;
cin>>n;
n=n+2;
ans=-1;

for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
visited[i]=0;
}
fun(0,0,0);
cout<<ans<<endl;
}


return 0;
}

- Bangali September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
    visited[pos]=1;

    if(n==total+1 && pos==1)
    {
        if(ans==-1)
        {
            ans=s;
        }
        else
        {
            ans=min(ans,s);
        }
    }
    
    for(int i=0;i<n;i++)
    {
        if(visited[i]==0)
        {
            int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
            fun(i,total+1,s+sum);
        }
    }
    visited[pos]=0;
}

int main()
{
    int t;
    cin>>t;
   // cout<<t<<endl;
    while(t--)
    {
       // int n;
        cin>>n;
        n=n+2;
        ans=-1;
       
       for(int i=0;i<n;i++)
       {
           cin>>x[i]>>y[i];
           visited[i]=0;
       }
       fun(0,0,0);
    cout<<ans<<endl;
    }
    
    
    return 0;

}

- Bangali September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int ans=-1;
int visited[20];
int x[20],y[20],n;
void fun(int pos,int total,int s)
{
    visited[pos]=1;

    if(n==total+1 && pos==1)
    {
        if(ans==-1)
        {
            ans=s;
        }
        else
        {
            ans=min(ans,s);
        }
    }
    
    for(int i=0;i<n;i++)
    {
        if(visited[i]==0)
        {
            int sum=abs(x[pos]-x[i])+abs(y[pos]-y[i]);
            fun(i,total+1,s+sum);
        }
    }
    visited[pos]=0;
}

int main()
{
    int t;
    cin>>t;
   // cout<<t<<endl;
    while(t--)
    {
       // int n;
        cin>>n;
        n=n+2;
        ans=-1;
       
       for(int i=0;i<n;i++)
       {
           cin>>x[i]>>y[i];
           visited[i]=0;
       }
       fun(0,0,0);
    cout<<ans<<endl;
    }
    
    
    return 0;
}

- virendrasingh1404 September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
	int n,i,c,x1,y1;
	scanf("%d",&n);
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	for(i=0;i<n;i++)
	scanf("%d %d",&x[i],&y[i]);
	int a[n];
	for(i=0;i<n;i++)
	a[i]=0;
	for(i=0;i<n;i++)
	{
		a[i]=1;
		c=abs(x1-x[i])+abs(y1-y[i]);
		solve(a,c,n,i);
		a[i]=0;
	}
	printf("%d\n",min);
	return 0;
	
}
void solve(int a[],int c,int n,int p)
{
	int s=0,s2,i;
	for(i=0;i<n;i++)
	{
		if(a[i]==0)
		{
		a[i]=1;
		solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
		a[i]=0;
	    }
	}
	for(i=0;i<n;i++)
	s=s+a[i];
	if(s==n)
	{
		s2=c+abs(x[p]-x2)+abs(y[p]-y2);
		if(min>s2)
		min=s2;
		return;
	}

}

- Anonymous October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
	int n,i,c,x1,y1;
	scanf("%d",&n);
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	for(i=0;i<n;i++)
	scanf("%d %d",&x[i],&y[i]);
	int a[n];
	for(i=0;i<n;i++)
	a[i]=0;
	for(i=0;i<n;i++)
	{
		a[i]=1;
		c=abs(x1-x[i])+abs(y1-y[i]);
		solve(a,c,n,i);
		a[i]=0;
	}
	printf("%d\n",min);
	return 0;
	
}
void solve(int a[],int c,int n,int p)
{
	int s=0,s2,i;
	for(i=0;i<n;i++)
	{
		if(a[i]==0)
		{
		a[i]=1;
		solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
		a[i]=0;
	    }
	}
	for(i=0;i<n;i++)
	s=s+a[i];
	if(s==n)
	{
		s2=c+abs(x[p]-x2)+abs(y[p]-y2);
		if(min>s2)
		min=s2;
		return;
	}
}

- Sad October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <math.h>
#include <conio.h>
void solve(int a[],int c,int n,int p);
int min=999999;
int x2,y2;
int x[12];
int y[12];
int main()
{
int n,i,c,x1,y1;
scanf("%d",&n);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
int a[n];
for(i=0;i<n;i++)
a[i]=0;
for(i=0;i<n;i++)
{
a[i]=1;
c=abs(x1-x[i])+abs(y1-y[i]);
solve(a,c,n,i);
a[i]=0;
}
printf("%d\n",min);
return 0;

}
void solve(int a[],int c,int n,int p)
{
int s=0,s2,i;
for(i=0;i<n;i++)
{
if(a[i]==0)
{
a[i]=1;
solve(a,(c+abs(x[p]-x[i])+abs(y[p]-y[i])),n,i);
a[i]=0;
}
}
for(i=0;i<n;i++)
s=s+a[i];
if(s==n)
{
s2=c+abs(x[p]-x2)+abs(y[p]-y2);
if(min>s2)
min=s2;
return;
}
}

- Sad October 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int abs(int i,int j){
    if(i-j>0)
        return i-j;
    else
        return j-i;
}
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);
	}

- sashi December 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int abs(int i,int j){
    if(i-j>0)
        return i-j;
    else
        return j-i;
}
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);
}

- Anonymous December 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>

using namespace std;

class coords{
    public:
        int x;
        int y;
};
coords off,home;
coords cust[10];
bool vis[10];


int cVisit(int i,int n){
    int max1=99999;
    int flag=1;
    for(int j=0;j<n;j++)
    {
        if(!vis[j])
        {
            flag=0;
            vis[j]=true;
            int temp=abs(cust[i].x-cust[j].x)+abs(cust[i].y-cust[j].y)+cVisit(j,n);
            vis[j]=false;
            if(temp<max1){max1=temp;}
        }
    }
    if(flag==1){return abs(cust[i].x-home.x)+abs(cust[i].y-home.y);}
    else{return max1;}
}

int func(int n){
    for(int i=0;i<n;i++)
        vis[i]=false;
    int max=99999;
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            vis[i]=true;
            int temp=abs(cust[i].x-off.x)+abs(cust[i].y-off.y)+cVisit(i,n);
            vis[i]=false;
            if(temp<max){max=temp;}
        }        
    }
    return max;
}

int main(){
    int t;
    while(t--){
        int n;
        cin>>n;
        cin>>off.x>>off.y;
        cin>>home.x>>home.y;   
        for(int i=0;i<n;i++)
            cin>>cust[i].x>>cust[i].y;
        cout<<func(n)<<endl;
    }
    
}

- Anonymous December 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Backtracking approach :
import java.util.Scanner;

public class Other {

public static void main(String[] args) {
int t = 10;
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
while (t != 0) {
int n = sc.nextInt();

int x[] = new int[n + 2];
int y[] = new int[n + 2];

x[0] = sc.nextInt();
y[0] = sc.nextInt();

x[n + 1] = sc.nextInt();
y[n + 1] = sc.nextInt();

for (int i = 1; i <= n; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
n = n + 2;
boolean[] visited = new boolean[n];
min = Integer.MAX_VALUE;
compute(visited, 0, 0, n - 1, x, y, 0);
System.out.println(min);
t--;
}
}

public static int min;

private static void compute(boolean[] visited, int i, int d, int n, int[] x, int[] y, int vv) {

if (vv == (n - 1)) {
int k = Math.abs(x[i] - x[n]) + Math.abs(y[i] - y[n]);
if ((d + k) < min) {
min = d + k;
}
return;
}

if (!visited[i]) {
visited[i] = true;
for (int k = 0; k < n; k++) {
if (!visited[k]) {
d = d + (Math.abs(x[i] - x[k]) + Math.abs(y[i] - y[k]));
vv += 1;
compute(visited, k, d, n, x, y, vv);
vv -= 1;
d = d - (Math.abs(x[i] - x[k]) + Math.abs(y[i] - y[k]));
visited[k] = false;
}
}
}
}
}

- Anonymous February 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
import java.lang.Math;
class GFG {
    
    static class pair
    {
        int x,y;
        public pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }
    static class mind
    {
        static int d=Integer.MAX_VALUE;
    }
    
    void swap(pair ar[],int x,int y)
    {
        pair temp=ar[x];
        ar[x]=ar[y];
        ar[y]=temp;
    }
    
    int calcDist(pair o,pair h,pair[] c)
    {
        int l=c.length;
        int sum=0;
        sum+=Math.abs(o.x-c[0].x)+Math.abs(o.y-c[0].y);
        for(int i=0;i<l-1;i++)
        {
        sum+=Math.abs(c[i].x-c[i+1].x)+Math.abs(c[i].y-c[i+1].y);    
        }
        sum+=Math.abs(c[l-1].x-h.x)+Math.abs(c[l-1].y-h.y);
        return sum;
    }
    
    public void bctrack(pair o,pair h,pair a[],int l, int hi)
    {
        if(l==hi)
        {
            int d=calcDist(o,h,a);
            mind.d=Math.min(d,mind.d);
            return;
        }
            for(int i=l;i<=hi;i++)
        {
            swap(a,l,i);
            bctrack(o,h,a,l+1,hi);
            swap(a,l,i);
        }
    }
	public static void main (String[] args) {
	    Scanner sc=new Scanner(System.in);
	    int t=sc.nextInt();
	    GFG ob=new GFG();
	    int tt=0;
	    while(t-->0)
	    {
	        tt++;
	        mind.d=Integer.MAX_VALUE;
	     int n=sc.nextInt();
	     pair[] customers=new pair[n];
	     pair off=new pair(sc.nextInt(),sc.nextInt());
	     pair home=new pair(sc.nextInt(),sc.nextInt());
	     for(int i=0;i<n;i++)
	     {
	         customers[i]=new pair(sc.nextInt(),sc.nextInt());
	     }
	        ob.bctrack(off,home,customers,0,n-1);
	        System.out.println("#"+tt+" "+mind.d);
	    }
	}
}

}

- Shivam Kanodia September 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
import java.lang.Math;
class GFG {
    
    static class pair
    {
        int x,y;
        public pair(int x,int y)
        {
            this.x=x;
            this.y=y;
        }
    }
    static class mind
    {
        static int d=Integer.MAX_VALUE;
    }
    
    void swap(pair ar[],int x,int y)
    {
        pair temp=ar[x];
        ar[x]=ar[y];
        ar[y]=temp;
    }
    
    int calcDist(pair o,pair h,pair[] c)
    {
        int l=c.length;
        int sum=0;
        sum+=Math.abs(o.x-c[0].x)+Math.abs(o.y-c[0].y);
        for(int i=0;i<l-1;i++)
        {
        sum+=Math.abs(c[i].x-c[i+1].x)+Math.abs(c[i].y-c[i+1].y);    
        }
        sum+=Math.abs(c[l-1].x-h.x)+Math.abs(c[l-1].y-h.y);
        return sum;
    }
    
    public void bctrack(pair o,pair h,pair a[],int l, int hi)
    {
        if(l==hi)
        {
            int d=calcDist(o,h,a);
            mind.d=Math.min(d,mind.d);
            return;
        }
            for(int i=l;i<=hi;i++)
        {
            swap(a,l,i);
            bctrack(o,h,a,l+1,hi);
            swap(a,l,i);
        }
    }
	public static void main (String[] args) {
	    Scanner sc=new Scanner(System.in);
	    int t=sc.nextInt();
	    GFG ob=new GFG();
	    int tt=0;
	    while(t-->0)
	    {
	        tt++;
	        mind.d=Integer.MAX_VALUE;
	     int n=sc.nextInt();
	     pair[] customers=new pair[n];
	     pair off=new pair(sc.nextInt(),sc.nextInt());
	     pair home=new pair(sc.nextInt(),sc.nextInt());
	     for(int i=0;i<n;i++)
	     {
	         customers[i]=new pair(sc.nextInt(),sc.nextInt());
	     }
	        ob.bctrack(off,home,customers,0,n-1);
	        System.out.println("#"+tt+" "+mind.d);
	    }
	}

- Shivam Kanodia September 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
        #define mod 1000000007
        #define pb push_back
        #define mp make_pair
        #define int long long
        #define nodes 100001
        #define level 18  // ceil(log2(nodes))
        #define N 15000005
        using namespace std;

        int n;
        vector<pair<int,int>>arr;
        pair<int,int>start,endd;
        map<pair<int,int>,bool>visited;
        int ans = INT_MAX;
        void dfs(pair<int,int>&x , pair<int,int>&prev, int cost)
        {
            visited[x]=1;
            //cout<<cost<<" ";
            bool flag = 1;
            if(start != x) cost += abs(x.first - prev.first) + abs(x.second - prev.second);
            for(int i=0;i<n;i++)
            {
                if(!visited[arr[i]]) 
                {
                    flag = 0;
                    dfs(arr[i] , x , cost);
                    visited[arr[i]] = 0;
                }
            }

            cost +=abs(endd.first - x.first) + abs(endd.second - x.second);
            
            if(flag) ans = min(ans,cost); //, cout<<cost<<" ";
            //cout<<"\n\n\n";
        }

        int32_t main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
           
          
         
        cin>>n;

        int x,y;
        cin>>x>>y;

        start = mp(x,y);
        cin>>x>>y;
        endd = mp(x,y);

        for(int i=1;i<=n;i++) 
        {
            cin>>x>>y;

            arr.pb(mp(x,y));
        }
        pair<int,int>prev;
        prev = mp(0,0);
        dfs(start,prev,0);     

        cout<<ans;   
        return 0;
    }

- Anonymous September 27, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More