Samsung Interview Question for Software Developers

Country: India
Interview Type: Written Test

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

Looks like a TSP, which is a O(2^n) problem.
This is why I created a greedy algorithm:

``````object ShortestDeliveryPath {
val officeLocation = Location(0,0)
val homeLocation = Location(100,100)
val deliveryLocations = List((20,30), (50,50), (70,70)).map(Location.tupled)

case class Location(x: Int, y: Int)

def main (args: Array[String]) {
val route = calculateRoute()
println(route)
}

def calculateRoute() = {
val nextLocation = closestLocation(location, processedLocations)
nextLocation.map(loc => go(loc, processedLocations + location)).getOrElse(processedLocations)
}
val route = (go(officeLocation, new mutable.LinkedHashSet()+officeLocation) + homeLocation).toList
(route, routeDistance(route))
}

def routeDistance(route: List[Location]): Int = {
route.sliding(2).map{case List(x, y) => distance(x, y)}.sum
}

def closestLocation(currentLocation: Location, processedLocations: mutable.LinkedHashSet[Location]): Option[Location] = {
deliveryLocations
.filterNot(processedLocations.contains)
.map(loc => (loc, distance(loc, currentLocation)))
.reduceOption((x, y) => if(x._2 < y._2) x else y)
.map(_._1)
}

def distance(location1: Location, location2: Location) = Math.abs(location1.x - location2.x) + Math.abs(location1.y - location2.y)
}``````

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

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

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

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

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

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

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

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

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.

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.