一亩三分地论坛

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

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

关于google fail掉以后的问题+面经

[复制链接] |试试Instant~ |关注本帖
chengyaxue 发表于 2015-5-29 07:55:10 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - Other - Onsite |Failfresh grad应届毕业生

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

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

x
最近刚面完google。然后hr打电话说hc没给offer, 但是她会给我找组。本来以为他说说而已,结果她后来还真发邮件来问我什么javascript写得怎么样?
我想请教一下, 这是什么情况?
因为google已经搞了一学期了,如果没什么希望就不太想花时间在它上面了。要是还是有希望, 我就准备去恶补js了
谢谢各位了。
另外贴一下面经. 1point3acres.com/bbs
1. 忘记了。。。
2. 给一个很大的文件,里面全是url,like yahoo.com, 有重复,输出一个文件,url unique
3. 两个general tree,A和B, A很大,判断B是不是A的子树
4. complete binary tree, 求结点个数

评分

2

查看全部评分

本帖被以下淘专辑推荐:

mymiracle 发表于 2015-5-29 20:24:21 | 显示全部楼层
意思是你的面试结果虽然没那么理想,但也不糟糕。
如果找到有个组要你的话还是有希望的。
然后她发现最近各个要人的组要js的人多,就这么问了问你。
回复 支持 反对

使用道具 举报

嘻嘻呵呵飞出去 发表于 2015-6-1 01:26:50 | 显示全部楼层
第2题的意义在哪里啊?考读写文件的function?
回复 支持 反对

使用道具 举报

laoxie09 发表于 2015-6-1 02:39:51 | 显示全部楼层
嘻嘻呵呵飞出去 发表于 2015-6-1 01:26. 鍥磋鎴戜滑@1point 3 acres
第2题的意义在哪里啊?考读写文件的function?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我也很想知道啊,估计直接hashmap会爆内存?考大文件处理?
回复 支持 反对

使用道具 举报

嘻嘻呵呵飞出去 发表于 2015-6-1 03:15:02 | 显示全部楼层
另外第4题除了遍历有更好的方法么?
回复 支持 反对

使用道具 举报

 楼主| chengyaxue 发表于 2015-6-2 10:37:27 | 显示全部楼层
laoxie09 发表于 2015-6-1 02:39
我也很想知道啊,估计直接hashmap会爆内存?考大文件处理?

应该就是考大文件的处理吧,爆内存
回复 支持 反对

使用道具 举报

 楼主| chengyaxue 发表于 2015-6-2 10:38:31 | 显示全部楼层
嘻嘻呵呵飞出去 发表于 2015-6-1 03:15
另外第4题除了遍历有更好的方法么?

从根节点开始, 从左往右,从1开始给节点编号。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后就可以在最后一层做二分查找
回复 支持 反对

使用道具 举报

jeff_xu001 发表于 2015-6-2 11:42:35 | 显示全部楼层
G 家做个备胎吧,OPT 三个月的unemployment period,全部花在这家身上想想也是不一定划算,真要走下来,G家起码1-2个月吧,u know that

onsite 的通过率据说只有不到10%,但薪资和发展也未必这么 worthwhile, Google is not that Google as it
was a few years ago  

FYR
回复 支持 反对

使用道具 举报

嘻嘻呵呵飞出去 发表于 2015-6-2 12:35:52 | 显示全部楼层
chengyaxue 发表于 2015-6-2 10:38
从根节点开始, 从左往右,从1开始给节点编号。
然后就可以在最后一层做二分查找
. From 1point 3acres bbs
嗯对,这样应该是O(N^2)  n是数的高度

上面那个hashmap爆内存何解?我只能想到在文件里sort,然后remove duplicates?
回复 支持 反对

使用道具 举报

Senfan 发表于 2015-6-2 16:37:34 | 显示全部楼层
都已经编号了计数了,为何还要最后一次二分?没看懂什么意思

补充内容 (2015-6-2 16:38):
遍历的复杂度才是O(n),为何多此一举?

补充内容 (2015-6-2 16:39):
哦,不好意思,补充的部分,看成是节点数了~~但还求解惑第一问
回复 支持 反对

使用道具 举报

