Agilent Technologies Microsoft Interview Question for Software Engineer / Developers

• 0

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

``````package problems;

import Definition.Matrix;

public class MaximumSumMatrix {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int[][] aMatrix = { { 2, 40, -8 }, { -12, 35, -8 }, { 12, -9, -8 } };
// Matrix.initialize(aMatrix);
Matrix.printMatrix(aMatrix);
findMaximumSubMatrix(aMatrix);
}

private static void findMaximumSubMatrix(int[][] aMatrix) {
// TODO Auto-generated method stub

int[] oneD;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < aMatrix.length; i++) {
oneD = new int[aMatrix[0].length];
int current = 0;
int maxCurrent = Integer.MIN_VALUE;
for (int k = i; k < aMatrix.length; k++) {
current = 0;
for (int j = 0; j < aMatrix[0].length; j++) {
oneD[j] = oneD[j] + aMatrix[k][j];
current = current + oneD[j];
if (current > maxCurrent) {
maxCurrent = current;
}
if (current < 0) {
current = 0;
}
}
if (maxSum < maxCurrent)
maxSum = maxCurrent;
}
}
System.out.print(maxSum);
}
}``````

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

see there:

There is a O(N^3) algorithm.

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

``````//Idea taken from stackoverflow
int findMaximumSubMatrix(int** matrix, int *top, int *left, int *bottom, int *right, unsigned int dim){
int i, j, k, maxSum, localMax, ret =0;
int **ps=NULL;
int *pos=NULL, *sum = NULL;
*top = -1;
*left = -1;
*bottom = -1;
*right = -1;

if (matrix == NULL || dim <= 0)
return -1;
//computing the vertical prefix sum for columns
ps = malloc (sizeof(int *) * dim);
if (ps == NULL)
return -1;
for (i = 0; i<dim;i++)
{
ps[i]=malloc (sizeof(int)*dim);
if (ps[i] == NULL)  {
ret = -1;
goto fail;
}
}

for (i = 0; i < dim; i++) {
for (j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}

maxSum = matrix[0][0];
*top = 0; *left = 0; *bottom = 0; *right = 0;

sum = malloc(sizeof(int)*dim);
if (sum == NULL){
ret =-1;
goto fail;
}
pos = malloc(sizeof(int)*dim);
if (pos == NULL){
ret =-1;
goto fail;
}

for (int i = 0; i < dim; i++) {
for (int k = i; k < dim; k++) {
// Kandane over all columns with the i..k rows
memset(sum, 0, dim*sizeof(int));
memset(pos,0, dim*sizeof(int));
localMax = 0;
//we keep track of the position of the max value over each Kandane's execution
// notice that we do not keep track of the max value, but only its position
sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
for (int j = 1; j < dim; j++) {
if (sum[j-1] > 0){
sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = pos[j-1];
}else{
sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = j;
}
if (sum[j] > sum[localMax]){
localMax = j;
}
}//Kandane ends here

if (sum[localMax] > maxSum){
/* sum[localMax] is the new max value
the corresponding submatrix goes from rows i..k.
and from columns pos[localMax]..localMax
*/
maxSum = sum[localMax];
*top = i;
*left = pos[localMax];
*bottom = k;
*right = localMax;
}
}
}

for(i = *top; i <= *bottom; i++){
for(int j = *left; j <= *right ; j++){
printf("%d ", matrix[i][j]);
}
printf("\n");
}

fail:
for (j=0;j<dim;j++) {
if (ps[i])
free(ps[i]);
}
if (ps)
free(ps);
if(pos)
free(pos);
if(sum)
free(sum);
return ret;
}

private void reset(int[] a) {
for (int index = 0; index < a.length; index++) {
a[index] = 0;
}
}``````

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

``````//Modified earlier post ...
//Idea taken from stackoverflow
int findMaximumSubMatrix(int** matrix, int *top, int *left, int *bottom, int *right, unsigned int dim){
int i, j, k, maxSum, localMax, ret =0;
int **ps=NULL;
int *pos=NULL, *sum = NULL;
*top = -1;
*left = -1;
*bottom = -1;
*right = -1;

if (matrix == NULL || dim <= 0)
return -1;
//computing the vertical prefix sum for columns
ps = malloc (sizeof(int *) * dim);
if (ps == NULL)
return -1;
for (i = 0; i<dim;i++)
{
ps[i]=malloc (sizeof(int)*dim);
if (ps[i] == NULL)  {
ret = -1;
goto fail;
}
}

for (i = 0; i < dim; i++) {
for (j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}

maxSum = matrix[0][0];
*top = 0; *left = 0; *bottom = 0; *right = 0;

sum = malloc(sizeof(int)*dim);
if (sum == NULL){
ret =-1;
goto fail;
}
pos = malloc(sizeof(int)*dim);
if (pos == NULL){
ret =-1;
goto fail;
}

for (int i = 0; i < dim; i++) {
for (int k = i; k < dim; k++) {
// Kandane over all columns with the i..k rows
memset(sum, 0, dim*sizeof(int));
memset(pos,0, dim*sizeof(int));
localMax = 0;
//we keep track of the position of the max value over each Kandane's execution
// notice that we do not keep track of the max value, but only its position
sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
for (int j = 1; j < dim; j++) {
if (sum[j-1] > 0){
sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = pos[j-1];
}else{
sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = j;
}
if (sum[j] > sum[localMax]){
localMax = j;
}
}//Kandane ends here

if (sum[localMax] > maxSum){
/* sum[localMax] is the new max value
the corresponding submatrix goes from rows i..k.
and from columns pos[localMax]..localMax
*/
maxSum = sum[localMax];
*top = i;
*left = pos[localMax];
*bottom = k;
*right = localMax;
}
}
}

for(i = *top; i <= *bottom; i++){
for(int j = *left; j <= *right ; j++){
printf("%d ", matrix[i][j]);
}
printf("\n");
}

fail:
for (j=0;j<dim;j++) {
if (ps[i])
free(ps[i]);
}
if (ps)
free(ps);
if(pos)
free(pos);
if(sum)
free(sum);
return ret;
}``````

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

Its a dymanic programming problem; Can anyone write an recurrence equation for this problem.

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

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

i was not able to access this site

Forbidden

You don't have permission to access /~rohit/mindsports/viewtopic.php on this server.

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

I cant think of a way to use subproblem to form an equation.

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

Can anyone post any soluton to this ?

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

Let me know what you guys think of this solution:

I'm assuming that a submatrix has to be rectangular, e.g. you create the submatrix by removing some combination of rows and columns from the perimeter of the matrix. So your algorithm would be something like this:
Add up the totals of all the rows and columns on the perimeter of the matrix. If any of them add up to a number less than zero, remove those, and this will be your submatrix with a maximum sum. Keep doing this until none of the rows or columns have a negative sum. (Note: I'm assuming that the matrix counts as a submatrix of itself. If not, just remove the row or column with the smallest sum in the first step.)

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

i started with a o(n^6) solution and was easily able to come to a o(n^4) one, but it took lot of time to narrow it down to o(n^3) . I have heard there is a o(n^2.69) solution as well.

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

Can anyone post the solution for this please.

Thanks,
Raj

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

its's very easy

solve recursively

base case : n=1

iterative case :
to find for m*n, find for m-1 * n-1 ,call it a

b = a + sum of upper row - mat[0][0]
c = a + sum of first col - mat[0][0]
d = a + sum of upper row + first col - mat[0][0]

return max(a,b,c,d);

sexy....
then

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

i know the solution to find out the maximum sum of sub array its O(n^3), its a DP problem but here we have to find out the sub array as well.

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

Given an O(N) method of finding the offset & length of the subsequence of elements with the highest sum in a one-dimensional array of N positive & negative integers:

FindSubsequenceWithMaxSum (int *Array, uint N)
{
unsigned long sum = 0, maxSum = LONG_MIN;
unisgned int offset, length,
maxOffset = 0, maxLength = 1;

for (uint i = 0; i < N; i++)
{
if (sum <= 0 || (sum + Array[i]) < 0)
{
sum = (long) Array[i];
offset = i;
length = 1;
}
else
{
sum += (long) Array[i];
length++;
}

if (sum > maxSum)
{
maxSum = sum;
maxOffset = offset;
maxLength = length;
}
}

/* Done: maxSum, maxOffset, maxLength */
}

...an O(N^2.69) solution is as follows:

FindSubmatrixWithMaxSum (int *Matrix, uint N)
{
unsigned long maxSum = LONG_MIN;
unsigned int maxRow = 0, maxColumn = 0,
maxWidth = 1, maxHeight = 1;

/* Find max subseq (height=?, width=1) across all columns */
for (uint col = 0; col < N; col++) { ... }

/* Find max subseq (height=1, width=?) across */
/* all uncompressed rows */
for (uint row = 0; row < N; row++) { ... }

/* Do row compression & compute max row subseqs */
for (uint augendRow = 0; augendRow < (N-1); augendRow++)
{
{
uint maxSumAfterCompression = INT_MIN,
maxColumnAfterCompression = 0,
maxLengthAfterCompression = 1;

for (uint col = 0; col < N; col++)
{
/* Compress this column, e.g. : */
/* Matrix[augendRow][col] += */
/* ...then track max subseq of row so far */
}

if (maxSumAfterCompression > maxSum)
{
maxSum = maxSumAfterCompression;
maxRow = augendRow;
maxColumn = maxColumnAfterCompression;
maxWidth = maxLengthAfterCompression;
maxHeight = 1 + addendRow - augendRow;
}
}
}

/* Done: maxSum, maxRow, maxColumn, maxWidth, maxHeight */
}

For example, given an N=4 matrix:

row 0 : a0 a1 a2 a3
b0 b1 b2 b3
c0 c1 c2 c3
d0 d1 d2 d3

...the first for(augendRow) loop iteration will compute max subsequences for the following row combinations:

(a0+b0 a1+b1 a2+b2)
(a0+b0+c0 a1+b1+c1 a2+b2+c2)
(a0+b0+c0+d0 a1+b1+c1+d1 a2+b2+c2+d2)

In all, max subsequences are generated (at O(N)) for a total of (N^2)/2 combinations, thus O((N^3)/2) or O(N^2.69).

Practical platform-specific optimizations may include:

- Transposing matrix (e.g. in h=?/w=1 loop) to improve locality of reference in innermost nested loop
- Performing multiple row compressions (augend-only or following rows) in the innermost loop

Note that the use of "long" types for "sum" variables may not suffice for underflow/overflow mitigation for large N.

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

Can you please elaborate this algorithm to full - fledge C code or algorithm

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

how can O( (N^3) /2 ) be O( N^2.69 ) ??

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

Typo in FindSubsequenceWithMaxSum() above:

if (sum <= 0 || (sum + Array[i]) < 0)

if (sum <= 0 || (sum + Array[i]) <= 0)

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

can you post the exact question

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

It is like finding maximum sum in sub array... but instead of single dimension it is a matrix now...

In a m x n matrix, find a submatrix p x q such that sum of all the elements in it is maximum as compared to any other submatrix of any size. Ofcourse the matriz contains negative elements otherwise the question doesn't make sense.

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

Sample example:
2 10 8 3
-8 14 -1 4
-6 -1 8 -2
1 8 7 3
8 2 -10 -8

10 8 3
14 -1 4
-1 8 -2
8 7 3

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

see there:

There is a O(N^3) algorithm.

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

O(n^3) where n is the number of cells in the matrix.
==============
for each cell i
..use i as the top left corner of all candidate rectangles/
..calculate the sum of all possible candidate rectangles (n^2)
..only record the max sum for i.
In the end, we have the max sum for each cell, then find the max sum for all cells.

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

Good solution.

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

that's not O(n^3).

n = number of rows or columns, there's n^2 total cells in the matrix. your outer loop (for each cell i) takes O(n^2), inner loop takes O(n^2), which makes this approach O(n^4)

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

http://alien.dowling.edu/~rohit/mindsports/viewtopic.php?t=139

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

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

Note:
Negative and Positive numbers are also present.

Solution 1:
List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.

Solution 2:
We construct an output array from the input array in the following manner:
inputArr[m][n] be the input array.
And let us make another array outputArr[m][n] with all fields set to zero by default.
Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].

So determine outputArr[i][j] =
inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]

Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]

