FreeOZ论坛

标题: 发个GOOGLE的面试题 [打印本页]

作者: decisiontree 时间: 13-3-2009 16:56
标题: 发个GOOGLE的面试题
Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.

我还是经常CODING的。但这个题目我想了一晚木有IDEA啊，竟然失眠了（那个BRUTEFORCE的穷尽搜索不算啊，it's》N！）。兄弟们同想！

作者: coredump 时间: 13-3-2009 17:37
z这里有答案（http://www.ocf.berkeley.edu/~wwu ... gi?board=riddles_cs;action=display;num=1160067677）。仅用于治疗失眠，想做题的先不要点

作者: coredump 时间: 13-3-2009 17:50

decisiontree 威望 +20 赖皮啊！

这不是为你的健康着想吗

作者: 清风不写字 时间: 13-3-2009 21:09
别跟自己过不去嘛，呵呵！

作者: kingsking 时间: 14-3-2009 10:33
N乘N的矩阵,再找一个最大的子矩阵?

作者: beysup 时间: 14-3-2009 13:17
用data mining的方法就行，找frequent patterns

作者: northwind79 时间: 14-3-2009 16:37
Typical dynamic programming problem

作者: decisiontree 时间: 14-3-2009 18:16

原帖由 kingsking 于 14-3-2009 11:33 发表

 登录/注册后可看大图

N乘N的矩阵,再找一个最大的子矩阵?

是的。

作者: decisiontree 时间: 14-3-2009 18:20

原帖由 beysup 于 14-3-2009 14:17 发表

 登录/注册后可看大图

用data mining的方法就行，找frequent patterns

我懂data mining,frequent patterns，但是still不会结。讲讲思路嘛。

作者: 周星星1832 时间: 16-3-2009 07:05
会解这道题就能进google?

作者: decisiontree 时间: 16-3-2009 11:49

原帖由 lufumin1832 于 16-3-2009 08:05 发表

 登录/注册后可看大图

会解这道题就能进google?

GOOGLE面试好几轮呢。这只是某轮中的某题。不过你如果能在没做过的情况下，当场给出这题的思路（非BRUTE FORCE）应该是很不错的CANDIDATE。

作者: someonehappy 时间: 16-3-2009 12:07
这题目，得是学过相关知识或者是有过相关工作经历的才能知道大致的答案吧。

有人可以光凭聪明才智就在面试环境中给出答案么？不太现实吧。

作者: 周星星1832 时间: 16-3-2009 12:15
什么是距阵，我早忘了。

作者: beysup 时间: 16-3-2009 12:21
标题: 回复 #9 decisiontree 的帖子
只要找出那些最大的patterns，当然还有threshold的问题，具体我没有实施过，但是我想应该差不多

google招人和微软的风格有一拼，不过基本都是名牌大学这个特点，google从2006年正式进军中国，团队建设已经基本完成，看看相关的新闻就了解了

作者: 周星星1832 时间: 16-3-2009 12:23
看来只招毕业生

作者: beysup 时间: 16-3-2009 12:25
标题: 回复 #15 lufumin1832 的帖子
也有面向社会的，不过要求比较高，去看看就知道了

大公司都偏爱名牌大学的应届生，因为他们才是真正的精英

作者: 周星星1832 时间: 16-3-2009 12:37
看来我是例外了

作者: someonehappy 时间: 16-3-2009 14:58

２１世纪什么最贵？

人才！

作者: 周星星1832 时间: 16-3-2009 14:59
这个我不例外阿

作者: decisiontree 时间: 17-3-2009 14:36

原帖由 beysup 于 16-3-2009 13:21 发表

 登录/注册后可看大图

只要找出那些最大的patterns，当然还有threshold的问题，具体我没有实施过，但是我想应该差不多

google招人和微软的风格有一拼，不过基本都是名牌大学这个特点，google从2006年正式进军中国，团队建设已经基本 ...

Frequent pattern 是可以找的。但是并不是越frequent，Matrix内和越大。因为正负数的大小不知道。
我觉得google和microsoft的面试题很多看似不太难但对知识的深度和广度要求都比较高，不知不觉它就在考你数论，信息论的知识了。

欢迎光临 FreeOZ论坛 (https://www.freeoz.org/bbs/)