## Flipkart Interview Question for Software Engineers

• 0

Country: India
Interview Type: Written Test

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

Since you have to collect all k cheese blocks, there are max k! ways to do this, which is worst case 10! ways.
Thus 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)

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

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).

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

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() {
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;``````

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

Where you have taken input as Jerry Position???
And please also tell me how distance formula will work here because there may be many block cell will be in the direct path between them??

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

``````#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() {
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;``````

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

``#include <iostream>``

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

``###sffkshfkdf``

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

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

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

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.

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

This solution will give TLE, as you are searching for all possible paths.

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

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

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

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?

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

How do you account for the fact that your path has to collect all the pieces of cheese, not just one of them?

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.