blueseen 发表于 2015-6-2 18:39:48 | 显示全部楼层
大文件去重的就是考内存的吧,类似外排序,可以把大文件一点一点读入到内存,每次处理一部分,可以选个1000个key,按这1000个key分成1001个文件,每次处理的url的hash值根据key分到不同的文件中,就是比如key是 10,100,那么小于10的分到第一个文件,10到100的分到第二个,大于100的分到第三个。最后一个一个文件去重,最后合并一个文件中。
第三题好像很难,只想到暴力枚举,好的做法可能跟分支的度数的hash值之类的有关吧。
第四题不懂你们在说什么,楼主说的编号不就是已经遍历了么,为什么还要二分查找呢?楼下说的高度的平方复杂度更是看不懂...我觉得考察点应该是剪枝吧,深度优先遍历,优先从左往右,第一个遍历到的叶子层数小于最下面一层的时候停止,不用整个遍历完。
回复 支持 反对

使用道具 举报

blueseen 发表于 2015-6-2 18:51:13 | 显示全部楼层
哦我懂楼主意思了,是二分判断...logn*logn的复杂度...
回复 支持 反对

使用道具 举报

Senfan 发表于 2015-6-2 19:22:48 | 显示全部楼层
blueseen 发表于 2015-6-2 18:51
哦我懂楼主意思了,是二分判断...logn*logn的复杂度...

可以麻烦稍微详细讲下吗?
回复 支持 反对

使用道具 举报

lsscat 发表于 2015-6-3 00:21:36 | 显示全部楼层
你这不是fail是team match。加油,希望还是很大的
回复 支持 反对

使用道具 举报

 楼主| chengyaxue 发表于 2015-6-3 04:17:16 | 显示全部楼层
Senfan 发表于 2015-6-2 19:22
可以麻烦稍微详细讲下吗?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是你一直往左走,到最下层,然后你就知道你的深度啊,然后前面有多少个节点久知道了,你只用算最下面这层的节点数。
比如最后你在第三层
然后在这一层,你知道最左边的那个节点是4,那如果全满的话最右边就是7。然后你就找中间那个5,看那个节点是空还是不是空。
根节点从1开始,你要找5,那个你画一下就知道了,编号很有规律。你是知道怎么一层一层走到5的。
复杂度就logn的平方。。。
主要我也没写代码,就跟那个面试官扯了半天才把这个方法扯出来
回复 支持 反对

使用道具 举报

 楼主| chengyaxue 发表于 2015-6-3 04:19:06 | 显示全部楼层
blueseen 发表于 2015-6-2 18:39
大文件去重的就是考内存的吧,类似外排序,可以把大文件一点一点读入到内存,每次处理一部分,可以选个1000 ...

第三题把树hash化,因为他follow up是说A树很大很大。在上面做很多次query。
回复 支持 反对

使用道具 举报

Senfan 发表于 2015-6-3 09:40:18 | 显示全部楼层
chengyaxue 发表于 2015-6-3 04:17
就是你一直往左走,到最下层,然后你就知道你的深度啊,然后前面有多少个节点久知道了,你只用算最下面这 ...

感谢楼主指教。其实,自己的疑惑是如何找节点“5”,自己想的就是用5不断除以2,找到其父节点的路径,不断压盏,然后不断出栈,这样来找。不知道你是怎么找节点“5”的?
回复 支持 反对

使用道具 举报

小桶 发表于 2015-6-5 06:15:08 | 显示全部楼层
chengyaxue 发表于 2015-6-2 14:19
第三题把树hash化,因为他follow up是说A树很大很大。在上面做很多次query。

LZ能在详细说说怎么hash树结构吗?是说对每一个节点都计算一个hash值,然后存进一个set里。每次query,就是先计算query树根节点的hash值,然后去set里look up一下,看看时候存在相同的值?如果存在,就说明存在子树?这个hash算法还需要保存位置信息啊,是说有现成的算法吗?能给个链接吗?多谢!!!
回复 支持 反对

使用道具 举报

jinzheyu 发表于 2015-11-15 11:35:40 | 显示全部楼层
楼主拿到HR提供的各个面试的feedback了吗?方便分享一下吗?谢谢。
回复 支持 反对

使用道具 举报

bill701 发表于 2015-11-15 13:07:11 | 显示全部楼层
第三题能先对树进行一个预处理吗?在对树先做一遍dfs分析,每个node存储一个自己作为root节点的中序和前序。然后比较的话只要判断是不是有一个点中序和后续都一样就行
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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