Sap Labs Interview Question
Country: United States
import ast
# goal is to get maximum collected money among paths of
# minimal length connecting [0,0] to [n,n] (moving
# diagonally is forbidden).
# The paths as above are obtained starting from [0,0]
# and at every step moving only either on the right (i.e. from A[i,j] to A[i,j+1])
# or downwards (i.e. from A[i,j] to A[i+1,j])
def transform(n, st) :
if len(st) == 0 or n == 0:
return []
else :
try :
matrix = ast.literal_eval(st)
except ValueError :
print('Oops, something got wrong!')
if len(matrix) == len(matrix[0]) and len(matrix) == n :
return matrix
else :
return []
def get_path(mat) :
increments = [[0,1], [1,0]]
current_nodes = [[0,0]]
current_values = [mat[0][0]]
money_on_paths = []
while len(current_nodes) > 0 :
updated_nodes = []
updated_values = []
for l in range(0,len(current_nodes)) :
if ((len(mat) -1)-current_nodes[l][0]) + (len(mat[0])-1 -current_nodes[l][1]) > 0 :
for delta in increments :
up = [current_nodes[l][i] + delta[i] for i in range(0, len(delta))]
if up[0] < len(mat) and up[1] < len(mat[0]) :
updated_nodes.append(up)
updated_values.append(mat[up[0]][up[1]] + current_values[l])
else :
money_on_paths.append(current_values[l])
current_nodes = updated_nodes
current_values = updated_values
print(money_on_paths)
return max(money_on_paths)
def f(size, the_string) :
m = transform(size, the_string)
if len(m) > 0 :
return get_path(m)
#test
a = '[[1,2,3], [3,4,5], [1,1,3]]'
print(f(3,a))
This is recursion method
int shortest(int graph[V][V], int xs, int ys, int xe, int ye)
{
if(xs < 0 || ys < 0 || xs >= V || ys >= V)
{
return 0;
}
if(xs == xe && ys == ye)
{
return graph[xs][ys];
}
int x = 0, y = 0;
int s4 = shortest(graph, xs + 1, ys, xe, ye);
int s6 = shortest(graph, xs, ys + 1, xe, ye);
return graph[xs][ys] + std::max(s4, s6);
}
This is recursive method:
int shortest(int graph[V][V], int xs, int ys, int xe, int ye)
{
if(xs < 0 || ys < 0 || xs >= V || ys >= V)
{
return 0;
}
if(xs == xe && ys == ye)
{
return graph[xs][ys];
}
int x = 0, y = 0;
int s4 = shortest(graph, xs + 1, ys, xe, ye);
int s6 = shortest(graph, xs, ys + 1, xe, ye);
return graph[xs][ys] + std::max(s4, s6);
}
public class MickyMoney {
public void findMaxMoney(int i, String money) {
int[][] values = new int[i][i];
money = money.substring(1, money.length() -1);
String[] valuesStr = money.split("\\),\\(");
int rowCount = 0;
for(String aVal : valuesStr) {
String[] ints = aVal.split(",");
int colCount = 0;
for(String anInt : ints) {
values[rowCount][colCount] = Integer.valueOf(anInt);
colCount ++;
}
rowCount ++;
}
// logic
findMax(0, 0, i, i, values, 0);
System.out.print(maxSum);
}
private void findMax(int nextRow, int nextCol, int maxRow, int maxCol, int[][] values, int sum) {
if(nextRow >= maxRow || nextCol >= maxCol) {
return;
}
sum += values[nextRow][nextCol];
if(nextRow == maxRow - 1 && nextCol == maxCol - 1) {
if(sum > maxSum) maxSum = sum;
}
findMax(nextRow, nextCol + 1, maxRow, maxCol, values, sum);
findMax(nextRow + 1, nextCol, maxRow, maxCol, values, sum);
}
int maxSum = 0;
}
public class MickyMoney {
public void findMaxMoney(int i, String money) {
int[][] values = new int[i][i];
money = money.substring(1, money.length() -1);
String[] valuesStr = money.split("\\),\\(");
int rowCount = 0;
for(String aVal : valuesStr) {
String[] ints = aVal.split(",");
int colCount = 0;
for(String anInt : ints) {
values[rowCount][colCount] = Integer.valueOf(anInt);
colCount ++;
}
rowCount ++;
}
// logic
findMax(0, 0, i, i, values, 0);
System.out.print(maxSum);
}
private void findMax(int nextRow, int nextCol, int maxRow, int maxCol, int[][] values, int sum) {
if(nextRow >= maxRow || nextCol >= maxCol) {
return;
}
sum += values[nextRow][nextCol];
if(nextRow == maxRow - 1 && nextCol == maxCol - 1) {
if(sum > maxSum) maxSum = sum;
}
findMax(nextRow, nextCol + 1, maxRow, maxCol, values, sum);
findMax(nextRow + 1, nextCol, maxRow, maxCol, values, sum);
}
int maxSum = 0;
public static void main(String[] args) {
new MickyMoney().findMaxMoney(4, "(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)");
}
}
/*
Dynamic programming problem since j[i] >= j[i-1], i[i] >= i[i-1]
can only move from left to right and top down
dp[i,j] = max(
dp[i-1,j], // if i>0
dp[i,j-1], // if j>0
0 // if i=0 and j =0
) + c[i,j]
Timecomplexity: O(n^2)
Spacecomplexity: O(n^2), can be optimized to O(n) (need vector of size n+1)
*/
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> ParseHouses(int n, const string& houses);
int MaxCollect(int n, const string& houses)
{
auto c = ParseHouses(n, houses);
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int c1 = i > 0 ? dp[i - 1][j] : 0;
int c2 = j > 0 ? dp[i][j - 1] : 0;
dp[i][j] = max(c1, c2) + c[i][j];
}
}
return dp[n - 1][n - 1];
}
void Match(istream& iss, char c)
{
char r = '\0';
while (!iss.eof() && (r == ' ' || r == '\n' || r == '\r' || r == '\0')) iss >> r;
if (r != c) throw "syntax error";
}
vector<vector<int>> ParseHouses(int n, const string& houses)
{
vector<vector<int>> res(n, vector<int>(n, 0));
stringbuf sb(houses);
istream iss(&sb);
for (int i = 0; i < n; i++)
{
Match(iss, '(');
for (int j = 0; j < n; j++)
{
int c;
iss >> res[i][j];
if (j != n - 1) Match(iss, ',');
}
Match(iss, ')');
if (i != n - 1) Match(iss, ',');
}
return res;
}
int main()
{
cout << MaxCollect(4, "(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)");
}
include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> ParseHouses(int n, const string& houses);
int MaxCollect(int n, const string& houses)
{
auto c = ParseHouses(n, houses);
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int c1 = i > 0 ? dp[i - 1][j] : 0;
int c2 = j > 0 ? dp[i][j - 1] : 0;
dp[i][j] = max(c1, c2) + c[i][j];
}
}
return dp[n - 1][n - 1];
}
void Match(istream& iss, char c)
{
char r = '\0';
while (!iss.eof() && (r == ' ' || r == '\n' || r == '\r' || r == '\0')) iss >> r;
if (r != c) throw "syntax error";
}
vector<vector<int>> ParseHouses(int n, const string& houses)
{
vector<vector<int>> res(n, vector<int>(n, 0));
stringbuf sb(houses);
istream iss(&sb);
for (int i = 0; i < n; i++)
{
Match(iss, '(');
for (int j = 0; j < n; j++)
{
int c;
iss >> res[i][j];
if (j != n - 1) Match(iss, ',');
}
Match(iss, ')');
if (i != n - 1) Match(iss, ',');
}
return res;
}
int main()
{
cout << MaxCollect(4, "(1,7,5,2),(5,12,3,6),(100,9,23,16),(16,4,5,9)");
}
- Luke Rhinehart August 22, 2016import ast # goal is to get maximum collected money among paths of # minimal length connecting [0,0] to [n,n] (moving # diagonally is forbidden). # The paths as above are obtained starting from [0,0] # and at every step moving only either on the right (i.e. from A[i,j] to A[i,j+1]) # or downwards (i.e. from A[i,j] to A[i+1,j]) def transform(n, st) : matr = ast.literal_eval(a) if len(matr) != len(matr[0]) or len(matr) != n : print('error') return [] else : return matr def get_path(mat) : increments = [[0,1], [1,0]] current_nodes = [[0,0]] current_values = [mat[0][0]] money_on_paths = [] while len(current_nodes) > 0 : updated_nodes = [] updated_values = [] for l in range(0,len(current_nodes)) : if ((len(mat) -1)-current_nodes[l][0]) + (len(mat[0])-1 -current_nodes[l][1]) > 0 : for delta in increments : up = [current_nodes[l][i] + delta[i] for i in range(0, len(delta))] if up[0] < len(mat) and up[1] < len(mat[0]) : updated_nodes.append(up) updated_values.append(mat[up[0]][up[1]] + current_values[l]) else : money_on_paths.append(current_values[l]) current_nodes = updated_nodes current_values = updated_values print(money_on_paths) return max(money_on_paths) #test a = '[[1,2,3], [3,4,5], [1,1,3]]' mat = ast.literal_eval(a) for j in range(0, len(mat)) : print(mat[j]) print(get_path(transform(3,a)))