查看: 731|回复: 12
收起左侧

[树/链表/图] 讨论一道面试题BFS?

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (633)
 
 
0% (5)    👎

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

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

x
讨论个面试题,在log文件里面有一些记录,记录的形式是:时间戳+服务器名+操作,判断这些操作是否valid,比如 例子1:

1,s1, A : B
1,s1, C : D
1,s1, B : C
在时间1, s1服务器的操作是 A->B->C->D,返回true
例子2:
1,s1, A : B
1,s1, C : D
1,s1, B : C
2,s1, D : E
2,s1, H : G
2,s1, G : S

因为时间时间1是合法的,时间1->2也是可以衔接上的,但是2的操作不valid,返回false


感觉我卡在如何把同一个时刻同一个服务器的操作flatten,比如例子1,其实A-B-C-D可以flatten成 A-D,面试官结束后好像提了一下某个BFS算法可以flatten,有谁了解么?或者给点思路。

谢谢了。

评分

参与人数 1大米 +6 收起 理由
14417335 + 6

查看全部评分


上一篇:很好奇大家在Remote面试时用什么工具讲解思路?
下一篇:纪念一下第一次拿Guardian
柯基101 2021-10-6 05:38:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (4943)
 
 
4% (246)    👎
阿东童鞋 发表于 2021-10-5 14:11
同一时刻的操作的顺序是不定的,bfs怎么处理?也就是flatten的方法是什么?

我没有用什么flatten,bfs就是有的走就往下走啊,

正常的bfs就是有边就往下走,你想象成每一个node有一个时间戳,往下走的时候加一个时间戳的检测,只有大于等于当前时间戳的边才能走,

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

 楼主| 阿东童鞋 2021-10-6 03:08:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (633)
 
 
0% (5)    👎
TensorKeras 发表于 2021-10-5 13:54
感觉有点像course scheduling
可以用Kahn's algorithm来做

如果序列合法,topological sort一遍,可以产生一个有效的序列,取首尾的两个操作就可以flatten。那不合法的情况呢,还得先通过别的方法(union find)先看看是否只有一个component么?

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

 楼主| 阿东童鞋 2021-10-6 05:11:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (633)
 
 
0% (5)    👎
Shubin_ren 发表于 2021-10-5 15:08
这就是标准bfs啊,只是附带上时间戳在每一步,要求每一次扩展后续时间不可以早于前面

同一时刻的操作的顺序是不定的,bfs怎么处理?也就是flatten的方法是什么?
回复

使用道具 举报

qlxf 2021-10-6 02:47:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (6619)
 
 
2% (162)    👎
是要所有的操作都能连接起来?2的操作为什么不对?

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

 楼主| 阿东童鞋 2021-10-6 02:49:40 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (633)
 
 
0% (5)    👎
qlxf 发表于 2021-10-5 13:47
是要所有的操作都能连接起来?2的操作为什么不对?

对,要连起来才对,2的操作连不起来
回复

使用道具 举报

TensorKeras 2021-10-6 02:54:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (104)
 
 
0% (1)    👎
感觉有点像course scheduling
可以用Kahn's algorithm来做

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

TensorKeras 2021-10-6 03:14:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (104)
 
 
0% (1)    👎
如果合法的话 iteration的次数应该就是vertices数

评分

参与人数 1大米 +1 收起 理由
阿东童鞋 + 1 欢迎分享你知道的情况,会给更多积分奖励!

查看全部评分

回复

使用道具 举报

 楼主| 阿东童鞋 2021-10-6 03:17:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (633)
 
 
0% (5)    👎
本帖最后由 阿东童鞋 于 2021-10-5 14:21 编辑
TensorKeras 发表于 2021-10-5 14:14
如果合法的话 iteration的次数应该就是vertices数

哦哦,我再看看kahn 算法

回复

使用道具 举报

TensorKeras 2021-10-6 03:21:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (104)
 
 
0% (1)    👎
回复

使用道具 举报

柯基101 2021-10-6 04:08:39 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (4943)
 
 
4% (246)    👎
这就是标准bfs啊,只是附带上时间戳在每一步,要求每一次扩展后续时间不可以早于前面



先遍历找到所有起点,起点大于1,false,同时记录所有可扩展的
然后就是正常bfs看是否可达,

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

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

本版积分规则

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