《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 177|回复: 1
收起左侧

Quora OA 新题 & 解答

[复制链接] |试试Instant~ |关注本帖
bambooshoot 发表于 2017-11-9 07:09:31 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 本科 实习@Quora - 校园招聘会 - 在线笔试 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
前段时间遇到了 Quora OA 的一道新题,在地里和其他地方搜了一下,没有搜到这题,应该是新题。正好看到有人问,就发出来造福大家。
题目描述:给一个 N*N 的矩阵,每个位置有一个可正可负的 integer。要求从矩阵中取出一个 rectangular,让其包含的数字之和最大。
50% 的数据:N <= 50
70% 的数据:N <= 100
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴100% 的数据:N <= 500

这个题应该算是比较经典的题了,如果是 O(N^4) 的算法应该可以过 50%,O(N^3) 的算法应该可以过 70%,要全过的话应该需要更快的算法。.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ 是用 Python 写的  O(N^3) 的算法,不出所料只过了 70%。具体方法可以看这个链接:-google 1point3acres
http://www.geeksforgeeks.org/dyn ... gle-in-a-2d-matrix/
-google 1point3acres
简单来说就是枚举平行的两条边界,转换为 1-D maximum sum subarray 的问题。
. from: 1point3acres.com/bbs
不知道有没有人知道更快的算法,大家讨论一下。我猜可能是二分答案或者是树状数组之类的吧。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

lchena 发表于 2017-11-9 07:31:54 | 显示全部楼层
谢谢楼主分享!楼主收到的oa link email里面,写的这个oa的题目是什么呀?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-21 16:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表