一亩三分地论坛

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

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

12.14 google电面

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

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

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

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

x
我来发一下面经攒攒人品~第一次电面也没什么经验555
一面:寒暄过后 问我会不会binary search tree。
1.找到与给定值相同的node
2.找到与给定值最接近的node
.鐣欏璁哄潧-涓浜-涓夊垎鍦3.找到与给定值最接近的两个node
(好吧这部分我还没写完时间就到了。。我用的方法是用第二问的找到第一个node之后,接着按第二问的方法比较value+1和value-1找到的node,直到找到不同的最近的node。。大神勿喷。。我就只能想到这)

二面:面试官先问了问我平时用过什么debug的方法
然后给我看了Introduction to Algorithms 第三版书的封面,描述了这种结构。
1.建数据结构(他描述的比较复杂。。然后我问了一下可以用tree么 他说可以 于是 我就豁然开朗了。。写了left right weight)
2.判断这个结构是不是balanced。balanced定义是左右子树weight之和一样。. more info on 1point3acres.com
3.big O.鏈枃鍘熷垱鑷1point3acres璁哄潧
4.后面就没让写代码,就说一说如果再考虑上length of arm,如何判断是不是balanced
5.写test case的思路
接下来又给我介绍了一下去google实习很有趣。。不知道是不是有希望呢~. Waral 鍗氬鏈夋洿澶氭枃绔,

正在焦急等待中。。。希望有一个好结果555。。。
. From 1point 3acres bbs
. 鍥磋鎴戜滑@1point 3 acres

评分

3

查看全部评分

杰西Jesse 发表于 2015-12-16 22:48:16 | 显示全部楼层
第一轮应该是lc的原题呢~
回复 支持 反对

使用道具 举报

 楼主| sugarheart 发表于 2015-12-17 01:54:08 | 显示全部楼层
杰西Jesse 发表于 2015-12-16 22:48.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一轮应该是lc的原题呢~

还真的。。不过没做过。。还是题做的太少了
回复 支持 反对

使用道具 举报

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.. 鍥磋鎴戜滑@1point 3 acres
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). visit 1point3acres.com for more.
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
1. 第一问很简单,就直接binary search. o(H)
2. 第二问用curr = tree, 一路判断下去, 用这个条件 curr =  ...

第三问只要两个没必要这么解,inorder复杂度o(n)了,直接binary search三个值,=target, <target, >target,取最接近的两个,复杂度o(logn)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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