面试被出了这么一题，各位大神来解解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试被出了这么一题，各位大神来解解

面试被出了这么一题，各位大神来解解# JobHunting - 待字闺中

u*82018-10-19 07:10

1 楼

给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
这一题，1小时，搞得定么？

f*n2018-10-19 07:10

2 楼

m * n的矩阵有m * n个未知数，m + n个方程组
当m * n > m + n的时候有无穷解

【在 u***8 的大作中提到】

: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？

Y*o2018-10-19 07:10

3 楼

好像分成小矩阵，加上非负数prune，再组合，我比较菜，大神来讲讲吧。

q*02018-10-19 07:10

4 楼

感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
溯。

u*82018-10-19 07:10

5 楼

谁会？是什么graph cut么？求大牛来解。

u*82018-10-19 07:10

6 楼

我就是想大神跟我说说，fang面试onsite轮，遇到这一题，是我水，还是这题难，
死也死个明白。

t*s2018-10-19 07:10

7 楼

Linear programming

【在 u***8 的大作中提到】

: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？

u*82018-10-19 07:10

8 楼

请丢个code，上来，一下，结果出来。我可以给伪币。

【在 t***s 的大作中提到】

: Linear programming

u*82018-10-19 07:10

9 楼

更新：我非常想知道，如何做这一题。今天HR来了电话，口气很冷淡的拒绝了。我问什
么都不说。就说12个月，block期。然后我说，这最后一题，实在不是1小时做得出来。
他也就说，有个survey，其余没办法。
求有大神丢个code上来，跑下来，答案出来。心服口服。给伪币。
给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
这一题，1小时，搞得定么？

Y*o2018-10-19 07:10

10 楼

好像分成小矩阵，加上非负数prune，再组合，我比较菜，大神来讲讲吧。

q*02018-10-19 07:10

11 楼

感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
溯。

u*82018-10-19 07:10

12 楼

谁会？是什么graph cut么？求大牛来解。

u*82018-10-19 07:10

13 楼

我就是想大神跟我说说，fang面试onsite轮，遇到这一题，是我水，还是这题难，
死也死个明白。

t*s2018-10-19 07:10

14 楼

Linear programming

【在 u***8 的大作中提到】

: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？

u*82018-10-19 07:10

15 楼

请丢个code，上来，一下，结果出来。我可以给伪币。

【在 t***s 的大作中提到】

: Linear programming

c*y2018-10-19 07:10

16 楼

