一亩三分地论坛

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

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

GOOGLE 11.19面筋

[复制链接] |试试Instant~ |关注本帖
gogo1207 发表于 2015-11-20 07:03:56 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x



国人大哥放水,leetcode原题:https://leetcode.com/problems/number-of-islands/  我用recursive 的 dfs写的,挂电话就发现island判断有个巨大的bug,所有test case都跑不过的--不过面试官似乎也没发现。设计 test case 时候没有想到big data,如果有大量的1,recursive时C++栈会爆掉。我想这个题正确的做法应该用iterative dfs。




给一个无向图,不是全链接,节点上有数字。求最长连续递增数字串的长度
9-1-2-3-4
|  |
2-3
答案是4:1-2-3-4
这个题我用dfs做,不过因为对图的数据结构表示不熟悉,又受到leetcode 题目https://leetcode.com/problems/longest-increasing-subsequence/ 的干扰(leetcode上允许不连续!这个题必须是相邻节点)最后写的简直是correct-free乱七八糟的,面试官都放弃治疗了。follow-up 图改成二叉树。



给一个二叉树,求树的直径。dfs,问了复杂度。. visit 1point3acres.com for more.



在无限数字流中估计中位数。要求可用内存越多中位数越精确。我说用的两个set,和两个heap一样。只是内存不够的时候从maxheap扔最小数,minheap扔最大数。
面试官说如果1  2  3 。。。。。。  10000000   0  -1  -2  -3 。。。。。 -10000000 怎么办,我说random input,面试官说输入流是串行的,不能random,我说用reservoir sampling. 面试官很高兴,也没让我实现代码就聊人生了--。


总体感觉G家面试很拼基本功呀,题目小变化多。面试精神高度紧张时,遇到相似的题高兴死了,很容易忽视小差异掉进坑里。从我个人经历感觉G家不要求bug free,而更看重分析题目的过程。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

rosemary1001 发表于 2015-12-4 03:49:37 | 显示全部楼层
请问楼主onsite结果有了吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-5 10:50:42 | 显示全部楼层
请问这最长上升序列中graph是怎么表示的呢?输入是什么?
回复 支持 反对

使用道具 举报

echo33 发表于 2015-12-7 01:52:47 | 显示全部楼层
树的直径是什么.....?
回复 支持 反对

使用道具 举报

 楼主| gogo1207 发表于 2015-12-8 03:00:11 | 显示全部楼层
rosemary1001 发表于 2015-12-4 03:49
请问楼主onsite结果有了吗?
. 1point 3acres 璁哄潧
实习电面不是onsite呢,现在在等host matching
回复 支持 反对

使用道具 举报

 楼主| gogo1207 发表于 2015-12-8 03:03:55 | 显示全部楼层
bobzhang2004 发表于 2015-12-5 10:50
请问这最长上升序列中graph是怎么表示的呢?输入是什么?

自定义了一个节点类,包含value和相邻节点的指针数组。
graph由节点类的数组表示
回复 支持 反对

使用道具 举报

 楼主| gogo1207 发表于 2015-12-8 03:05:46 | 显示全部楼层
echo33 发表于 2015-12-7 01:52
树的直径是什么.....?

任意两个节点在树上相连经过的节点数叫做它们的距离
所有距离里面最大的是树的直径,不知道有没有错。。
回复 支持 反对

使用道具 举报

echo33 发表于 2015-12-8 04:12:13 | 显示全部楼层
gogo1207 发表于 2015-12-8 03:05
任意两个节点在树上相连经过的节点数叫做它们的距离
所有距离里面最大的是树的直径,不知道有没有错。。

所以最大的就是某个node左右字树里最深的两个叶子的depth之和?.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2015-12-8 04:12):
not depth就是到那个node的距离
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 06:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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