Samsung Interview Question for Software Engineers


Country: India
Interview Type: Written Test




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

import 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);
	};
}

- Mei Li February 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

please give c++ code

- jitin August 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

{
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 ..}

- Daljit Singh March 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra's algorithm
But I don't understand what we need to minimize?
Sum of costs (5th value) or sum of distances abs(x1-x2)+abs(y1-y2) ?

- dmitry.labutin February 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can you please explain the code.

- sunny.1rn12cs113 March 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you give c++ code ?

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

The solution to the problem can be solved by using dynamic programming + backtracking

- Akhil Guttula June 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Akhil. Can you send the code?

- Sourav August 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Shivi_Chan August 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ShiviChan August 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

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

#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;
}

- erpankr56070 November 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you give sample input and output?

- aeshaa55 November 28, 2018 | Flag


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