+1，对n^2范围的点逐一试探，递归下去，如果发现rowsum[i]或colsum[j]比当前累积
的数字小了就失败返回。或者行列剩下的数（假设有范围0-255）不够凑齐sum，也失败
返回。感觉这是二维图像重建，要是有特别快的方法意义感觉蛮大的，这个只能说是暴
力搜索。为了找所有的解感觉只能这样了吧，毕竟解空间那么大。别的算法一小时也不
现实。
如果没有范围的话，那每个点只能从1到min(rowsum[i], colsum[j]循环了。
如果不限制整数的话，那我就没辙了，没准是无穷多解，这个可能得先问清楚。

【在 q*******0 的大作中提到】

: 感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
: 溯。

p*22018-10-19 07:10

17 楼

大概写了半个小时，估计onsite直接就跪了。
public class Solution {
int m;
int n;
int[] rows;
int[] cols;
List> all = new ArrayList<>();
List serialize(int[][] matrix) {
List al = new ArrayList<>();
for(int[] arr : matrix) {
StringBuilder sb = new StringBuilder();
for(int i : arr) {
if(sb.length() > 0) {
sb.append(",");
}
sb.append(i);
}
al.add(sb.toString());
}
return al;
}
boolean valicate(int[][] matrix) {
int[] r = new int[m];
int[] c = new int[n];
for(int i=0; ifor(int j=0; jr[i] += matrix[i][j];
c[j] += matrix[i][j];
if(i == m-1 && cols[j] != c[j]) {
return false;
}
}
if(rows[i] != r[i]) {
return false;
}
}
return true;
}
void dfs(int[][] matrix, int index) {
if(index == m*n) {
if(valicate(matrix)) {
all.add(serialize(matrix));
}
return;
}
int x = index/n;
int y = index%n;
int row = 0;
for(int j=0; jrow += matrix[x][j];
}
int col = 0;
for(int i=0; icol += matrix[i][y];
}
for(int num = 1; num <= Math.min(rows[x]-row, cols[y]-col); num++) {
matrix[x][y] = num;
dfs(matrix, index+1);
}
matrix[x][y] = 0;
}
List> composeMatrix(int m, int n, int[] rows, int[] cols) {
this.m = m;
this.n = n;
this.rows = rows;
this.cols = cols;
all.clear();
int[][] matrix = new int[m][n];
dfs(matrix, 0);
return all;
}
}

t*d2018-10-19 07:10

18 楼

2爷都说跪了，我也没什么遗憾了。还是被国人出的这一题。我也是没有办法。当场傻
眼。

【在 p*****2 的大作中提到】

: 大概写了半个小时，估计onsite直接就跪了。
: public class Solution {
: int m;
: int n;
: int[] rows;
: int[] cols;
: List> all = new ArrayList<>();
: List serialize(int[][] matrix) {
: List al = new ArrayList<>();
: for(int[] arr : matrix) {

f*e2018-10-19 07:10

19 楼

用递归，很好写！f(m,n)｛一维递归里面call f(m-1, n)｝
明天我写个mutual recursive的。

p*22018-10-19 07:10

20 楼

我觉得面试过程很重要。如果是G家的话，interviewer很看重思路。按照我的理解，这
题主要考察的是DFS。现在DFS的趋势是不那么直接了，加了很多条件。LC上的有些
medium dfs也不是看起来简洁明了，比如756。
想想看，如果你工作起来怎么handle ambiguity。problem solving是面试官重点考察
的一个主要方面。

【在 t******d 的大作中提到】

: 2爷都说跪了，我也没什么遗憾了。还是被国人出的这一题。我也是没有办法。当场傻
: 眼。

e*22018-10-19 07:10

21 楼

class solution {
public:
void aux(vector& rows, vector& cols, int m, int n, vector<
vector>& temp, vector>>& res)
{
if (m == rows.size() - 1 && n == cols.size() - 1) {
if (rows[m] >= 0 && cols[n] >= 0 && rows[m] == cols[n]) {
temp[m][n] = rows[m];
res.push_back(temp);
}
}
else{
int start = n == cols.size() - 1 ? rows[m] : 0;
for (int i = start; i <= min(rows[m], cols[n]); i++) {
temp[m][n] = i;
rows[m] -= i;
cols[n] -= i;
if (n + 1 < cols.size())
aux(rows, cols, m, n + 1, temp, res);
else
aux(rows, cols, m + 1, 0, temp, res);
rows[m] += i;
cols[n] += i;
}
}
}
void f(vector& rows, vector& cols, vector>>
& res)
{
vector> temp(rows.size(), vector(cols.size()));
aux(rows, cols, 0, 0, temp, res);
}
};

e*22018-10-19 07:10

22 楼

//recurse entry by entry; if any constraint is violated, return
class solution {
public:
void aux(vector& rows, vector& cols, int m, int n, vector<
vector>& temp, vector>>& res)
{
if (m == rows.size() - 1) {
if (accumulate(cols.begin(), cols.end(), 0) == rows.back()) {
temp.back() = cols;
res.push_back(temp);
}
}
else{
int start = n == cols.size() - 1 ? rows[m] : 0;
for (int i = start; i <= min(rows[m], cols[n]); i++) {
temp[m][n] = i; rows[m] -= i; cols[n] -= i;
n + 1 < cols.size()?aux(rows, cols, m, n + 1, temp, res):aux
(rows, cols, m + 1, 0, temp, res); // recurse to next entry
rows[m] += i; cols[n] += i;
}
}
}
void f(vector& rows, vector& cols, vector>>
& res) {
if(accumulate(cols.begin(), cols.end(), 0) != accumulate(rows.begin(),
rows.end(), 0)) return;
vector> temp(rows.size(), vector(cols.size()));
aux(rows, cols, 0, 0, temp, res);
}
};

【在 e********2 的大作中提到】

: class solution {
: public:
: void aux(vector& rows, vector& cols, int m, int n, vector<
: vector>& temp, vector>>& res)
: {
: if (m == rows.size() - 1 && n == cols.size() - 1) {
: if (rows[m] >= 0 && cols[n] >= 0 && rows[m] == cols[n]) {
: temp[m][n] = rows[m];
: res.push_back(temp);
: }

b*h2018-10-19 07:10

23 楼

这题写个最基本的回溯用不了20分钟吧。再加个记忆搜索，应该就够应付面试官了。

T*e2018-10-19 07:10

24 楼

俺还是佩服2爷和你。敢直接贴码，肚里有货。我承认我只能马后炮
地说这是combination sum的变形，2D。但第一眼我也没认出来。：)
楼主加油。

【在 e********2 的大作中提到】

: //recurse entry by entry; if any constraint is violated, return
: class solution {
: public:
: void aux(vector& rows, vector& cols, int m, int n, vector<
: vector>& temp, vector>>& res)
: {
: if (m == rows.size() - 1) {
: if (accumulate(cols.begin(), cols.end(), 0) == rows.back()) {
: temp.back() = cols;
: res.push_back(temp);

u*82018-10-19 07:10

25 楼

我到现在也没看出来是comb sum 2d。

【在 T*******e 的大作中提到】

: 俺还是佩服2爷和你。敢直接贴码，肚里有货。我承认我只能马后炮
: 地说这是combination sum的变形，2D。但第一眼我也没认出来。：)
: 楼主加油。

p*22018-10-19 07:10

26 楼

大牛慢慢来吧。

【在 u***8 的大作中提到】

: 我到现在也没看出来是comb sum 2d。

u*82018-10-19 07:10

27 楼

某培训机构说，面试出这max flow，要么就是不招人，要么就是直接想拒人。

【在 p*****2 的大作中提到】

:
: 大牛慢慢来吧。

C*y2018-10-19 07:10

28 楼

我操，任何一个bi公司平时的活也碰不到这种问题吧。