## Sap Labs Interview Question

Country: United States

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

``````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) :
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)))``````

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

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

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

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);
}

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

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

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

``````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;

}``````

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

``````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)");
}

}``````

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

How to output the path taken by the traversal?

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

Which language is this java or not

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

``````/*
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)");
}``````

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

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)");
}

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.