Now we can run an algorithm similar to the first solution only difference is that finding the sum is easier now.

For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.

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

You can find the solution here at dailyjobquestions.com/2011/10/10/max-submatrix/

Here's the dynamic programming implementation in C++

``````typedef struct info{int i; int j; int max;} info;

int row(int** a, int i,  int j1, int j2) {
int s = 0;
for (int j = j1; j <= j2; j++) s += a[i][j];
return s;
}

int column(int** a, int j, int i1, int i2) {
int s = 0;
for (int i = i1; i <= i2; i++) s += a[i][j];
return s;
}

void max_matrix(int** a, int n) {
info** p = new info*[n];
for (int i = 0; i < n; i++) p[i] = new info[n];

info max_info = {0, 0, a[0][0]};
int max_i = 0;
int max_j = 0;

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = (info){i, j, a[i][j]};
if (i > 0) {
info up = p[i-1][j];
up = (info){up.i, up.j, up.max + row(a, i, up.j, j)};
if (up.max > p[i][j].max) p[i][j] = up;
}
if (j > 0) {
info left = p[i][j - 1];
left = (info){left.i, left.j, left.max + column(a, j, left.i, i)};
if (left.max > p[i][j].max) p[i][j] = left;
}
if (max_info.max < p[i][j].max) {
max_info = p[i][j];
max_i = i;
max_j = j;
}
}
}
printf("The submatrix starts at (%i, %i) and ends at (%i, %i) and the sum is %i", max_info.i, max_info.j, max_i, max_j, max_info.max);
for (int i = 0; i < n; i++) delete[] p[i];
delete[] p;
}``````

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

