Samsung Interview Question Software Engineers
Country: India
Interview Type: Written Test
{
var min ;
S ---> W1 ---> W2 ----> W3 ----> ... ---> WN -----> D
1. take all permutations (recursion) of Wi to reach D .
2. update the distance( manhattan ) for the trip and check if value of the trip is < min
update min ;
print min ;
}
{take for both starting and ending points of wormholes as mentioned in the statement for the logic ..}
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>entry;
vector<pair<int,int>>exit1;
vector<int>cost;
int main()
{
int n;
cin>>n;
int x1,y1,x2,y2,d;
for(int i=0;i<n;i++)
{
cin>>x1>>y1>>x2>>y2>>d;
entry.push_back({x1,y1});
exit1.push_back({x2,y2});
cost.push_back(d);
}
int sx=-1,sy=-1,ex=-1,ey=-1;
cin>>sx>>sy>>ex>>ey;
entry.push_back({sx,sy});
entry.push_back({ex,ey});
exit1.push_back({sx,sy});
exit1.push_back({ex,ey});
cost.push_back(0);
cost.push_back(0);
int dis[n+2][n+2];
memset(dis,0,sizeof(dis));
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(i==j)
continue;
int d1=abs(exit1[i].first-entry[j].first)+abs(exit1[i].second-entry[j].second)+cost[i];
int d2=abs(exit1[i].first-exit1[j].first)+abs(exit1[i].second-exit1[j].second)+cost[i];
d1=min(d1,d2);
dis[i][j]=d;
}
}
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
for(int k=0;k<n+2;k++)
{
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
cout<<dis[n][n+1];
return 0;
}
I think this might work
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>entry;
vector<pair<int,int>>exit1;
vector<int>cost;
int main()
{
int n;
cin>>n;
int x1,y1,x2,y2,d;
for(int i=0;i<n;i++)
{
cin>>x1>>y1>>x2>>y2>>d;
entry.push_back({x1,y1});
exit1.push_back({x2,y2});
cost.push_back(d);
}
int sx=-1,sy=-1,ex=-1,ey=-1;
cin>>sx>>sy>>ex>>ey;
entry.push_back({sx,sy});
entry.push_back({ex,ey});
exit1.push_back({sx,sy});
exit1.push_back({ex,ey});
cost.push_back(0);
cost.push_back(0);
int dis[n+2][n+2];
memset(dis,0,sizeof(dis));
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(i==j)
continue;
int d1=abs(exit1[i].first-entry[j].first)+abs(exit1[i].second-entry[j].second)+cost[i];
int d2=abs(exit1[i].first-exit1[j].first)+abs(exit1[i].second-exit1[j].second)+cost[i];
d1=min(d1,d2);
dis[i][j]=d;
}
}
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
for(int k=0;k<n+2;k++)
{
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
for(int i=0;i<n+2;i++)
{
for(int j=0;j<n+2;j++)
{
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
cout<<dis[n][n+1];
return 0;
}
int d1=abs(exit1[i].first-entry[j].first)+abs(exit1[i].second-entry[j].second)+cost[i];
int d2=abs(exit1[i].first-exit1[j].first)+abs(exit1[i].second-exit1[j].second)+cost[i];
d1=min(d1,d2);
dis[i][j]=d;
Why have you taken the minimum of both distances? According to question, the shortest path from source to destination may take the longer path to a wormhole so as to get shorter path overall.
Difficult assignment to make a closet loophole towards warmhole mystery closer than point for both blackhole rather than whitehole over the space shining with prior glamour of film academy appointment in many session, informer parking at the northport central complex with a limited value.
Transportation neither be intimated with public as well as private so that condonation of delay in transit be reinstatement on event of the day.
Difficult assignment to make a closet loophole towards warmhole mystery closer than point for both blackhole rather than whitehole over the space shining with prior glamour of film academy appointment in many session, informer parking at the northport central complex with a limited value.
Transportation neither be intimated with public as well as private so that condonation of delay in transit be reinstatement on event of the day.
#include <iostream>
using namespace std;
struct grid {
int x;
int y;
};
int main()
{
int n;
cin >> n;
grid s,d;
cin >> s.x >> s.y >> d.x >> d.y;
grid* vertex = new grid[2 * n + 2];
int* a = new int[n];
for (int i = 0;i < 2*n;i+=2) {
cin >> vertex[i].x >> vertex[i].y;
cin >> vertex[i+1].x >> vertex[i+1].y;
cin >> a[i / 2];
}
vertex[2 * n] = s;
vertex[2 * n + 1] = d;
int** graph = new int* [2 * n + 2];
for (int i = 0;i < 2 * n + 2;i++) {
graph[i] = new int[2 * n + 2];
}
int V = 2 * n + 2;
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
graph[i][j] = abs(vertex[i].x - vertex[j].x) + abs(vertex[i].y - vertex[j].y);
}
}
for (int i = 0;i < n;i++) {
if (a[i] < graph[2*i][2*i+1]) {
graph[2 * i][2 * i + 1] = a[i];
graph[2 * i + 1][2 * i] = a[i];
}
}
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
for (int k = 0;k < V;k++) {
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
cout << graph[2 * n][2 * n + 1];
return 0;
}
#include <iostream>
using namespace std;
struct grid {
int x;
int y;
};
int main()
{
int n;
cin >> n;
grid s,d;
cin >> s.x >> s.y >> d.x >> d.y;
grid* vertex = new grid[2 * n + 2];
int* a = new int[n];
for (int i = 0;i < 2*n;i+=2) {
cin >> vertex[i].x >> vertex[i].y;
cin >> vertex[i+1].x >> vertex[i+1].y;
cin >> a[i / 2];
}
vertex[2 * n] = s;
vertex[2 * n + 1] = d;
int** graph = new int* [2 * n + 2];
for (int i = 0;i < 2 * n + 2;i++) {
graph[i] = new int[2 * n + 2];
}
int V = 2 * n + 2;
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
graph[i][j] = abs(vertex[i].x - vertex[j].x) + abs(vertex[i].y - vertex[j].y);
}
}
for (int i = 0;i < n;i++) {
if (a[i] < graph[2*i][2*i+1]) {
graph[2 * i][2 * i + 1] = a[i];
graph[2 * i + 1][2 * i] = a[i];
}
}
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
for (int k = 0;k < V;k++) {
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
cout << graph[2 * n][2 * n + 1];
return 0;
}
#include <iostream>
using namespace std;
struct grid {
int x;
int y;
};
int main()
{
int n;
cin >> n;
grid s,d;
cin >> s.x >> s.y >> d.x >> d.y;
grid* vertex = new grid[2 * n + 2];
int* a = new int[n];
for (int i = 0;i < 2*n;i+=2) {
cin >> vertex[i].x >> vertex[i].y;
cin >> vertex[i+1].x >> vertex[i+1].y;
cin >> a[i / 2];
}
vertex[2 * n] = s;
vertex[2 * n + 1] = d;
int** graph = new int* [2 * n + 2];
for (int i = 0;i < 2 * n + 2;i++) {
graph[i] = new int[2 * n + 2];
}
int V = 2 * n + 2;
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
graph[i][j] = abs(vertex[i].x - vertex[j].x) + abs(vertex[i].y - vertex[j].y);
}
}
for (int i = 0;i < n;i++) {
if (a[i] < graph[2*i][2*i+1]) {
graph[2 * i][2 * i + 1] = a[i];
graph[2 * i + 1][2 * i] = a[i];
}
}
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
for (int k = 0;k < V;k++) {
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
cout << graph[2 * n][2 * n + 1];
return 0;
}
#include<iostream>
using namespace std;
int ans,mask[10],w[10][5],n;
int distance(int sx,int sy,int dx,int dy) {
int xd=(sx>dx)?(sx-dx):(dx-sx);
int yd=(sy>dy)?(sy-dy):(dy-sy);
return (xd+yd);
}
void cal(int sx,int sy,int dx,int dy,int dis) {
ans=min(ans,distance(sx,sy,dx,dy)+dis);
for(int i=0;i<n;i++) {
if(mask[i]==0) {
mask[i]=1;
int temp=distance(sx,sy,w[i][0],w[i][1])+dis+w[i][4];
cal(w[i][2],w[i][3],dx,dy,temp);
temp=distance(sx,sy,w[i][2],w[i][3])+dis+w[i][4];
cal(w[i][0],w[i][1],dx,dy,temp);
mask[i]=0;
}
}
}
int main() {
int t;
cin>>t;
while(t--) {
cin>>n;
int sx,sy,dx,dy;
cin>>sx>>sy>>dx>>dy;
for(int i=0;i<n;i++) {
mask[i]=0;
for(int j=0;j<5;j++) {
cin>>w[i][j];
}
}
ans=999999;
cal(sx,sy,dx,dy,0);
cout<<ans<<endl;
}
return 0;
}
- Mei Li February 12, 2017import java.util.*; public class SpaceShipProblem { public static void main(String[] args) { Coordinate source = new Coordinate(0, 0); Coordinate dest = new Coordinate(100, 200); /* WarmHole wh1 = WarmHole wh2 = ... WarmHole whk = */ List<WarmHole> list = new ArrayList<WarmHole>(); /* list.add... */ WHPath minPath = findMinPath(source, dest, list); } public static WHPath findMinPath(Coordinate source, Coordinate dest, List<WarmHole> list) { if (source.x == dest.x && source.y == dest.y) { return new WHPath(null, 0); } WHPath minPath = null; Set<WarmHole> markout = new HashSet<WarmHole>(); for (WarmHole wh : list) { if (markout.contains(wh)) { continue; } markout.add(wh); Iterator<Coordinate> it = wh.pairs.iterator(); Coordinate whpointA = null; Coordinate whpointB = null; if (it.hasNext()) { whpointA = it.next(); } if (it.hasNext()) { whpointB = it.next(); } //find minPath from left and right point of the warm hole, compare which one is better to use WHPath pathA = findMinPath(whpointB, dest, list); WHPath pathB = findMinPath(whpointA, dest, list); List<WarmHole> path = null; int distance = 0; if (findDistance(source, whpointB) + pathA.distance < findDistance( source, whpointA) + pathB.distance) { path = pathB.path; distance = findDistance(source, whpointB) + pathA.distance; } else { path = pathA.path; distance = findDistance(source, whpointA) + pathB.distance; } if (path != null) { if (minPath == null) { minPath = new WHPath(path, distance); } else if (distance < minPath.distance) { minPath.distance = distance; minPath.path = path; } } } return minPath; } public static int findDistance(Coordinate source, Coordinate dest) { return Math.abs(source.x - dest.x) + Math.abs(source.y - dest.y); } } class WHPath { int distance; List<WarmHole> path; WHPath(List<WarmHole> path, int distance) { this.path = path; this.distance = distance; }; } class Coordinate { int x; int y; Coordinate(int x, int y) { this.x = x; this.y = y; }; } class WarmHole { Set<Coordinate> pairs = new HashSet<Coordinate>(); WarmHole(Coordinate a, Coordinate b) { pairs.add(a); pairs.add(b); }; }