Flipkart Interview Question
Software EngineersCountry: India
Interview Type: Written Test
Represent the starting point, ending point and the cheese positions as vertices of a graph. The problem of visiting all vertices in a graph is called the Travelling salesman problem. TSP has a dynamic programming solution, although the best you could do with this is reducing the complexity from O(n!) to O(n^2 * 2^n).
Here starting from the tom position , i am finding the nearest cheese , then from this current position i am traversing all the cheese. And from the last cheese position i am moving towards jerry.
#include <iostream>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
struct point
{
long long x,y,searched=0;
};
struct ans
{
int index=0;
int steps=0;
}a;
struct ans fun(vector<point> v,struct ans a,int start,int k)
{
v[start].searched=1;
if(k==0) return a;
else
{
double diff_x, diff_y;
int i=0;
while(v[i].searched ==1 && i<v.size()-1){i++;}
diff_x = abs(v[start].x - v[i].x);
diff_y = abs(v[start].y - v[i].y);
int best = i;
double best_dist = sqrt(pow(diff_x,2)+ pow(diff_y,2));
double hold_dist;
for(int j=i+1; j<(int)v.size()-1; ++j)
{
if(v[j].searched !=1)
{
diff_x = abs(v[start].x - v[j].x);
diff_y = abs(v[start].y - v[j].y);
hold_dist=sqrt(pow(diff_x,2)+pow(diff_y,2));
if(hold_dist < best_dist)
{
best_dist = hold_dist;
best = j;
}
}
}
v[best].searched=1;
diff_x=abs(v[best].x- v[start].x);
diff_y=abs(v[best].y- v[start].y);
a.steps=a.steps+std::max(diff_x,diff_y);
a.index=best;
k=k-1;
return fun(v,a,best,k);
}
}
int main() {
// your code goes here
vector<point> v;
int k;
cin>>k;
point p;
for(int i=0;i<=k+1;i++)
{
if(i==0) {p.x=0;p.y=0;}
else{cin >> p.x ;
cin >> p.y;}
v.push_back(p);
}
ans a;
a=fun(v,a,0,k);
// steps to reach to jerry
double diff_x, diff_y;
diff_x=abs(v[a.index].x-v[k+1].x);
diff_y=abs(v[a.index].y-v[k+1].y);
a.steps=a.steps+max(diff_x,diff_y);
cout << a.steps;
return 0;
#include <iostream>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
struct point
{
long long x,y,searched=0;
};
struct ans
{
int index=0;
int steps=0;
}a;
struct ans fun(vector<point> v,struct ans a,int start,int k)
{
v[start].searched=1;
if(k==0) return a;
else
{
double diff_x, diff_y;
int i=0;
while(v[i].searched ==1 && i<v.size()-1){i++;}
diff_x = abs(v[start].x - v[i].x);
diff_y = abs(v[start].y - v[i].y);
int best = i;
double best_dist = sqrt(pow(diff_x,2)+ pow(diff_y,2));
double hold_dist;
for(int j=i+1; j<(int)v.size()-1; ++j)
{
if(v[j].searched !=1)
{
diff_x = abs(v[start].x - v[j].x);
diff_y = abs(v[start].y - v[j].y);
hold_dist=sqrt(pow(diff_x,2)+pow(diff_y,2));
if(hold_dist < best_dist)
{
best_dist = hold_dist;
best = j;
}
}
}
v[best].searched=1;
diff_x=abs(v[best].x- v[start].x);
diff_y=abs(v[best].y- v[start].y);
a.steps=a.steps+std::max(diff_x,diff_y);
a.index=best;
k=k-1;
return fun(v,a,best,k);
}
}
int main() {
// your code goes here
vector<point> v;
int k;
cin>>k;
point p;
for(int i=0;i<=k+1;i++)
{
if(i==0) {p.x=0;p.y=0;}
else{cin >> p.x ;
cin >> p.y;}
v.push_back(p);
}
ans a;
a=fun(v,a,0,k);
// steps to reach to jerry
double diff_x, diff_y;
diff_x=abs(v[a.index].x-v[k+1].x);
diff_y=abs(v[a.index].y-v[k+1].y);
a.steps=a.steps+max(diff_x,diff_y);
cout << a.steps;
return 0;
#include <iostream>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
struct point
{
long long x,y,searched=0;
};
struct ans
{
int index=0;
int steps=0;
}a;
struct ans fun(vector<point> v,struct ans a,int start,int k)
{
v[start].searched=1;
if(k==0) return a;
else
{
double diff_x, diff_y;
int i=0;
while(v[i].searched ==1 && i<v.size()-1){i++;}
diff_x = abs(v[start].x - v[i].x);
diff_y = abs(v[start].y - v[i].y);
int best = i;
double best_dist = sqrt(pow(diff_x,2)+ pow(diff_y,2));
double hold_dist;
for(int j=i+1; j<(int)v.size()-1; ++j)
{
if(v[j].searched !=1)
{
diff_x = abs(v[start].x - v[j].x);
diff_y = abs(v[start].y - v[j].y);
hold_dist=sqrt(pow(diff_x,2)+pow(diff_y,2));
if(hold_dist < best_dist)
{
best_dist = hold_dist;
best = j;
}
}
}
v[best].searched=1;
diff_x=abs(v[best].x- v[start].x);
diff_y=abs(v[best].y- v[start].y);
a.steps=a.steps+std::max(diff_x,diff_y);
a.index=best;
k=k-1;
return fun(v,a,best,k);
}
}
int main() {
// your code goes here
vector<point> v;
int k;
cin>>k;
point p;
for(int i=0;i<=k+1;i++)
{
if(i==0) {p.x=0;p.y=0;}
else{cin >> p.x ;
cin >> p.y;}
v.push_back(p);
}
ans a;
a=fun(v,a,0,k);
// steps to reach to jerry
double diff_x, diff_y;
diff_x=abs(v[a.index].x-v[k+1].x);
diff_y=abs(v[a.index].y-v[k+1].y);
a.steps=a.steps+max(diff_x,diff_y);
cout << a.steps;
return 0;
}
you need to do BFS from tom position to Jerry position and between them count the number of nodes / cells which has cheese. If count < k, remove this path else count the nodes in between. At the end of every traversal which has cheese count = k, compare total path with minimum path saved in variable. If it is less than previous then set new minimum or just ignore that. At last print the number.
is it the case that
1. start from tom and make a bfs and choose the closest cheese lets say cheese_i1
2. Start from cheese_i1 and make a bfs and travel to the closest unused cheese lets say cheese_i2
3. start from cheese_i2 and reach the next closest cheese
....
11. after visiting all the cheese items, find the closest path to reach the jerry
so summation of all these path lengths would give us the required output
please let me know if I'm missing something
This is a tricky problem indeed. However, this is a shortest-path problem, of which are several solutions. There are at least 2 common algos, one of which is Dijkstra. For simplicity, you can use DFS to find the min path. It would have linear running time O(|V|+|E|), and storage O(|V|). When you find a new path, compare the distance of the new path to the old path. Anyhow, that's how I would start. What'd you think?
Since you have to collect all k cheese blocks, there are max k! ways to do this, which is worst case 10! ways.
- User123 July 26, 2015Thus for each value in this 10! you would need to do BFS from (0,0) to cheese1. Then BFS from cheese1 to cheese2 and so on.. You then take min of all such paths
For example for a smaller k=3, you can have
origin->c1->c2->c3->jerry
origin->c1->c3->c2->jerry
origin->c2->c1->c3->jerry
origin->c2->c3->c1->jerry
origin->c3->c1->c2->jerry
origin->c3->c2->c1->jerry
making it 3!= 6 ways to do so.
You can obviously memoise this and bring down the complexity to O(k^2) from O(k!)
(Or you can do bottom up by storing BFS min value for cheeses at any two points ci and cj)
So you would be doing k BFS, bringing the complexity to k*O(V+E)*k^2 = k^3*O(V+E)