Google SWE intern 电面

倒序浏览 · 2019-10-30 10:31:33

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

两轮电面
第一轮 house robber III 的变种，包含负

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

如何phd毕业的心得。

求大米！！！

tomdzh123 · 2019-10-30 22:12:02

第一轮包含负数的就是要注意沿tree往上sum为负的时候要清零。

不知道小帅 · 2019-10-30 11:19:00

本帖最后由不知道小帅于 2019-10-30 11:38 编辑

第二轮那个最优解的话是啥啊，我可以想到O(n) time的sliding window,是这样处理吗。

uathena · 2019-11-30 06:50:10

yezhengli_mr9 发表于 2019-11-8 14:33
楼上有回答“第一轮包含负数的就是要注意沿tree往上sum为负的时候要清零”，但我总感觉有各种edge case.

难道不是遇到为负的时候就默认不rob吗？反正不rob了上面相邻一层可rob可不rob反而更自由？

rpfernman1 · 2019-10-30 11:29:11

不知道小帅发表于 2019-10-30 11:19
第二轮那个最优解的话是啥啊，你可以想到O(n) time的sliding window,是这样处理吗。

如果没有额外信息，就必须穷尽所有可能，显然O(n)是下限

onerhao · 2019-10-30 15:18:44

不是2d动态规划解吗
i递减，j递增

insomniadog · 2019-10-30 15:58:25

请问第一题包含负数需要有哪些改变么？感觉和原题解法一样？

insomniadog · 2019-10-30 15:59:39

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

tomdzh123 · 2019-10-30 22:15:56

第二轮，时间复杂度O(N)，关键点在于如何把n拆成两部分，一部分从左边取，一部分都是从右边取，取的顺序是不重要的，各取了几个才是重要的。需要计算两个辅助array，一个是从左到右的prefix和，一个是从右到左

codeyy · 2019-10-30 23:51:06

物理教授。g家真是人才辈出啊

skrm

楼主有消息吗？