【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3675|回复: 17
收起左侧

Google电面跪经

[复制链接] |试试Instant~
我的人缘0
yxyxyx 发表于 2016-10-12 02:48:00 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩

2017(10-12月) 码农类General 博士 全职@Google - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
刚刚面完,一个三哥打来的电话。
前半个小时一直在口头描述算法,一个代码都没写。。。我还问了下要不要写伪代码,三哥的回复是你不要写你就给我说。。。

口述题:
具体题目是假设有很多人,组成一个graph,graph的连接关系是父母和子女相连,现在你可以自己定义这个graph格式。然后的子问题:. 围观我们@1point 3 acres
1. 如何判断两个node有血缘关系?.1point3acres网
2. 时间复杂度多少?O(n)还是O(2n)?
3. 对于一个node,从它开始组成的graph诗是个什么结构? (Binary Tree)
4. 如果有两个set里面存了两个node的所有先辈,set sorted如何判断两个node有血缘关系? On做法?
5. 如果一个set长度特别大,另外一个长度较小,怎么做?如果用hashmap,是把大的变成hashmap还是把小的变成hashmap?如果用unordered的hashmap,整体时间复杂度多少(包括构造hashmap和查找)? 如果用ordered hashmap,整体时间复杂度多少(构造hashmap和查找)
6. 一个高度为h的满二叉树有几个node?有几个leaf node?
7. 如果可以对graph进行预处理,让查找时间变短,如何进行预处理?

期间还有很多很多的细节讨论,但是就是不让写代码。。。。-google 1point3acres

说了半个多小时了说完了,然后说让做一道题。一看,没见过,是memmove...

int memmove(void * src, void * dst, int size)

具体就是要把src的memory移到dst的memory里,转移size个byte。。 期间要注意的是void* cast成char * (楼主不幸写的时候没有做),然后还有src转移的时候遇到了NULL怎么办,还有如果src和dst要转移的部分有memory重叠怎么处理。
. Waral 博客有更多文章,

总之跪的很惨。。这要是能拿onsite我当众直播吃翔(并不会)



补充内容 (2016-10-13 00:17):
完了,真的要直播吃翔了。。。。

评分

参与人数 1大米 +50 收起 理由
candy_shmily + 50

查看全部评分


上一篇:10.11 google 电面
下一篇:Thumbtack店面

本帖被以下淘专辑推荐:

我的人缘0
xihaokai1 发表于 2016-10-12 02:57:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
每个node结构里多存一个“太祖”(root)不就O(1)判断有没有血缘关系了?
回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-12 03:01:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
xihaokai1 发表于 2016-10-11 14:57
每个node结构里多存一个“太祖”(root)不就O(1)判断有没有血缘关系了?

这个就是preprocessing的时候要做的事,不过你要做的是把这个node所有的太祖全部存起来(太祖爸爸的...爸爸的爸爸,太祖爸爸的...爸爸的妈妈,太祖妈妈的...妈妈的爸爸,太祖妈妈的...妈妈的妈妈)这样才行,否则会出错
回复

使用道具 举报

我的人缘0
xihaokai1 发表于 2016-10-12 03:04:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
yxyxyx 发表于 2016-10-12 03:01
这个就是preprocessing的时候要做的事,不过你要做的是把这个node所有的太祖全部存起来(太祖爸爸的...爸 ...
. 留学申请论坛-一亩三分地
为什么要存所有的长辈呢,只要是同一个太祖的就是有血缘关系了啊。

补充内容 (2016-10-12 03:05):. 1point 3acres 论坛
哦,明白了,还有妈妈。。。

补充内容 (2016-10-12 03:06):
那看来只能union-find了啊
回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-12 03:11:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
xihaokai1 发表于 2016-10-11 15:04
为什么要存所有的长辈呢,只要是同一个太祖的就是有血缘关系了啊。

补充内容 (2016-10-12 03:05):

这个就看你的graph定义是什么了。

如果你的graph是从child到parents的graph,那么只存一个太祖是不行的。

比如:. 1point3acres

                孩子
             |          |
          爸爸       妈妈
       |        |     |          |
    爷爷   奶奶  外公    外婆

那么你要是只存一个太祖的话,你存哪个呢?如果你存爷爷的话,那么找孩子和妈妈的关系的时候就会找不到,因为妈妈的太祖只可能是外公和外婆,她不知道爷爷这个节点。所以孩子需要存的节点是{爷爷,奶奶,外公,外婆}, 妈妈要存的节点是{外公,外婆},这样才可以。

如果你把图构成父母指向孩子就更不行了,因为爸爸和妈妈共有孩子这个子节点,但是爸爸和妈妈没有血缘关系。。。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-12 03:14:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
xihaokai1 发表于 2016-10-11 15:04. 1point 3acres 论坛
为什么要存所有的长辈呢,只要是同一个太祖的就是有血缘关系了啊。

补充内容 (2016-10-12 03:05):

Union find我当时也提出来了,最后感觉还是不大行,还是得存一下这个节点能遍历到的所有太祖节点(也就是二叉树的叶子节点)才行
回复

使用道具 举报

我的人缘0
xihaokai1 发表于 2016-10-12 03:17:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
yxyxyx 发表于 2016-10-12 03:14. 一亩-三分-地,独家发布
Union find我当时也提出来了,最后感觉还是不大行,还是得存一下这个节点能遍历到的所有太祖节点(也就是 ...

楼主,细想其实这不是二叉树,父母近的可以是近亲乱伦,远的可以是远方亲戚。。。。
回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-12 03:29:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
xihaokai1 发表于 2016-10-11 15:17
. 1point3acres楼主,细想其实这不是二叉树,父母近的可以是近亲乱伦,远的可以是远方亲戚。。。。

lol                  

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

头像被屏蔽
我的人缘0
lll_2013 发表于 2016-10-12 04:49:30 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-12 04:56:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
lll_2013 发表于 2016-10-11 16:49
楼主谢谢分享,说不定你有机会表演当中吃翔,其实录个youtube就行了,我们要求不会很高

所以说非常尴尬,从某个角度上讲我还是愿意直播的,但是几率渺茫
回复

使用道具 举报

我的人缘0
gmixy 发表于 2016-10-12 04:59:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (140)
 
 
0% (1)  踩
额,楼主做第二道题的时候是不是已经趋近崩溃了我估计

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

头像被屏蔽
我的人缘0
lll_2013 发表于 2016-10-12 05:09:48 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0
ytsr 发表于 2016-10-12 05:55:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (357)
 
 
4% (18)  踩
好非主流的题目。. visit 1point3acres for more.

头牌过了我可以免费提供热翔、、
回复

使用道具 举报

我的人缘0
ytsr 发表于 2016-10-12 05:58:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (357)
 
 
4% (18)  踩
lll_2013 发表于 2016-10-12 05:09
我开下脑洞,你打算直播那个品种的翔???
. 一亩-三分-地,独家发布
这题我感觉有点像segment tree,辈分最高的长辈是leaf nod ...

这就不是个树啊。

除非全是独生子女
回复

使用道具 举报

头像被屏蔽
我的人缘0
lll_2013 发表于 2016-10-12 06:44:31 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

我的人缘0
longfeix 发表于 2016-10-12 06:56:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
店面有点bug应该还好,楼主好运
回复

使用道具 举报

我的人缘0
madrid 发表于 2016-10-12 13:38:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  0% (0)
 
 
0% (0)  踩
半个小时口头表述,证明楼主的口语相当强悍。
回复

使用道具 举报

我的人缘0
362802781 发表于 2016-10-13 04:21:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
为什么都是口述题目, 是因为楼主是博士吗
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-25 18:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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