【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

狗家电面。。感觉药丸

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

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

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

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

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

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

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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 451, 订阅: 68
  • · google|主题: 68, 订阅: 17
prodigalr 发表于 2016-11-8 04:00:12 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
这题和LC261 graph valid tree一样吗?
回复 支持 反对

使用道具 举报

 楼主| Seraph_Roy 发表于 2016-11-8 04:14:29 | 显示全部楼层
关注一亩三分地微博:
Warald
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呢?
. 1point 3acres 璁哄潧
就如果有两个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/
但是具体mess 的node数量 ...

感觉没那么难…?好像就按照楼上回复的带个map就好…mess的node是有可能有多个
回复 支持 反对

使用道具 举报

caocancabbage 发表于 2016-11-8 07:13:19 | 显示全部楼层
Seraph_Roy 发表于 2016-11-8 07:06
感觉没那么难…?好像就按照楼上回复的带个map就好…mess的node是有可能有多个
.1point3acres缃
哦哦,好的明白了~谢谢~~
回复 支持 反对

使用道具 举报

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 3acres 璁哄潧
如果是有环的话也要打印出两条路吗,这时候也没有两条路啊,就是说第一步还要先判断是不是有环还是是有两个 ...

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

使用道具 举报

小A要当码农 发表于 2016-11-28 10:31:11 | 显示全部楼层
Seraph_Roy 发表于 2016-11-8 10:30
fix的话set null就好了……有环也有两条path呀一条长的一条短的
. 鍥磋鎴戜滑@1point 3 acres
print出两条path 是什么思路呀?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-22 12:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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