2 MS Interview problems

1. Given an integer array (positive #, negative #, or 0), find a subarray with the maximum sum.

(A subarray is a consecutive subsequence of the original array.  The sum of an array is just the sum of its individual elements.)

2. Suppose you have a M-by-N matrix (i.e. M rows and N columns), whose entries are all integers.  We want to set all the elements on the i-th row and j-th column to 0 if matrix entry (i, j) is 0.  Write a routine that does this and we want to find a solution with the minimum amount of memory consumption and fastest speed (i.e. the less memory you use to store some intermediate result, the better).  Highlight the next sentence for a quick hint: you can actually find a solution that only scans the matrix once and use O(1) memory (i.e. constant amount of memory).

For instance, if the matrix is:

1   0   2

3   1   1

then, the result should be:

0   0   0

3   0   1

(since the (1, 2) entry is 0, we set all elements on the 1st row and 2nd column to 0)

 

1. 最大子数列 （Kadane算法）

 

        static void FindMaxSumSubarray(int[] array, out int start, out int end)
{
int tmp, max, cur;
start = end = 0;
tmp = 0;
max = int.MinValue;
cur = 0;
for (int i=0; i<array.Length; i++)
{
tmp += array[i];
if (tmp > max)
{
start = cur; end = i; max = tmp;
}
if (tmp < 0)
{
tmp = 0; cur = i + 1;
}
}
}

 

顺便说一句：这个问题在2维数列的情况下是一个蛮有名的machine learning的问题。google一下maximum subarray machine learning可以查到不少文献。

 

2. 矩阵设零 (特殊的1x1矩阵我就偷懒掉了，: ) )

 

 

       static void ZeroThemOut(ref int[,] matrix)
{
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
int oneExtraFlagForCol0 = 1;
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (0 == matrix[r, c])
{
matrix[r, 0] = 0;
if (0 == c)
oneExtraFlagForCol0 = 0;
else
matrix[0, c] = 0;
}
}
}
for (int r = 1; r < rows; r++)
{
if (0 == matrix[r, 0])
{
for (int c = 0; c < cols; c++)
matrix[r, c] = 0;
}
}
for (int c = 1; c < cols; c++)
{
if (0 == matrix[0, c])
{
for (int r = 0; r < rows; r++)
matrix[r, c] = 0;
}
}
if (0 == matrix[0, 0])
{
for (int c = 0; c < cols; c++)
matrix[0, c] = 0;
}
if (0 == oneExtraFlagForCol0)
{
for (int r = 0; r < rows; r++)
matrix[r, 0] = 0;
}
}