一亩三分地论坛

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

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

[找工就业] google onsite

[复制链接] |试试Instant~ |关注本帖
Hgcas 发表于 2016-11-2 01:30:33 | 显示全部楼层 |阅读模式

2017(1-3月)-[14]CS本科+<3个月短暂实习/全职 - 猎头| 码农类全职@Googlefresh grad应届毕业生

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

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

x
MTV 四轮上周面的-google 1point3acres
1. leetcode 425 word square     当时理解错题目了。。。

2. find num of ways from one point to another point (n * n square). from: 1point3acres.com/bbs
    Ex     1 2 3 4
            5  6 7 8
            9 10 11 12

永远从左下 走到 右下,         9 -》 12
只能 往右面走(右上,右,右下)            
follow up: 限定高度和宽度    给m * n
                  必须经过某个点,
                  必须经过某些点. more info on 1point3acres.com
dp 可解

3.  n 支筷子,每个筷子有个length,m个人,每个人拿到的pair 有个diff,如何使最大的diff最小
Ex: (1, 2) diff 1
         (2, 5) diff 3       ====> diff = max(1,3) = 3 (如何使结果最小). more info on 1point3acres.com

         sort一下, 贪心可解, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢国人姐姐各种提示 xD

4. simple design
比较抽象,可以理解手机系统
android 点两下home, ios home按住会出现 当前所有的app,      
如何调度app使用户想用chrome,chrome就到当前的app,其他的app 在background 进程, 同时后端有个监控器,会有一些log记录app的相关信息(比如启动app,app crash了)   理解下app最最基本的生命周期比较好

评分

2

查看全部评分

william_gong 发表于 2016-11-2 01:50:28 | 显示全部楼层
求问第三题贪心的思路,多谢
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-2 02:10:24 | 显示全部楼层
为啥你有design ? new grad 不是不考design 吗
回复 支持 反对

使用道具 举报

suiyuan2009 发表于 2016-11-2 02:26:09 | 显示全部楼层
第三题需要一个简单得dp,或者二分答案贪心吧
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-2 02:44:37 | 显示全部楼层
我也觉得第三题是DP
SORT之后类似house robber吧!
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-11-2 03:25:43 | 显示全部楼层
suiyuan2009 发表于 2016-11-2 02:26
第三题需要一个简单得dp,或者二分答案贪心吧

求思路
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-11-2 05:05:35 | 显示全部楼层
同问为啥楼主有 system design?.鏈枃鍘熷垱鑷1point3acres璁哄潧

楼主也是上周五面的吗?
回复 支持 反对

使用道具 举报

 楼主| Hgcas 发表于 2016-11-2 10:33:16 | 显示全部楼层
第三题 sort 一下, 建个m * n的数组,然后每次看选不选这支筷子,选的话update下max,不选继续recursion
我试着把代码写一下,

吐槽下他们拿的我去年初的简历,那时才大二。。。. more info on 1point3acres.com

design有的,但是不难,当时最后一轮了,讨论了很多,写了大概的框架和里面几个function把其他的讲了讲就没时间了
回复 支持 反对

使用道具 举报

reboot329 发表于 2016-11-2 11:51:19 | 显示全部楼层
意思是现在new grad也考system desgin了。。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-2 16:11:35 | 显示全部楼层
Hgcas 发表于 2016-11-2 10:33
第三题 sort 一下, 建个m * n的数组,然后每次看选不选这支筷子,选的话update下max,不选继续recursion
...

第三题 感觉应该可以优化。。
回复 支持 反对

使用道具 举报

guoyuezhong 发表于 2016-11-2 22:53:59 | 显示全部楼层
求第三题思路~
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 10:26:35 | 显示全部楼层
第四题应该怎么做啊,完全没有思路。==
回复 支持 反对

使用道具 举报

blood8088 发表于 2016-11-4 11:32:21 | 显示全部楼层
说说自己第三题的思路:

先排序,然后用DP,DP里面有个贪心的地方,就是最后选出来的m个pair,每个pair里面的数在原有序数组里肯定是相连的,可用传统贪心的反证法证明这个。

然后就用DP找pair,trivial解O(mn)时间和空间,可以用技巧压到O(n)空间。. 鍥磋鎴戜滑@1point 3 acres

阿咧,打完之后,感觉跟楼主的思路重复了,楼主轻拍。
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 12:35:57 | 显示全部楼层
blood8088 发表于 2016-11-4 11:32
说说自己第三题的思路:

先排序,然后用DP,DP里面有个贪心的地方,就是最后选出来的m个pair,每个pair ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是[i, i+1] 那么dp 转移方程为. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
dp[m][j][l] = min{max{dp[m1][j][i-1]}, dp[m2][i+1][l], diff(i, i+1)} (m1 + m2 = m-1)....
不过感觉复杂度不止o(mn)...
似乎可以继续优化。。。
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 12:41:45 | 显示全部楼层
achilleszou 发表于 2016-11-4 12:35. from: 1point3acres.com/bbs
我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是 那么dp 转移方程为

貌似下面的dp 更简单。. 1point 3acres 璁哄潧
dp[j] = min{dp[j-1], max{diff(j, j-1), dp[i-1][j-2]}
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 12:44:47 | 显示全部楼层
achilleszou 发表于 2016-11-4 12:41
貌似下面的dp 更简单。
dp[j] = min{dp[j-1], max{diff(j, j-1), dp[j-2]}

写错了,应该是:

dp[j] = min{dp[j-1], max{diff(j, j-1), dp[i-1][j-2]}

dp[j] 表示在 下标[0...j] 中取i对筷子。
回复 支持 反对

使用道具 举报

blood8088 发表于 2016-11-4 12:45:14 | 显示全部楼层
achilleszou 发表于 2016-11-4 12:35
我的思路差不多。. 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs
因为每次选出的pair 是相邻的。那么假设选出的pair 是 那么dp 转移方程为

我觉得是这样。. Waral 鍗氬鏈夋洿澶氭枃绔,

dp[m] = min( dp[m][i + 1],                                      ----> 不选 pair(i, i+1)
                         max(dp[m - 1][i + 2], diff(i, i+1))        ----> 选 pair(i, i+1)


补充内容 (2016-11-4 12:46):
打错,等式左边应该是 dp[m];. 1point 3acres 璁哄潧

补充内容 (2016-11-4 12:47):
dp[m][  i  ]
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 12:56:56 | 显示全部楼层
blood8088 发表于 2016-11-4 12:45
我觉得是这样。
. from: 1point3acres.com/bbs
dp[m] = min( dp[m],                                      ----> 不选 pair(i, i+1) ...

你的dp 解法中 dp[m] 代表从 [i, ... n] 中 选m双筷子?.1point3acres缃

我的解法中 dp[m] 代表从[0, ... i] 中 选m双筷子。

如果我的理解没错的话,应该两个都行
回复 支持 反对

使用道具 举报

achilleszou 发表于 2016-11-4 12:57:48 | 显示全部楼层
achilleszou 发表于 2016-11-4 12:56
你的dp 解法中 dp[m] 代表从  中 选m双筷子?

我的解法中 dp[m] 代表从[0, ... i] 中 选m双筷子。

为啥发帖中 【】【】 被删了。。。。。==|
回复 支持 反对

使用道具 举报

blood8088 发表于 2016-11-4 13:11:01 | 显示全部楼层
achilleszou 发表于 2016-11-4 12:57
为啥发帖中 【】【】 被删了。。。。。==|
. From 1point 3acres bbs
[     i      ]


好像会被解释成斜体字(italic),类似html什么的吧。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 22:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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