一亩三分地论坛

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

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

Google 电面 3.9

[复制链接] |试试Instant~ |关注本帖
simplessssss 发表于 2016-3-19 00:59:32 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
上周三面的google,只面了一条题目. From 1point 3acres bbs

给定一个棵树,树的节点是一个的值是一对pair, 树可能有很多children,然后要做的就是给定一个pair <x, y>查看是不是能在一个树的同一高度上 找到这两个值,并且x只能在第一个位置,
y只能在第二哥位置。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第一问:写算法,楼主写了BFS的算法,也说DFS可以实现.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up: time and space complexity.
follow up: if I want to get space O(logn)的算法,怎么做。 楼主说如果树不是balanced话,dfs也要O(n), 然后面试官说假定树是balanced,就是说高度为O(logn), 这里纠结了一小会,. Waral 鍗氬鏈夋洿澶氭枃绔,
因为没有确定面试官说的话,以为要求O(1)的解法,并且不能用dfs去做。 后来make sure了一下需求,就说dfs很可以解决。.鐣欏璁哄潧-涓浜-涓夊垎鍦
follow up: 找树的规律,每对节点都是一个interval,并且每个子节点将父亲节点的interval进行划分 和interval tree一样。
follow up: 改一开始的code,是不是提高效率,加上interval的剪枝,写了代码。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point 3acres 璁哄潧
PS: 快10天了,hr一直没有消息。。。是不是挂了--楼主的oa也是10多天才有消息,中间一周的时候催了一下hr,现在急需发邮件问的话,会不会太aggressive了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

4

查看全部评分

jjustc 发表于 2016-6-17 05:51:14 | 显示全部楼层
jy_121 发表于 2016-4-29 00:27
你好,我想问下这个题不是说节点值是pair类型吗,为什么你这里画的还是只有一个值?谢谢

"给定一个棵树,树的节点是一个的值是一对pair, 树可能有很多children"

楼主简直给大家出了一道阅读理解,我语文也不好,不知道 怎么理解 楼主的意思
按后面的回复来看 应该是 树的节点是一个的 /(要搜索的)值是一对pair

难道是这个意思?
回复 支持 1 反对 0

使用道具 举报

potaty 发表于 2016-6-17 23:52:41 | 显示全部楼层
读不懂 简直阅读理解
回复 支持 1 反对 0

使用道具 举报

hayreddinluo 发表于 2016-3-19 03:07:56 | 显示全部楼层
祝楼主收到onsite!

确认一下,要不要考虑这种情况,比如找pair<1,2>,然后树是这个样子的. more info on 1point3acres.com
                          1
                   1            3
               1      5     2     4
               1                 2 6 9. Waral 鍗氬鏈夋洿澶氭枃绔,
那么最后一层是满足要求的吧? 如果用DFS是不是还要记录一下当前层如果不够两个,之前那个是否是1?
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-3-19 03:08:36 | 显示全部楼层
hayreddinluo 发表于 2016-3-19 03:07
祝楼主收到onsite!

确认一下,要不要考虑这种情况,比如找pair,然后树是这个样子的

嗯 是~~
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-3-19 08:51:27 | 显示全部楼层
还要继续第二轮,肯定有环节没有做好,而且只做了一轮,加油加油!!
回复 支持 反对

使用道具 举报

stefan0428 发表于 2016-3-19 11:57:12 | 显示全部楼层
楼主能解释下什么是 “树的节点是一个的值是一对pair”, 能给个例子吗? 谢谢
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-3-20 04:10:59 | 显示全部楼层
stefan0428 发表于 2016-3-19 11:57
楼主能解释下什么是 “树的节点是一个的值是一对pair”, 能给个例子吗? 谢谢
.鐣欏璁哄潧-涓浜-涓夊垎鍦
一半的树的节点只有一个int 类型的,这里就是一对pair
回复 支持 反对

使用道具 举报

tmacytr 发表于 2016-3-20 06:31:05 | 显示全部楼层
follow up: 找树的规律,每对节点都是一个interval,并且每个子节点将父亲节点的interval进行划分 和interval tree一样。
follow up: 改一开始的code,是不是提高效率,加上interval的剪枝,写了代码。
楼主 这部分没太看懂 是同一题的follow up吗 数是任意数 还是bst啊?不懂什么叫将父亲节点的interval划分。。。感谢~

补充内容 (2016-3-19 16:31):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
树是任意树 还是bst?
回复 支持 反对

使用道具 举报

 楼主| simplessssss 发表于 2016-3-22 11:53:54 | 显示全部楼层
tmacytr 发表于 2016-3-20 06:31.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up: 找树的规律,每对节点都是一个interval,并且每个子节点将父亲节点的interval进行划分 和interv ...

就是interval tree
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-29 00:27:38 | 显示全部楼层
hayreddinluo 发表于 2016-3-19 03:07
祝楼主收到onsite!

确认一下,要不要考虑这种情况,比如找pair,然后树是这个样子的
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你好,我想问下这个题不是说节点值是pair<>类型吗,为什么你这里画的还是只有一个值?谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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