回复: 16
跳转到指定楼层
上一主题 下一主题
收起左侧

狗新鲜挂经

全局:

2021(7-9月) Other 其他 硕士 全职@google - 网上海投 - 在线笔试  | | Fail | 应届毕业生

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

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

x
应该是自己想的题目,是道graph题。每个节点和边的定义如下Node{
      int id;
      Link[] links;
}

Link{
     int id
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
间?答曰dfs遍历找到link的bottleneck,最后N/bottleneck就可以了


评分

参与人数 2大米 +9 收起 理由
匿名用户-I103H + 8
wchen329 + 1 很有用的信息!

查看全部评分


上一篇:cruise 店面挂经
下一篇:亚麻 店面
推荐
lllxin37 2021-5-27 10:50:06 | 只看该作者
全局:
BFS + dijkstra , java里的话就是BFS+PriorityQueue 每次挑选传输速度最快的计算
回复

使用道具 举报

全局:
对路径的dfs时间复杂度太高了吧
感觉这个可以用网络流问题解决
回复

使用道具 举报

全局:
请问楼主,link的定义是不是少了点什么东西,怎么知道node和哪个node相连呢??
回复

使用道具 举报

🔗
edyyy 2021-5-27 07:02:27 | 只看该作者
全局:
第一题,无cycle,所以求图直径,用bfs
回复

使用道具 举报

全局:
感谢分享!请问楼主,这是电面吗?还有楼主是否知道挂在哪里?(加米!
回复

使用道具 举报

🔗
 楼主| fuqing04 2021-5-27 10:18:58 来自APP | 只看该作者
全局:
wchen329 发表于 2021-05-26 18:27:06
感谢分享!请问楼主,这是电面吗?还有楼主是否知道挂在哪里?(加米!
应该是没有一遍bug free的关系,第一题我开始写的bfs,后来bfs发现算每条路径时间会非常麻烦然后改的dfs
回复

使用道具 举报

🔗
 楼主| fuqing04 2021-5-27 10:28:17 | 只看该作者
全局:
edyyy 发表于 2021-5-27 07:02
第一题,无cycle,所以求图直径,用bfs

我一开始也是这么写的,后来发现由于每条link传输速度不同,最终的最长时间其实跟直径没有直接关系。所以应该是深度优先算出每条路径所花的最大时间,最后返回最大值。
回复

使用道具 举报

🔗
edyyy 2021-5-27 11:07:10 | 只看该作者
全局:
fuqing04 发表于 2021-5-27 10:28
我一开始也是这么写的,后来发现由于每条link传输速度不同,最终的最长时间其实跟直径没有直接关系。所以 ...

呀,我没仔细看居然速度不一样,那就是Dijkstra 但是是求两点之间最流速短
回复

使用道具 举报

🔗
huxinran 2021-5-27 11:16:18 | 只看该作者
全局:
follow-up 也不是dijkstra吧 说的是不用接受完就可以开始传输,我觉得lz的思路是对的,假设每条link都可以瞬间接到Bytes,  就dfs找到每一条path里最慢的link,
回复

使用道具 举报

🔗
hugjz 2021-5-28 02:37:24 | 只看该作者
全局:
本帖最后由 hugjz 于 2021-5-28 02:41 编辑

link是单向的吗?

如果是双向,因为题目说明了没有环, 那么就没有一个node有两个父亲node的情况,那么楼主的方法可行。不需要dijstra,因为到某一点只有一条路径,不需要求最短路径。

如果是单项的,虽然没有环,但不能排除一个node有两个父亲node的情况,那么楼主的方法不可行。这种情况下要用bottom-up topo



回复

使用道具 举报

🔗
 楼主| fuqing04 2021-5-28 10:30:43 | 只看该作者
全局:
hugjz 发表于 2021-5-28 02:37
link是单向的吗?

如果是双向,因为题目说明了没有环, 那么就没有一个node有两个父亲node的情况,那么 ...

分析非常到位。1-2问题是单向link,并且为了简便计算,可以假设成是一个tree。
回复

使用道具 举报

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

本版积分规则

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