查看: 6166| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

[找工就业] google 高频题 删除二叉树的坏边

全局:

2018(4-6月)-CS博士+fresh grad 无实习或全职 | 内推| 码农类General全职@google

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
给一个二叉树,删除一条坏边。看了地里一些相关的帖子,感觉题目描述比较模糊。
所以这道题是不是里扣陆霸四呢?

有没有面过的说说? 谢谢.

上一篇:Google offer review会不会因为opt快到期了挂人?
下一篇:问下大家有遇到过vdartinc.com这个公司的人发过来的邮件
🔗
luogaoqi 2018-4-14 05:25:52 | 只看该作者
全局:
没面过 但是感觉就是 union find直接搞定
回复

使用道具 举报

🔗
misty1007 2018-4-14 07:21:29 | 只看该作者
全局:
是不是dfs一遍 维护一个visited 如果已经visit过了就是坏边 这样就可以了。但是这道题的那个BST的followup 我不太会 借个楼看看有没有面过的前辈能解释一下BST的followup具体是什么题目
回复

使用道具 举报

🔗
xiaozha 2018-4-14 08:47:49 | 只看该作者
全局:
我也觉得应该是union find的变种,如果题意理解正确的话。
回复

使用道具 举报

🔗
liushaobo 2018-4-14 10:18:11 | 只看该作者
全局:
是不是 应该是lc那道有向图去坏边那题?
回复

使用道具 举报

🔗
liushaobo 2018-5-29 06:42:53 | 只看该作者
全局:
wendaomumu 发表于 2018-5-29 06:13
有向图那个题看了答案也是似懂非懂。。。。不知道哪位高人能有好的思路解释下

我觉得discussion最高票那个答案讲的还行。
回复

使用道具 举报

🔗
szyyn95 2018-6-2 09:24:24 | 只看该作者
全局:
luogaoqi 发表于 2018-4-14 05:25
没面过 但是感觉就是 union find直接搞定

无向的是可以union find轻松搞定,有向的麻烦一些。而且现在这题貌似出各种变种了. From 1point 3acres bbs

补充内容 (2018-6-2 09:51):
我看到的一个变种是,如果有多条多余的edge怎么办
回复

使用道具 举报

🔗
hypeng1993 2018-6-7 06:03:52 | 只看该作者
全局:
szyyn95 发表于 2018-6-2 09:24-baidu 1point3acres
无向的是可以union find轻松搞定,有向的麻烦一些。而且现在这题貌似出各种变种了

补充内容 (2018-6-2 0 ...
. .и
有向图是不是只要限制一个node只有一个child或者只有一个parent,就可以union find呀?多条多余边的情况,可不可以在原过程中(比如DFS)找到一条多余的边后,去掉这条,然后接着走下去,继续找呢?我感觉可行?
回复

使用道具 举报

🔗
ootsuka 2018-11-12 03:45:58 | 只看该作者
全局:
想请问如何遍历一个树并存下它所有的edge的?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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