Flipkart Interview Question for Software Engineers


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)

- User123 July 26, 2015 | Flag Reply
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).

- StrictMath August 07, 2015 | Flag Reply
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() {
	// 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;

- Pallavi August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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??

- vishgupta92 August 17, 2015 | Flag
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() {
	// 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;

- Pallavi August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

- Pallavi August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

###sffkshfkdf

- Pallavi August 02, 2015 | Flag Reply
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() {
	// 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;
}

- Pallavi August 02, 2015 | Flag Reply
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.

- Phoenix September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sumanth October 01, 2022 | Flag
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

- wolfofsv August 21, 2021 | Flag Reply
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?

- Yev July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous July 29, 2015 | 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