一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1836|回复: 18
收起左侧

10/08/2015 Palantir 电面

[复制链接] |试试Instant~ |关注本帖
batman4001 发表于 2015-10-9 05:33:43 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Palantir - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
面经原题:给一个2D的matrix,里面是数字。0代表这个点是水,其他数字代表陆地,相邻的陆地会形成一个岛屿。求所有岛屿的最大值。
比如:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1 2 0 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3 0 4 0
0 1 0 1
结果就是1 + 2 + 3 = 6.

Follow up 1:如果存在值为负数的点会有什么影响?并相应的修改之前的code。

Follow up 2: 之前是用recursive的方法实现的,所以让用iterative的方法重新写一下。

评分

3

查看全部评分

Mark6 发表于 2016-5-31 08:39:31 | 显示全部楼层
有负数的情况,可以先把负数当成0处理。先把每个岛的大小求出来,并且放到这个岛上的所有位置。然后再扫描一下matrix,遇到有负数的,看是否值得把负数周围的岛链接起来,并更新岛的大小。
回复 支持 1 反对 0

使用道具 举报

leixiang5 发表于 2015-10-9 06:26:02 | 显示全部楼层
是不是leetcode number of islands原题啊?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-10-9 06:26:02 | 显示全部楼层
是不是leetcode number of islands原题啊?
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-10-9 06:37:08 | 显示全部楼层
leixiang5 发表于 2015-10-9 06:26
是不是leetcode number of islands原题啊?

不是,这个是把island的所有value加起来,找total最大的value。不是数island的个数。
回复 支持 反对

使用道具 举报

sjtucissy 发表于 2015-10-10 10:22:32 | 显示全部楼层
求问楼主面试官叫啥?
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-10-10 11:39:41 | 显示全部楼层
sjtucissy 发表于 2015-10-10 10:22
求问楼主面试官叫啥?

面试官叫Matt
回复 支持 反对

使用道具 举报

TerrenceLi 发表于 2015-10-12 08:42:58 | 显示全部楼层
有负数有什么影响吗?难道说被数字代表高度,被水包围的负数不算岛吗:)
回复 支持 反对

使用道具 举报

krist 发表于 2015-10-25 00:27:04 | 显示全部楼层
同问负数有什么影响~~~
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-29 14:58:29 | 显示全部楼层
krist 发表于 2015-10-25 00:27
同问负数有什么影响~~~

感觉有没有负数都得把所有的岛遍历一遍,没啥影响。。
回复 支持 反对

使用道具 举报

venomj 发表于 2015-11-5 12:05:55 | 显示全部楼层
肯定有影响啊,负数的可以不累加,但情况并不那么简单
比如:
1  2  3
0 -5  0
0  1  2
最大还是6,但
1  2  3
0 -1  0
0  1  2. 1point3acres.com/bbs
最大就是8了
bfs或dfs时code必须要处理负数情况,如果发现会使总值变小,要抛弃这个点和它后面可能的点
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-5 12:25:48 | 显示全部楼层
venomj 发表于 2015-11-5 12:05
肯定有影响啊,负数的可以不累加,但情况并不那么简单.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如:
1  2  3
.1point3acres缃
噢明白了,负数原来可以不加。。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-11-5 12:27:54 | 显示全部楼层
有负数的情况用dp
回复 支持 反对

使用道具 举报

鬼刃道 发表于 2015-11-12 05:54:55 | 显示全部楼层
请问那个负数的follow up 怎么处理呢?
回复 支持 反对

使用道具 举报

鬼刃道 发表于 2015-11-12 06:12:52 | 显示全部楼层

大神 能详细解释一下吗?
回复 支持 反对

使用道具 举报

thisismj 发表于 2015-11-27 11:08:10 | 显示全部楼层
感觉考虑负数的情况比较难。如果矩阵只有一行,那么就是 MaxSubarray的问题,用到DP解决,但是一般2维怎么用DP?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-28 07:11:48 来自手机 | 显示全部楼层
venomj 发表于 2015-11-5 12:05. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
肯定有影响啊,负数的可以不累加,但情况并不那么简单
比如:
1  2  3

大神可以贴下代码吗?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-11-30 23:24:55 | 显示全部楼层
同求问有负数怎么做
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-31 03:40:24 | 显示全部楼层
venomj 发表于 2015-11-5 12:05
肯定有影响啊,负数的可以不累加,但情况并不那么简单
比如:
1  2  3
.1point3acres缃
那遍历的时候可以如果发现总结过小于0,还得将标记为已读的变为未读吧
回复 支持 反对

使用道具 举报

yangluphil 发表于 2016-11-24 13:59:29 | 显示全部楼层
venomj 发表于 2015-11-5 12:05
肯定有影响啊,负数的可以不累加,但情况并不那么简单
比如:
1  2  3

非0的都是陆地,题目求的是所有岛屿里的最大值不是所有连续陆地的最大值,所以必须加吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 17:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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