一亩三分地论坛

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

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

[找工就业] Google电面

[复制链接] |试试Instant~ |关注本帖
baiery 发表于 2016-1-21 03:40:09 | 显示全部楼层 |阅读模式

2016(1-3月)-[14]EE硕士+<3个月短暂实习/全职 - 内推| 码农类全职@Googlefresh grad应届毕业生

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

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

x
刚面玩谷歌电面,心情还难以平复,谷歌是楼主的dream company,虽然知道自身水平可能要进去还是比较困难的,可是不能放弃啊!!
面试官上来没有多说啥,直接打开google doc开写,一共2道题。
第一题是给一个binary tree,然后判断每个节点的左子树和右子树的val和是否相等,如果整个树满足条件,最后return true。这题有点紧张,我做法有点暴力,对于每个节点我都重新算了他们子树val的和,这样时间复杂度应该是N*logN,不过面试官也买账了。我后来想到其实可以用个数据结构把各个节点的和存起来,省的每次重新算整个树。
迅速第二题,第二题是我刚好前一天看到的Find the longest substring with k unique characters in a given string,但是因为太晚了想说今天再看,结果没来得及看就考了。。。我看到题目内心崩溃了一下。。。不过我还是冷静下来,我的一开始的做法是用一个类似window的结构,或者说就是two pointer,start和end,遍历整个string,然后window内部的char全都存到hashmap里,key是char,value是count,一边遍历整个string,一边update start和end,update的方法是我另外写了一个function来检查以start为头,end为尾的这个substring是不是符合unique k的条件,然后每次update结束之后,我用另外一个string来记录当前最长的substring,看是否需要update这个string,最后返回这个string就是最长的了。不过因为我的那个check function需要O(N),所以整个算法最后是O(N^2),面试官问能不能提高到O(N),我想了想发觉不需要另外设计一个check function,直接用hashmap就可以检测,如果不满足条件就把start往后移动,更新hashmap,直到满足才停止,所以相当于start 遍历了一边,end遍历了一边,所以时间是2*N,也就是N,然后面试官挺满意这个结果,让我问了几个问题就结束啦。
楼主实在是太紧张了,讲话一直结巴,希望没有太影响面试结果,求onsite~~~~~~~就算没有offer也让我去onsite一次吧~~~~~~~~


补充内容 (2016-1-21 04:12):
第一题follow up了一点,就是如果把val从int改成float会有什么问题,我也不太确定,说的是会有精度问题,所以如果要比较是否相等时,需要自己定义一个isEqual,只要差值小于某个很小的值,就相等
hitowings 发表于 2016-1-22 16:40:40 | 显示全部楼层
楼主是找内推的么?啥时候投的?
回复 支持 反对

使用道具 举报

cicitaotao 发表于 2016-2-5 13:45:35 | 显示全部楼层
lz知道面试结果了吗》
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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