shrishty
BAN USER
Comments (9)
Reputation 15
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
This is the recursive solution. Can easily be mapped to dynamic programming
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minSteps(int M[5][5], int index, unordered_map<int, int> m, bool left)
{
cout<<"index = "<<index<<" isleft = "<<left<<endl;
if(index >= 5)
{
cout<<"Recursion ended"<<endl;
return 0;
}
int steps = 0;
if(m.find(index) != m.end())
{
if(left)
{
for(int j = 0; j < 5; j++)
{
steps++;
if(M[index][j] == 0)
{
m[index] = 1;
if(m[index] == 0)
{
return min(5 + minSteps(M, index+1, m, false),
2 * steps  1 + minSteps(M, index + 1, m, true));
}
}
}
}
else
{
for(int j = 4; j >=0; j)
{
steps++;
if(M[index][j] == 0)
{
m[index] = 1;
if(m[index] == 0)
{
return min(5 + minSteps(M, index + 1, m, true),
2 * steps  1 + minSteps(M, index + 1, m, false));
}
}
}
}
}
else
{
if(left)
{
return min(5 + minSteps(M, index + 1, m, false),
0 + minSteps(M, index + 1, m, true));
}
else
{
return min(5 + minSteps(M, index + 1, m, true),
0 + minSteps(M, index + 1, m, false));
}
}
return 0;
}
int main()
{
vector<pair<int, int>> ls = { {1, 1}, {1, 4}, {2, 2}, {3, 4}};
int R, C;
R = 5; C = 5;
int M[5][5];
unordered_map<int,int> m;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
M[i][j] = 1;
}
}
for(auto itr: ls)
{
M[itr.first][itr.second] = 0;
if(m.find(itr.first) == m.end())
{
m[itr.first] = 1;
}
else
{
m[itr.first] += 1;
}
}
cout<<minSteps(M, 0, m, true)<<endl;
return 0;
}

shrishty
February 24, 2018 Comment hidden because of low score. Click to expand.
1
of 1 vote
The code can be beautified. I have assumed matrix size is 5x5 but it can be easily generalized.
int[][] room = new int[][]{
{1,1,1,1,1},
{1,0,1,1,0},
{1,1,0,1,1},
{1,1,1,1,0},
{1,1,1,1,1}
};
this is the sequence of steps  (1, 0), (1, 1), (1, 2), (1,3),(1,4), (2,4), (2,3),(2,2),(2,3),(2,4),(3,4)
All computers are repaired at this point.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
I dont think maps would work here.
 shrishty October 17, 2018Consider this example
p1 > a, b, c
p2 > d
p3 > d, a
p4 > e
in this case there is only one unique contact that is p1. This problem can be thought as a graph problem where we care supposed to find all disconnected graphs.
In above example p1, p2 and p3 are connected together hence same contact. p4 is disconnected.