一亩三分地论坛

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

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

Google实习电面

[复制链接] |试试Instant~ |关注本帖
rhett.lhy 发表于 2015-1-17 17:29:56 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Pass

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

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

x
一共两轮电面,第一轮是个中国人,问了两道题:第一题是化简linux path,就是比如"/a/b/../c"要化简成"/a/c"。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题是求一个矩阵内的最大子矩阵和,然后问了如果矩阵里有负数有没有关系(没关系因为是DP)。. 1point3acres.com/bbs

第二轮是个外国人,问了一道题:有N个已经排好序的数列,要把他们合并成一个有序数列。之后扩展了一下问如果给你一个cluster你会如何处理这个问题。

总体感觉第一个中国人问的比较中规中矩,第二个外国人问的很发散,比较research oriented。

面试完之后pass了,可惜这次没有匹配到合适的team。.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

mzhang 发表于 2015-1-18 07:30:45 | 显示全部楼层
PHD? 字数字数
回复 支持 反对

使用道具 举报

masa 发表于 2015-1-18 07:48:40 | 显示全部楼层
mzhang 发表于 2015-1-18 07:30.鏈枃鍘熷垱鑷1point3acres璁哄潧
PHD? 字数字数

-google 1point3acres寫了本科
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-1-18 07:54:42 | 显示全部楼层
"可惜这次没有匹配到合适的team"指老死在池子里?。。。
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-18 08:25:44 | 显示全部楼层
kurtwang 发表于 2015-1-18 07:54
"可惜这次没有匹配到合适的team"指老死在池子里?。。。
. from: 1point3acres.com/bbs
匹配了3次team都觉得不太合适,就去了FB
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-18 08:26:13 | 显示全部楼层

恩,PhD在读
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-18 08:26:47 | 显示全部楼层

也可能我写错了,我看要选的是已获得的最高学历,我就写了本科。我现在是PhD在读。
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-1-18 09:16:29 | 显示全部楼层
rhett.lhy 发表于 2015-1-18 08:25
匹配了3次team都觉得不太合适,就去了FB
. 1point 3acres 璁哄潧
原来如此
回复 支持 反对

使用道具 举报

applepie11 发表于 2015-1-19 02:59:44 | 显示全部楼层
最大子矩阵你是用n2的方法做的吗?
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-19 03:03:29 | 显示全部楼层
applepie11 发表于 2015-1-19 02:59
最大子矩阵你是用n2的方法做的吗?

恩是的 (n是矩阵的边长)
. from: 1point3acres.com/bbs
补充内容 (2015-1-19 03:05):
看错了,最优算法应该是O(n^3)吧?枚举上下边界然后按照一维的问题从左往右DP。
回复 支持 反对

使用道具 举报

applepie11 发表于 2015-1-19 03:06:58 | 显示全部楼层
rhett.lhy 发表于 2015-1-19 03:03
恩是的 (n是矩阵的边长). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2015-1-19 03:05):
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那得先把histogram编一下,我觉得解释起来挺麻烦的呀,你咋在电话解释清楚的呀??
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-19 03:12:19 | 显示全部楼层
applepie11 发表于 2015-1-19 03:06.鐣欏璁哄潧-涓浜-涓夊垎鍦
那得先把histogram编一下,我觉得解释起来挺麻烦的呀,你咋在电话解释清楚的呀??

啊?这个和histogram不一样的吧……硬要说联系的话,histogram是总体图形是个不规则图形,网格化的话每个格子可以看做是weight为1;这个题是整体矩阵是个规则的正方形/长方形,每个格子里的weight可以是不一样的……
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-19 03:13:10 | 显示全部楼层
applepie11 发表于 2015-1-19 03:06
那得先把histogram编一下,我觉得解释起来挺麻烦的呀,你咋在电话解释清楚的呀??

反正我当时直接跟他说这是个经典DP问题,然后就开始编,编完随便解释了两句就过了……
回复 支持 反对

使用道具 举报

applepie11 发表于 2015-1-19 06:54:06 | 显示全部楼层
rhett.lhy 发表于 2015-1-19 03:13
反正我当时直接跟他说这是个经典DP问题,然后就开始编,编完随便解释了两句就过了……

我想的是在histogram里找最大矩形,然后套回原题。要是普通dp是n3吧?类似这种http://blog.csdn.net/yusiguyuan/article/details/12877103. 1point3acres.com/bbs

你是怎么dp的?
回复 支持 反对

使用道具 举报

 楼主| rhett.lhy 发表于 2015-1-19 08:29:57 | 显示全部楼层
applepie11 发表于 2015-1-19 06:54
我想的是在histogram里找最大矩形,然后套回原题。要是普通dp是n3吧?类似这种http://blog.csdn.net/yusi ...

col[j]表示第i竖列index从0到j的和,然后两重循环枚举上下界,循环里面从左往右按照经典的一维问题做,上下界之间每一列的和就是把对应的col减一下就行了
回复 支持 反对

使用道具 举报

applepie11 发表于 2015-1-19 10:15:39 | 显示全部楼层
rhett.lhy 发表于 2015-1-19 08:29-google 1point3acres
col[j]表示第i竖列index从0到j的和,然后两重循环枚举上下界,循环里面从左往右按照经典的一维问题做,上 ...

那就是每一行累加上面所有值吗?枚举上下界目的是什么?能稍微说明一下吗?找矩形吗?
如果是两重循环,每个循环里面不是O(n)吗?难道是O(1) 找最大子段和?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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