ADP Interview Question
abcsCountry: India
Interview Type: Written Test
Note: Just wrote this up. Please check, I didn't run this code to confirm if its bug-free.
Assuming all the costs are non-negative, We can use Dynamic Programming method. There are different ways to parse the string to a 2D array. we can get the numbers and insert them row by row into a 2D array.
Assuming we have done that and parsed them into a 2D vector array Paths, then
class MinimumCost{
Public:
unsigned int getMin(std::vector<vector<int> > &Paths, int i, int j){
int up = INT_MAX, left = INT_MAX, Diag = INT_MAX
if(i - 1 >= 0){
up = Paths[i-1][j];
if(j - 1) >= 0)Diag = Paths[i-1][j-1];
}
if (j - 1) >= 0){
left = Paths[i][j-1];
}
unsigned int Min = std::min(left,min(up, Diag));
if( Min == INT_MAX) return 0;
return Min;
}
std::string BackTrack(std::vector<vector<int> > &PathCosts, int i, int j){
std::string Path = “”;
while(i >= 0 || j >=0){
int Min = getMin(PathCosts,i,j);
if ( i -1 >= 0 && Min == PathCosts[i-1][j]){
i = i - 1;
Path = “R” + Path;
}else if (i -1 >= 0 && j -1 >= 0 && Min == PathCosts[i-1][j-1]{
i = i - 1;
j = j - 1;
Path = “D” + Path;
}else {
j = j -1;
Path = “B” + Path;
}
}
return Path;
}
std::string getShortestPath(std::vector<vector<int> > Paths){
std::vector<vector<int> > PathCosts;
int len = Paths.size();
std::string Path = “”;
PathCosts.resize(len);
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
PathCost[i].resize(len);
PathCost[i][j] = Paths[i][j] + getMin(Paths,i,j);
}
}
return std::to_string(PathCost[len - 1][len - 1]) + “,” + BackTrack(PathCost, len - 1, len - 1);
}
};
Note: Just wrote this up. Please check, I didn't run this code to confirm if its bug-free.
Assuming all the costs are non-negative, We can use Dynamic Programming method. There are different ways to parse the string to a 2D array. we can get the numbers and insert them row by row into a 2D array.
Assuming we have done that and parsed them into a 2D vector array Paths, then
class MinimumCost{
Public:
unsigned int getMin(std::vector<vector<int> > &Paths, int i, int j){
int up = INT_MAX, left = INT_MAX, Diag = INT_MAX
if(i - 1 >= 0){
up = Paths[i-1][j];
if(j - 1) >= 0)Diag = Paths[i-1][j-1];
}
if (j - 1) >= 0){
left = Paths[i][j-1];
}
unsigned int Min = std::min(left,min(up, Diag));
if( Min == INT_MAX) return 0;
return Min;
}
std::string BackTrack(std::vector<vector<int> > &PathCosts, int i, int j){
std::string Path = “”;
while(i >= 0 || j >=0){
int Min = getMin(PathCosts,i,j);
if ( i -1 >= 0 && Min == PathCosts[i-1][j]){
i = i - 1;
Path = “R” + Path;
}else if (i -1 >= 0 && j -1 >= 0 && Min == PathCosts[i-1][j-1]{
i = i - 1;
j = j - 1;
Path = “D” + Path;
}else {
j = j -1;
Path = “B” + Path;
}
}
return Path;
}
std::string getShortestPath(std::vector<vector<int> > Paths){
std::vector<vector<int> > PathCosts;
int len = Paths.size();
std::string Path = “”;
PathCosts.resize(len);
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
PathCost[i].resize(len);
PathCost[i][j] = Paths[i][j] + getMin(Paths,i,j);
}
}
return std::to_string(PathCost[len - 1][len - 1]) + “,” + BackTrack(PathCost, len - 1, len - 1);
}
};
class CandidateCode {static void main(String[] args) throws java.lang.Exception {String s[] = { "5#7#2#4", "1#8#1#3", "6#2#9#5", "1#6#2#8" };minimumCost(s, 4);}public static String minimumCost(String[] input1, int input2) {int m = 4;int n = 4;int cost[][] = new int[m][n];for (int i = 0; i < m; i++) {String ary[] = input1[i].split("#");for (int j = 0; j < n; j++) {cost[i][j] = Integer.parseInt(ary[j]);}}int minCost = MCPath(cost, m, n);System.out.printf(" Min " + minCost);return "";}static int MCPath(int cost[][], int m, int n) {int dp[][] = new int[m][n];String direction[][] = new String[m][n];dp[0][0] = cost[0][0];direction[0][0] = "";int i;int j;for ( i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + cost[i][0];direction[i][0] = "B";}for ( j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + cost[0][j];direction[0][j] = "R";}for ( i = 1; i < m; i++)for ( j = 1; j < n; j++)dp[i][j] = cost[i][j] + min(direction, i, j, dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);return dp[m - 1][n - 1];}static String getPath(int dp[][], String direction[][], int m, int n) {if (m == 0 & n == 0)return "";else {int cnt = min(dp[m - 1][n], dp[m][n - 1], dp[m-1][n - 1]);if (cnt == 1)m--;else if (cnt == 2)n--;else {m--;n--;}return direction[m][n] + "" + getPath(dp, direction, m, n);}}static int min(String direction[][], int i, int j, int x, int y, int z) {if (x <= y) {if (x <= z) {direction[i][j] = "R";return x;}} else {if (y <= z) {direction[i][j] = "B";return y;}}direction[i][j] = "D";return z;}static int min(int x, int y, int z) {if (x < y)return (x < z) ? 1 : 3;else return (y < z) ? 1 : 3;}static String direction(int selectedM, int selectedN, int m, int n) {if (selectedM < m && selectedN < n) {return "D";} else if (selectedM == m && selectedN < n) {return "R";} else if (selectedM < m && selectedN == n) {return "B";}return "T";}}
not getting shortestpath correctly but minimumcost value is correct
class CandidateCode {static void main(String[] args) throws java.lang.Exception {String s[] = { "5#7#2#4", "1#8#1#3", "6#2#9#5", "1#6#2#8" };minimumCost(s, 4);}public static String minimumCost(String[] input1, int input2) {int m = 4;int n = 4;int cost[][] = new int[m][n];for (int i = 0; i < m; i++) {String ary[] = input1[i].split("#");for (int j = 0; j < n; j++) {cost[i][j] = Integer.parseInt(ary[j]);}}int minCost = MCPath(cost, m, n);System.out.printf(" Min " + minCost);return "";}static int MCPath(int cost[][], int m, int n) {int dp[][] = new int[m][n];String direction[][] = new String[m][n];dp[0][0] = cost[0][0];direction[0][0] = "";int i;int j;for ( i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + cost[i][0];direction[i][0] = "B";}for ( j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + cost[0][j];direction[0][j] = "R";}for ( i = 1; i < m; i++)for ( j = 1; j < n; j++)dp[i][j] = cost[i][j] + min(direction, i, j, dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);return dp[m - 1][n - 1];}static String getPath(int dp[][], String direction[][], int m, int n) {if (m == 0 & n == 0)return "";else {int cnt = min(dp[m - 1][n], dp[m][n - 1], dp[m-1][n - 1]);if (cnt == 1)m--;else if (cnt == 2)n--;else {m--;n--;}return direction[m][n] + "" + getPath(dp, direction, m, n);}}static int min(String direction[][], int i, int j, int x, int y, int z) {if (x <= y) {if (x <= z) {direction[i][j] = "R";return x;}} else {if (y <= z) {direction[i][j] = "B";return y;}}direction[i][j] = "D";return z;}static int min(int x, int y, int z) {if (x < y)return (x < z) ? 1 : 3;else return (y < z) ? 1 : 3;}static String direction(int selectedM, int selectedN, int m, int n) {if (selectedM < m && selectedN < n) {return "D";} else if (selectedM == m && selectedN < n) {return "R";} else if (selectedM < m && selectedN == n) {return "B";}return "T";}}
class CandidateCode {static void main(String[] args) throws java.lang.Exception {String s[] = { "5#7#2#4", "1#8#1#3", "6#2#9#5", "1#6#2#8" };minimumCost(s, 4);}static String minimumCost(String[] input1, int input2) {int m = 4;int n = 4;int cost[][] = new int[m][n];for (int i = 0; i < m; i++) {String ary[] = input1[i].split("#");for (int j = 0; j < n; j++) {cost[i][j] = Integer.parseInt(ary[j]);}}int minCost = MCPath(cost, m, n);System.out.printf(" Min " + minCost);return "";}static int MCPath(int cost[][], int m, int n) {int dp[][] = new int[m][n];String direction[][] = new String[m][n];dp[0][0] = cost[0][0];direction[0][0] = "";int i;int j;for ( i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + cost[i][0];direction[i][0] = "B";}for ( j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + cost[0][j];direction[0][j] = "R";}for ( i = 1; i < m; i++)for ( j = 1; j < n; j++)dp[i][j] = cost[i][j] + min(direction, i, j, dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);return dp[m - 1][n - 1];}static String getPath(int dp[][], String direction[][], int m, int n) {if (m == 0 & n == 0)return "";else {int cnt = min(dp[m - 1][n], dp[m][n - 1], dp[m-1][n - 1]);if (cnt == 1)m--;else if (cnt == 2)n--;else {m--;n--;}return direction[m][n] + "" + getPath(dp, direction, m, n);}}static int min(String direction[][], int i, int j, int x, int y, int z) {if (x <= y) {if (x <= z) {direction[i][j] = "R";return x;}} else {if (y <= z) {direction[i][j] = "B";return y;}}direction[i][j] = "D";return z;}static int min(int x, int y, int z) {if (x < y)return (x < z) ? 1 : 3;else return (y < z) ? 1 : 3;}static String direction(int selectedM, int selectedN, int m, int n) {if (selectedM < m && selectedN < n) {return "D";} else if (selectedM == m && selectedN < n) {return "R";} else if (selectedM < m && selectedN == n) {return "B";}return "T";}}
char* minimumCost(char* input1[],int input2)
{
//Write code here
vector< vector<int> > v(input2),vc;
vector< vector<string> > vs(input2);
int r=input2,i,t,j,c,minm;
for(i=0;i<r;i++)
{
j=0; t=0; c=0;
while(arr[i][j]!='\0')
{
if(arr[i][j]=='#')
{
v[i].pb(t);
t=0;
c++;
}
else
t=t*10+arr[i][j]-'0';
j++;
}
v[i].pb(t);
}
c++;
vc=v;
vs[0].pb("\0");
string str;
for(i=1;i<r;i++)
{
v[i][0]+=v[i-1][0];
str=str+'B';
vs[i].pb(str);
}
str="";
for(i=1;i<c;i++)
{
v[0][i]+=v[0][i-1];
str=str+'R';
vs[0].pb(str);
}
for(i=1;i<r;i++)
{
for(j=1;j<c;j++)
{
minm=min(v[i-1][j-1],min(v[i-1][j],v[i][j-1]));
if(v[i-1][j-1]==minm)
{
v[i][j]+=v[i-1][j-1];
vs[i].pb(vs[i-1][j-1]+'D');
}
else if(v[i-1][j]==minm)
{
v[i][j]+=v[i-1][j];
vs[i].pb(vs[i-1][j]+'B');
}
else
{
v[i][j]+=v[i][j-1];
vs[i].pb(vs[i][j-1]+'R');
}
}
}
ostringstream os;
os<<v[r-1][c-1];
printf("%d\n",v[r-1][c-1]);
str=os.str() + "," + vs[r-1][c-1]+ '\0';
cout<<str<<endl;
char *s=(char*)malloc(str.length()+1);
strcpy(s,str.c_str());
//printf("%s\n",s);
return s;
}
int main()
{
//char *arr[26]={"1#3","4#5","7#12","20#23","23#24"};
//char *arr[26]={"1#4","2#3","3#4"};
//char *arr[26]={"1#2","1#3","2#3","3#4","4#7","5#6","4#5"};
char *arr[100]={"5#7#2#4","1#8#1#3","6#2#9#5","1#6#2#8"};
//char *arr[100]={"1#7#2#4","1#8#1#3","1#9#9#5","1#1#1#1"};
//minimumCost(arr,4);
printf("%s\n",minimumCost(arr,4));
// _getche();
}
import java.io.*;
import java.util.*;
import java.lang.*;
class test {
public static void main(String[] args) throws java.lang.Exception {
String abc = "5#7#2#4,1#8#1#3,6#2#9#5,1#6#2#8";
minimumCost(abc, 4);
// your code goes here
}
public static String minimumCost(String input1, int input2) {
int i, j;
String[] str1 = input1.split(",");
int[][] matrix = new int[str1.length][];
for (i = 0; i < matrix.length; i++) {
String[] str2 = str1[i].split("#");
matrix[i] = new int[str2.length];
for (j = 0; j < matrix[i].length; j++) {
matrix[i][j] = Integer.parseInt(str2[j]);
}
}
int m = i, temp = 0;
int cost = 0, k = 0;
String[] code = new String[4];
code[0] = "B";
code[1] = "D";
code[2] = "R";
int[] codeint = new int[m];
cost = matrix[0][0];
for (i = 0; i < m;) {
for (j = i; j < m;) {
if (matrix[i][j + 1] > 0) {
temp = cost + matrix[i][j + 1];
codeint[k] = 2;
}
if (matrix[i + 1][j] > 0)
if (temp > cost + matrix[i + 1][j]) {
temp = cost + matrix[i + 1][j];
codeint[k] = 0;
}
if (matrix[i + 1][j + 1] > 0)
if (temp > cost + matrix[i + 1][j + 1]) {
temp = cost + matrix[i + 1][j + 1];
codeint[k] = 1;
}
switch (codeint[k]) {
case 0:
i++;
break;
case 1:
i++;
j++;
break;
case 2:
j++;
break;
}
k++;
cost = temp;
}
}
// System.out.print(cost);
String res = String.format("%d", cost);
// return Integer.toString(cost);
return res;
}
}
this problem can be solved using dynamic programming.
costs = parseStringTo2dArray(input1, input2); // here you should parse your string input to 2d array of integers.
- Anonymous April 26, 2016