一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1578|回复: 10
收起左侧

12.14 google电面

[复制链接] |试试Instant~ |关注本帖
sugarheart 发表于 2015-12-16 15:58:33 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
我来发一下面经攒攒人品~第一次电面也没什么经验555
一面:寒暄过后 问我会不会binary search tree。. 鍥磋鎴戜滑@1point 3 acres
1.找到与给定值相同的node
2.找到与给定值最接近的node
3.找到与给定值最接近的两个node. more info on 1point3acres.com
(好吧这部分我还没写完时间就到了。。我用的方法是用第二问的找到第一个node之后,接着按第二问的方法比较value+1和value-1找到的node,直到找到不同的最近的node。。大神勿喷。。我就只能想到这)

二面:面试官先问了问我平时用过什么debug的方法
然后给我看了Introduction to Algorithms 第三版书的封面,描述了这种结构。
1.建数据结构(他描述的比较复杂。。然后我问了一下可以用tree么 他说可以 于是 我就豁然开朗了。。写了left right weight). 1point3acres.com/bbs
2.判断这个结构是不是balanced。balanced定义是左右子树weight之和一样。
3.big O. more info on 1point3acres.com
4.后面就没让写代码,就说一说如果再考虑上length of arm,如何判断是不是balanced. From 1point 3acres bbs
5.写test case的思路
接下来又给我介绍了一下去google实习很有趣。。不知道是不是有希望呢~. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

正在焦急等待中。。。希望有一个好结果555。。。


评分

3

查看全部评分

杰西Jesse 发表于 2015-12-16 22:48:16 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第一轮应该是lc的原题呢~
回复 支持 反对

使用道具 举报

 楼主| sugarheart 发表于 2015-12-17 01:54:08 | 显示全部楼层
关注一亩三分地微博:
Warald
杰西Jesse 发表于 2015-12-16 22:48
第一轮应该是lc的原题呢~
. From 1point 3acres bbs
还真的。。不过没做过。。还是题做的太少了
回复 支持 反对

使用道具 举报

tiantiana 发表于 2015-12-17 02:42:33 | 显示全部楼层
3.找到与给定值最接近的两个node

My solution is like,
1. define a function findNode(TreeNode root, int target, int flag). flag == 0 is to return the node with exact same value, flag = 1 is to find the closest larger node, flag = -1 is to find the cloest smaller node.
2. You should be clear now, right. Use findNode(root, target, 0), node1 = findNode(root, target, 1), node2 = findNode(root, target, -1) to find 3nodes. Then, to use findNode(root, node1.val, 1) and findNode(root, node2.val, -1) to find another 2 nodes.
3. return the 2 closest nodes from those 5 nodes.
回复 支持 反对

使用道具 举报

liruoyuxgd2006 发表于 2015-12-17 06:50:36 | 显示全部楼层
我面试的题目也很简单,第一轮只给了一个followup,第二轮时间耽搁了,连followup question都没有呢
回复 支持 反对

使用道具 举报

wildchild 发表于 2015-12-17 11:32:27 | 显示全部楼层
杰西Jesse 发表于 2015-12-16 22:48
第一轮应该是lc的原题呢~

!杰西!
回复 支持 反对

使用道具 举报

e5399014 发表于 2015-12-28 04:12:04 | 显示全部楼层
结果出来了么
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-31 03:54:25 | 显示全部楼层
第一题是不是找到了最近接的Node, 找第二接近的Node就是找最近的岂不是第一接近的?
回复 支持 反对

使用道具 举报

Teness 发表于 2016-1-31 09:34:16 | 显示全部楼层
1. 第一问很简单,就直接binary search. o(H)
2. 第二问用curr = tree, 一路判断下去, 用这个条件 curr = curr.val < target ? curr.right : curr.left; O(H)
3. 第三问可以用inorder traversal,然后keep 一个list保存最closet的几个node,理论上可以直接 k cloest nodes. O(n)
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-1 15:57:58 | 显示全部楼层
Teness 发表于 2016-1-31 09:34. from: 1point3acres.com/bbs
1. 第一问很简单,就直接binary search. o(H)
2. 第二问用curr = tree, 一路判断下去, 用这个条件 curr =  ...
. 1point3acres.com/bbs
第三问只要两个没必要这么解,inorder复杂度o(n)了,直接binary search三个值,=target, <target, >target,取最接近的两个,复杂度o(logn)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-25 12:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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