一亩三分地论坛

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

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

新鲜G家店面

[复制链接] |试试Instant~ |关注本帖
冰川之狐 发表于 2016-9-18 11:13:55 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
本周三刚面完,在地里发一下.。
上次有过一次店面,但是由于分的组和电话声音的问题,面的不好。然后recruiter和我沟通了之后觉得再给我一次机会。上次的店面请戳链接
由于我是在美东,和美西时间差3小时,所以面试时间比较晚,6点开始。面食的人叫Mike,以白人小哥,挺和蔼的,是technical manager。然后电话里面声音有点浑浊,不过仔细听还能听清楚。小哥先和我闲扯了几句,然后问我Java和C++那个更好,我说C++;他说那也行,你写C++,我能看懂,好几年前用的了,不过题目是用Java写的,然后直接上题。
. From 1point 3acres bbs
第一题
就是lc里面的303,给了一个接口Sum,里面有set和sum两function,还有一个存数据的数据结构。他咸用一个数组来存放数据,然后问我用这个的好处是什么。我说了可以直接用index获取其中的数据,也可以快速获取头和尾,搜索的话如果是顺序的可以用BS来快速搜索。然后他问sum这个function的时间复杂度呢?我说你这里只给了声明,没有implementation,我不知道;他说就一个一个加,我说那worse case就是O(n)。他说好,那如果sum要被经常调用的话O(n)肯定不行,你要怎么弄好。问道这心理暗喜,因为在lc做过了,但是还是平静一下先询问一下条件,比如是用数组寸数据吗,固定长度吗之类之类的。然后确认好就说了当前单元存放之前所有元素之和,他说可以,然后就开始写。因为他给的是一个接口,然后需要自己定义个一数组来存放数据,另外一个来存放加和的sum的数据,然后再写接口里面的函数,写的时候没注意,当前单元格里面的值还包含了苯单元格的值,经他指出来我修改了。然后他问时间复杂度?我说O(1),他说你再写一下set函数,我就直接对index的单元格里面更新值,然后重新再计算一次加和的sum(后来想想可以不用从头开始算,从更新的index算就行了,不过他也没有说什么)

第二题
lc的304,从一维数组审计到二维数组,问我怎么generalize刚才的solution。我想了一下,可以对每一行进行刚才的求和,然后根据坐标求对应行subSum的总和就行了,我就写了一下。写完了他问我求二维的时间复杂度,我说之前求每个单元格之前的部分Sum的这里因为便利了所有元素,所以是O(n), n = row*col,然后说sum坐标范围的时候二了一下,因为他给的例子坐标是只求了两行的,然后我就说是O(1),然后他说你这个好像不太对,有这么多航。我立马意识到求全部的行当然不是O(1),立马改成O(row),他说好。

面试问题基本就是这样,一共40分钟这样。他问我有没有什么问题问他,我就问这些面试题目是在工作中遇到的吗?他笑笑说不是。然后就介绍了一下工作。他说我还做的不错,我心里挺开心,想想碰到的题目不难真是运气好。全称他挺supportive的,但是一直在说比较好的话,不知道最终反馈给HR那边怎么样。所以在地里面发发面经攒人品,求过求Onsite!
.鐣欏璁哄潧-涓浜-涓夊垎鍦




补充内容 (2016-9-22 01:31):
今天Recruiter打电话过来告诉我说不move forward

补充内容 (2016-9-22 04:06):
-google 1point3acres经过和地里面的小伙伴讨论, 觉得面的题目应该是LC307和308.

评分

1

查看全部评分

PennyLoveLife 发表于 2016-9-22 01:59:18 | 显示全部楼层
我感觉这是lc307的题,因为sum要经常调用,是不是说明里面的值会更新?
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 02:05:32 | 显示全部楼层
PennyLoveLife 发表于 2016-9-22 01:59
我感觉这是lc307的题,因为sum要经常调用,是不是说明里面的值会更新?

对,看了一下应该是307和308。
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-9-22 02:21:54 | 显示全部楼层
都做出来了竟然还没过。。。。。。。
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 02:41:55 | 显示全部楼层
chenyuhaohy 发表于 2016-9-22 02:21
都做出来了竟然还没过。。。。。。。

如果是307和308的话情况就不一样了
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-9-22 03:52:37 | 显示全部楼层
冰川之狐 发表于 2016-9-22 02:41
如果是307和308的话情况就不一样了

.鐣欏璁哄潧-涓浜-涓夊垎鍦这几道题我还以为很偏所以没做过。看leetcode上提交的次数也很少。。
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 04:04:46 | 显示全部楼层
chenyuhaohy 发表于 2016-9-22 03:52
这几道题我还以为很偏所以没做过。看leetcode上提交的次数也很少。。

-google 1point3acres恩,我也只做过303和304,没有看307和308,其实前后差别挺大的,后面的要难
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-9-22 04:06:03 | 显示全部楼层
估计他要求用BIT做吧
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 04:08:43 | 显示全部楼层
xihaokai1 发表于 2016-9-22 04:06
估计他要求用BIT做吧

是的,我因为没做过,所以不知道改用BIT,他也一点提醒都没有,就一直让我继续说说说,最后还说做的不错
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-9-22 04:10:13 | 显示全部楼层
冰川之狐 发表于 2016-9-22 04:08
是的,我因为没做过,所以不知道改用BIT,他也一点提醒都没有,就一直让我继续说说说,最后还说做的不错{ ...

. 1point3acres.com/bbs用BIT是不是太难了额。。学校都没教过这东西。。
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 04:12:31 | 显示全部楼层
chenyuhaohy 发表于 2016-9-22 04:10
用BIT是不是太难了额。。学校都没教过这东西。。

不用BIT的话时间复杂度估计不行。毕竟Google是intenent的公司,要处理大量数据。
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-9-22 12:29:20 | 显示全部楼层
冰川之狐 发表于 2016-9-22 04:12
不用BIT的话时间复杂度估计不行。毕竟Google是intenent的公司,要处理大量数据。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问下LZ是本科还是研究生还是PhD?
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-22 23:52:12 | 显示全部楼层
chenyuhaohy 发表于 2016-9-22 12:29. 1point 3acres 璁哄潧
请问下LZ是本科还是研究生还是PhD?

LZ是master。
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-9-23 12:11:24 | 显示全部楼层
其实lc 307 和308比303 304就多了一个update 函数, 也就是面试官说的set函数, 其他都一样的........
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-9-23 23:58:50 | 显示全部楼层
qiuxuxing007 发表于 2016-9-23 12:11
其实lc 307 和308比303 304就多了一个update 函数, 也就是面试官说的set函数, 其他都一样的........

关键是要怎么实现update,naive的update需要O(n),用BIT可以实现O(logn)。估计面试官就想看的是BIT...
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-4 09:13:39 | 显示全部楼层
有SET的话应该是307和308,楼主理解错题目了,估计是悲剧的原因
回复 支持 反对

使用道具 举报

 楼主| 冰川之狐 发表于 2016-10-4 21:55:01 | 显示全部楼层
liurudahai 发表于 2016-10-4 09:13
有SET的话应该是307和308,楼主理解错题目了,估计是悲剧的原因

是的,所以悲剧了,在这也给大家提个醒吧
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-8 14:16:44 | 显示全部楼层
chenyuhaohy 发表于 2016-9-22 02:21
都做出来了竟然还没过。。。。。。。

因为307 308要用 binary indexed tree 写
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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