The easiest solution is in deep first search:
each time splitting matrix by vertical or horizontal line on two:
if one submatix sum is negative and another submatrix sum
is positive, then those with positive sum is better than the original
matrix, use it for next step.

The idea is described in the code below (for the case of vector):

``````from random import randint;
maxSum = [0];
bestMatrix = [0];
def DFS(a):
print a;
if sum(a) > maxSum[0]:
maxSum[0] = sum(a);
bestMatrix[0] = a;
for splitter in range(1, len(a)):
leftSum = sum(a[:splitter]);
rightSum = sum(a[splitter:]);
if leftSum > 0 and rightSum < 0:
DFS(a[:splitter]);
elif leftSum < 0 and rightSum > 0:
DFS(a[splitter:])
a = [randint(0, 20) - 10 for item in range(10)];
print a;
DFS(a);
print maxSum[0];
print bestMatrix[0];``````

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

this is for one dimension right, i think kadenes is best for one dimension !

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

I came with this solution in java, the first comments says it has a solution but is incorrect

``````import java.util.*;

public class HelloWorld {

public static void main(String []args){
int[][] aMatrix = {
{ 2, 40, -8 }, { -12, 35, -8 }, { 12, -9, -8 }
};

Object[] subMatrix = longestSubmatrixSum(aMatrix);

System.out.println(Arrays.toString(subMatrix));
}

public static Object[] longestSubmatrixSum(int [][] matrix) {
int cols = matrix[0].length,
rows = matrix.length,
totalMatrixElements = cols * rows,
arrayIndex = 0,
maxSum = -9999999;

int [] plainArray = new int[totalMatrixElements];

List trackNumbers = new ArrayList(),
auxTrackNumbers = new ArrayList();

for (int i = 0; i < rows; i++) {
for (int k = 0; k < cols; k++) {
plainArray[arrayIndex] = matrix[i][k];
arrayIndex++;
}
}

for (int i = 0; i < totalMatrixElements; i++) {
int currentSum = 0;

for (int k = i; k < totalMatrixElements; k++) {

currentSum = plainArray[k] + currentSum;

if (maxSum < currentSum) {
maxSum = currentSum;

trackNumbers = ((List) ((ArrayList) auxTrackNumbers).clone());
}
}
// We clear values so we now is a new line
auxTrackNumbers.clear();
}

System.out.println("max sum is:" + maxSum);

return trackNumbers.toArray();
}
}``````

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

Dynamic table fill-up:
/* As solution[i-1][j-1] will be counted twice in solution matrix fill-up we need to subtract it */

``solution[i][j] = matrix[i][j] + (solution[i-1][j] + solution[i][j-1] - solution[i-1][j-1])``

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.