《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3990|回复: 23
收起左侧

狗家电面。。感觉药丸

[复制链接] |试试Instant~ |关注本帖
Seraph_Roy 发表于 2016-11-8 03:28:35 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 本科 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚电面的狗家,题很简单自己完全没做好哎。。
-google 1point3acres
给一个binary tree,里面的某一些node有problem导致整个树不是binary tree(他问我有可能有什么问题。。实际上就是要么有环,要么就是某个node有俩parent啥的)要找出那些有问题的node而且fix它们。follow up是要print从root到那个node的两条path出来。
. From 1point 3acres bbs
哎第一家电面就是狗家脑子一片空白,感觉面试官给了各种提示才把题做完,还不知道是不是本来还有第二题因为我做太慢了就没做了。。发个面筋求个人品。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 462, 订阅: 111
  • · google|主题: 68, 订阅: 18
prodigalr 发表于 2016-11-8 04:00:12 | 显示全部楼层
这题和LC261 graph valid tree一样吗?
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 04:14:29 | 显示全部楼层
prodigalr 发表于 2016-11-8 04:00
这题和LC261 graph valid tree一样吗?
.1point3acres缃
不太一样。。给的就是一个树让你直接fix……
回复 支持 反对

使用道具 举报

小雨嘀嗒 发表于 2016-11-8 04:50:23 | 显示全部楼层
为什么有两条path呢?
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 04:56:49 来自手机 | 显示全部楼层
小雨嘀嗒 发表于 2016-11-8 04:50
为什么有两条path呢?

就如果有两个pointer指向同一个node的话就会有两条不同的path啦
回复 支持 反对

使用道具 举报

gabrielzhuyun 发表于 2016-11-8 06:09:27 | 显示全部楼层
请问楼主每个node是有一个parent? 那他给了input是什么形式啊?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-11-8 06:33:02 | 显示全部楼层
一个node有两个parent不就是有circle么, dfs带一个visite, 有circle直接cut就好了
回复 支持 反对

使用道具 举报

caocancabbage 发表于 2016-11-8 06:59:19 | 显示全部楼层
有点像 LC 99吧:
https://leetcode.com/problems/recover-binary-search-tree/
但是具体mess 的node数量未知?
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 06:59:48 | 显示全部楼层
huai10 发表于 2016-11-8 06:33
一个node有两个parent不就是有circle么, dfs带一个visite, 有circle直接cut就好了

嗯对大概就是这样
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 07:03:31 | 显示全部楼层
gabrielzhuyun 发表于 2016-11-8 06:09
请问楼主每个node是有一个parent? 那他给了input是什么形式啊?

input就是个root的pointer
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 07:06:41 | 显示全部楼层
caocancabbage 发表于 2016-11-8 06:59
有点像 LC 99吧:
https://leetcode.com/problems/recover-binary-search-tree/. 鍥磋鎴戜滑@1point 3 acres
但是具体mess 的node数量 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
感觉没那么难…?好像就按照楼上回复的带个map就好…mess的node是有可能有多个
回复 支持 反对

使用道具 举报

caocancabbage 发表于 2016-11-8 07:13:19 | 显示全部楼层
Seraph_Roy 发表于 2016-11-8 07:06
感觉没那么难…?好像就按照楼上回复的带个map就好…mess的node是有可能有多个

哦哦,好的明白了~谢谢~~
回复 支持 反对

使用道具 举报

warriorbrant 发表于 2016-11-8 09:19:23 | 显示全部楼层
如果是有环的话也要打印出两条路吗,这时候也没有两条路啊,就是说第一步还要先判断是不是有环还是是有两个parent,如果向course schedule那题的话,是要保持两个set check ring的,这题直接两种情况可以合并了,只要一个set,然后mark过的直接判定error,然后将当前node 的对应子节点设为null,你是怎么fix的呢
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 10:30:53 来自手机 | 显示全部楼层
warriorbrant 发表于 2016-11-8 09:19. 鍥磋鎴戜滑@1point 3 acres
如果是有环的话也要打印出两条路吗,这时候也没有两条路啊,就是说第一步还要先判断是不是有环还是是有两个 ...

fix的话set null就好了……有环也有两条path呀一条长的一条短的
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-28 10:31:11 | 显示全部楼层
Seraph_Roy 发表于 2016-11-8 10:30. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
fix的话set null就好了……有环也有两条path呀一条长的一条短的

print出两条path 是什么思路呀?
回复 支持 反对

使用道具 举报

美腻小码农 发表于 2017-2-1 12:44:25 | 显示全部楼层
总之就是加油
回复 支持 反对

使用道具 举报

美腻小码农 发表于 2017-2-1 12:44:30 | 显示全部楼层
加油加油加油
回复 支持 反对

使用道具 举报

hackenkreuz 发表于 2017-8-10 01:57:32 | 显示全部楼层
dfs或者preorder traversal,follow up带个visited map,应该就可以了
回复 支持 反对

使用道具 举报

jy02535954 发表于 2017-8-10 02:16:14 | 显示全部楼层
为毛不带个HashSet  node在表里就剪枝
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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