靖轩豪苑二手房: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

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 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;elsematrix[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;}}