一亩三分地论坛

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

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

狗家电面。。感觉药丸

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

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

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

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

x
刚电面的狗家,题很简单自己完全没做好哎。。

给一个binary tree,里面的某一些node有problem导致整个树不是binary tree(他问我有可能有什么问题。。实际上就是要么有环,要么就是某个node有俩parent啥的)要找出那些有问题的node而且fix它们。follow up是要print从root到那个node的两条path出来。

哎第一家电面就是狗家脑子一片空白,感觉面试官给了各种提示才把题做完,还不知道是不是本来还有第二题因为我做太慢了就没做了。。发个面筋求个人品。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 58, 订阅: 6
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一样吗?

不太一样。。给的就是一个树让你直接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. Waral 鍗氬鏈夋洿澶氭枃绔,
请问楼主每个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/
但是具体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
如果是有环的话也要打印出两条路吗,这时候也没有两条路啊,就是说第一步还要先判断是不是有环还是是有两个 ...

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

使用道具 举报

小A要当码农 发表于 2016-11-28 10:31:11 | 显示全部楼层
Seraph_Roy 发表于 2016-11-8 10:30. Waral 鍗氬鏈夋洿澶氭枃绔,
fix的话set null就好了……有环也有两条path呀一条长的一条短的
. 1point 3acres 璁哄潧
print出两条path 是什么思路呀?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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