一亩三分地论坛

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

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

gg intern 02/09面经

[复制链接] |试试Instant~ |关注本帖
candy_shmily 发表于 2016-2-10 10:55:43 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
本帖最后由 candy_shmily 于 2016-2-10 08:41 编辑

趁着跑test来发面经求RP
约的时间是今天12:00PM-1:00PM第一轮 1:00PM-2:00PM第二轮

第一轮印度小哥 口音虽然重。。。但是平时跟印度人组队学习的唯一好处就是现在听他们讲话无压力= =
上来直接做题
http://www.careercup.com/question?id=5648527329853440
then 时间复杂度空间复杂度. 鍥磋鎴戜滑@1point 3 acres
之前没看过面经 面完查到的. From 1point 3acres bbs
. more info on 1point3acres.com
第二轮白人小妹儿 听起来感觉特热情。。。
一上来问我recent project 我去。。。不是gg都是一上来直接做题的吗。。。蒙圈儿三秒之后 cc大法好。。。
然后做题 面完也没找到这个题 我简单描述一下。。。
一个N*N matrix 每一个点由如下class表示
class Point{
    int x;
    int y;. From 1point 3acres bbs
}
对于matrix里的点 要么可以站在上面loop up/down/left/right 要么就是wall或者light wall可以挡住lights.鏈枃鍘熷垱鑷1point3acres璁哄潧
比如
L*LQ*W. 1point3acres.com/bbs
*L****
W*LL**. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
L*L**W
*L****
W*LL**

比如站在这个Q点 可以看到4个lights(左边两个下面两个).1point3acres缃
要求找到这个matrix里面可以看到最多lights的Point 并且return it
input是walls, lights, N (walls和lights是List<Point>)
output是Point

then 时间复杂度空间复杂度

anyway 结果不重要了 已经从了amazon 发面经攒人品给男票下周面amazon 求a也收了他 于是咱们就可以一起去Seattle愉快地浪起来了~~~
.1point3acres缃

评分

3

查看全部评分

johnjavabean 发表于 2016-2-10 14:36:13 | 显示全部楼层
第二题google变了N种问法考的....有炸弹,怪兽和墙的,有人,花和墙的....现在又来了人,灯和墙.....也是醉了.....是fulltime onsite经常遇到的一道题,第一题还真没见过....再次证明了狗家题库浩如烟海
回复 支持 1 反对 0

使用道具 举报

johnjavabean 发表于 2016-2-10 15:14:46 | 显示全部楼层
然后似乎左和上可以一起算,右和下可以一起算,于是乎可以两次遍历就得到最大值

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

ilyak 发表于 2016-2-10 14:59:37 | 显示全部楼层
johnjavabean 发表于 2016-2-10 14:36. from: 1point3acres.com/bbs
第二题google变了N种问法考的....有炸弹,怪兽和墙的,有人,花和墙的....现在又来了人,灯和墙.....也是醉 ...

可以求第二题的做法咩?!
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-10 15:02:53 | 显示全部楼层
ilyak 发表于 2016-2-10 14:59
可以求第二题的做法咩?!

新建一个矩阵,先按行得到每个点往左往右看能看到灯总数,墙的点为0,然后再按列遍历,把上下看的总数加上去,最后求一个max,时间复杂度空间复杂度都是n^2
回复 支持 反对

使用道具 举报

ilyak 发表于 2016-2-10 15:04:50 | 显示全部楼层
哦哦哦相当于brute force遍历整个matrix可以落脚的点?谢谢!
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-10 15:06:54 | 显示全部楼层
johnjavabean 发表于 2016-2-9 23:02
新建一个矩阵,先按行得到每个点往左往右看能看到灯总数,墙的点为0,然后再按列遍历,把上下看的总数加 ...

这个时间复杂度是O(n^3) 空间复杂度是O(n)
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-10 15:07:41 | 显示全部楼层
ilyak 发表于 2016-2-10 15:04
哦哦哦相当于brute force遍历整个matrix可以落脚的点?谢谢!

并不是....你这样复杂度是m*n*(m+n)
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-10 15:12:37 | 显示全部楼层
candy_shmily 发表于 2016-2-10 15:06
这个时间复杂度是O(n^3) 空间复杂度是O(n)

看来我表述的不清楚,第一遍按行左到右,dp[j] = dp[j-1] + 1 if m[j] == L,遇到W直接设成0,然后从右到左再加一遍,然后从上到下,从下到上,最后一遍可以顺便求出max,四边遍历,每次n^2,所以n^2时间n^2空间

补充内容 (2016-2-10 15:13):.鏈枃鍘熷垱鑷1point3acres璁哄潧
晕....打[   i  ]会直接变斜体,其实是dp[ i   ][j]啦
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-10 15:12:47 | 显示全部楼层
johnjavabean 发表于 2016-2-9 23:07
并不是....你这样复杂度是m*n*(m+n)

worst case有N*N个点要check 每个点要最多要check行和列2N 于是N^3
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-10 15:13:47 | 显示全部楼层
johnjavabean 发表于 2016-2-9 23:12
看来我表述的不清楚,第一遍按行左到右,dp[j] = dp[j-1] + 1 if m[j] == L,遇到W直接设成0,然后从右到 ...

那我们的方法不一样 你的比较高端 是她的follow up 我没写出来 只会N^3的
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-2-10 15:22:57 | 显示全部楼层
google的题上来一开始咋都觉得是看不懂啊
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-11 00:39:06 | 显示全部楼层
mchzh 发表于 2016-2-9 23:22. Waral 鍗氬鏈夋洿澶氭枃绔,
google的题上来一开始咋都觉得是看不懂啊

我也觉得我遇到的题好难 一开始看题都看了半天 第二个白人小妹儿说话又快 越解释越快我越蒙= =
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-15 09:45:07 | 显示全部楼层
请教楼主这两题咋做的啊?第一题我的想法是用union find做但是需要O(NlongN)了,第二个如果生成矩阵的话,L相对来说比*少的话,从L来DFS好像快一点
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-15 10:56:42 | 显示全部楼层
lxxxxxxx 发表于 2016-2-14 17:45. more info on 1point3acres.com
请教楼主这两题咋做的啊?第一题我的想法是用union find做但是需要O(NlongN)了,第二个如果生成矩阵的话,L ...

我都是brute force来的。。。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-15 10:58:05 | 显示全部楼层
candy_shmily 发表于 2016-2-15 10:56
我都是brute force来的。。。

soga!谢谢啦!!沾沾楼主喜气希望亚麻也能给我发offer QAQ
回复 支持 反对

使用道具 举报

yanyanlr 发表于 2016-2-27 06:09:17 | 显示全部楼层
请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊
回复 支持 反对

使用道具 举报

 楼主| candy_shmily 发表于 2016-2-27 15:45:46 | 显示全部楼层
yanyanlr 发表于 2016-2-26 14:09
请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊啊啊 请联系我啊 ...

联系你干啥呀熊嬷嬷
回复 支持 反对

使用道具 举报

yanyanlr 发表于 2016-2-27 23:48:28 | 显示全部楼层
candy_shmily 发表于 2016-2-27 02:45.1point3acres缃
联系你干啥呀熊嬷嬷

不知道    发觉奸情
回复 支持 反对

使用道具 举报

yanyanlr 发表于 2016-2-28 01:15:30 | 显示全部楼层
candy_shmily 发表于 2016-2-27 02:45
联系你干啥呀熊嬷嬷

不要乱起外号    有男淫的  妞妞
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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