一亩三分地论坛

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

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

Google新鲜面经

[复制链接] |试试Instant~ |关注本帖
excellent5 发表于 2015-11-19 04:42:27 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
刚刚面完,感觉是要跪了,攒RP
第一轮,应该是个美国人。问了下你做过的最大的项目,里面用到了哪些test的工具之类的。然后开始搞算法题。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
给定一个二维数组,让你找里面有多少个3*3的正方形,每行每列每个对角线的和都是一个给定的值。我这题想不到好方法,直接暴力遍历所有3*3的方格去检查了。。。
这道题完了之后,又问了下Java里面的sychonized和static关键字是什么意思,然后给了个函数让你找有什么bug(溢出和线程同步)

第二轮,印度人。
第一题是leetcode上面的buy and sell stock II,用贪心算法做的
第二题是如果改一下变成卖完股票之后需要等一天再买,最大收益多少。这题并没有好的思路,又是基本遍历做的。。各位大神们有什么好想法吗. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

2

查看全部评分

本帖被以下淘专辑推荐:

Jaden 发表于 2015-11-19 04:49:21 | 显示全部楼层
第二题听起来和那个leetcode抢劫的题有点像,抢了一间以后不能抢下一间,只能隔着抢,还是用dp做吧。
回复 支持 反对

使用道具 举报

 楼主| excellent5 发表于 2015-11-19 06:10:20 | 显示全部楼层
Jaden 发表于 2015-11-19 04:49
第二题听起来和那个leetcode抢劫的题有点像,抢了一间以后不能抢下一间,只能隔着抢,还是用dp做吧。

是不是这样,保存每天卖出的获得的收益最大值。
假设我在第i天卖出,第j天最后一次买进,那递归式就是OPT(i) = Max[OPT(j-1) + P(i) - P(j)],然后由于我们不一定要在j-1天买进,所以要算1<=k<=j-1中的OPT(K)的最大值来替换OPT(j-1)
回复 支持 反对

使用道具 举报

ljdsoft 发表于 2015-11-19 06:27:39 | 显示全部楼层
感觉好难,祝楼主好运
回复 支持 反对

使用道具 举报

Jaden 发表于 2015-11-19 06:50:26 | 显示全部楼层
excellent5 发表于 2015-11-19 06:10
是不是这样,保存每天卖出的获得的收益最大值。
假设我在第i天卖出,第j天最后一次买进,那递归式就是OP ...

恩 我想的也差不多,只不过楼主那个max里好像没写完。
我现在想出来的是:

dp[0] = 0 因为第一天肯定没发获利.鐣欏璁哄潧-涓浜-涓夊垎鍦
dp =  max(price-price[i-1]+dp[i-1],dp[i-1]);

不知道对不对。

补充内容 (2015-11-19 06:50):
dp =  max(price-price[i-1]+dp[i-1],dp[i-1]);. 1point3acres.com/bbs

补充内容 (2015-11-19 06:51):
dp不知道为啥打不出来。。。
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-19 07:23:44 | 显示全部楼层
excellent5 发表于 2015-11-19 06:10. 鍥磋鎴戜滑@1point 3 acres
是不是这样,保存每天卖出的获得的收益最大值。
假设我在第i天卖出,第j天最后一次买进,那递归式就是OP ...

貌似有道理,不过OPT(i)不应该等于 Max[OPT(j-2) + P(i) - P(j)]么?
因为如果第j天买进,说明j-1天的时候是不能卖出的,也就是最早也是j-2天卖出的才能在j天买进吧?
回复 支持 反对

使用道具 举报

Jaden 发表于 2015-11-19 07:33:24 | 显示全部楼层
stonezms 发表于 2015-11-19 07:23
貌似有道理,不过OPT(i)不应该等于 Max[OPT(j-2) + P(i) - P(j)]么?
因为如果第j天买进,说明j-1天的时 ...

但是你更新j-1的时候会做一次相同的判断,所以这时候opt(j-1)和opt(j-2)在不买的情况下,应该是相同的吧。
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-19 07:40:50 | 显示全部楼层
Jaden 发表于 2015-11-19 07:33. Waral 鍗氬鏈夋洿澶氭枃绔,
但是你更新j-1的时候会做一次相同的判断,所以这时候opt(j-1)和opt(j-2)在不买的情况下,应该是相同的吧 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
额。。。先确认下楼主OPT(i)表示的是什么啊,我理解是在i的时候卖的最大profit吧?
. From 1point 3acres bbs
然后没懂为什么“opt(j-1)和opt(j-2)在不买的情况下,应该是相同的”?能详细解释下么,谢!
回复 支持 反对

使用道具 举报

Jaden 发表于 2015-11-19 07:47:42 | 显示全部楼层
stonezms 发表于 2015-11-19 07:40
额。。。先确认下楼主OPT(i)表示的是什么啊,我理解是在i的时候卖的最大profit吧?

然后没懂为什么“o ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我重写想了一些,opt(j-1)和opt(j-2)不相同。。不好意思
opt(j) 就代表第j天的最大利润, 那么opt(j) = max(p(j)-p(j-1)+opt(j-1),opt(j-2)),如果max里第一项大,那说明继续持有,如果第二项大,那说明j-2那一天就卖了,j-1这一天啥也不能干。
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-19 07:57:28 | 显示全部楼层
Jaden 发表于 2015-11-19 07:47. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我重写想了一些,opt(j-1)和opt(j-2)不相同。。不好意思
opt(j) 就代表第j天的最大利润, 那么opt(j) =  ...

这个好像跟楼主那个思路不大一样。。。总觉的哪里有问题 额。。
回复 支持 反对

使用道具 举报

 楼主| excellent5 发表于 2015-11-19 08:21:44 | 显示全部楼层
stonezms 发表于 2015-11-19 07:23.1point3acres缃
貌似有道理,不过OPT(i)不应该等于 Max[OPT(j-2) + P(i) - P(j)]么?
因为如果第j天买进,说明j-1天的时 ...

嗯,对的,按他给的例子来说如果你在第j-1天卖出了的话,需要至少等到j+1填才能买进,这里应该是OPT(j-2)
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-11-19 09:43:22 | 显示全部楼层
求问楼主什么叫基本遍历?
回复 支持 反对

使用道具 举报

 楼主| excellent5 发表于 2015-11-19 09:45:25 | 显示全部楼层
Augustus 发表于 2015-11-19 09:43
求问楼主什么叫基本遍历?

我的意思是基本是brute-force的方法遍历所有可能的买卖方法做的
回复 支持 反对

使用道具 举报

 楼主| excellent5 发表于 2015-11-19 09:52:47 | 显示全部楼层
Augustus 发表于 2015-11-19 09:43
求问楼主什么叫基本遍历?

第二轮第二题,我是这么做的,定义一个maxprofit(int[] prices, int startday)表示从startday开始能得到的最大利润(可以不在startday买),然后递归这个函数。

  1. int currentmaxprofit = 0;
  2. for(int i=startday; i<price.length; i++)
  3.     for(int j=i; j<price.length; j++)
  4.         currentmaxprofit = max[price[j] - price[i] + maxprofit(price, j+2), currentmaxprofit];
  5. return currentmaxprofit;
复制代码
这样的话重复算了很多遍一样的东西,应该用DP之类的把算过的memorization
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 12:14:51 | 显示全部楼层
第一轮 3* 3的正方形也只能暴力做吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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