一亩三分地论坛

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

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

亚麻OA2 Order Dependency 疑问求解答

[复制链接] |试试Instant~ |关注本帖
xuanyuanyi12 发表于 2016-11-26 13:40:52 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Amazon - 内推 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
亲爱的童鞋们我又来求解答了~~~前面一些问题得到了地里同学们的帮助,非常感谢!我在看Order Dependency的时候又产生了好些疑问,还望做过的同学帮忙解答,感激不尽~
1. 我看网上一个帖子里Order Dependency是由cur和pre组成的,那就是说pre是cur的前提我们要输出的顺序是pre -> cur对吧?
2. 我看见好多同学讲什么在用map建图的时候要用Order的名字不要用Order Object作为Key. 这个我很疑惑,按逻辑来说就算有两个人叫张三也不能说明这两个人是一个人呀!Object要看reference才能决定是不是同一个呀!难道说亚麻的输入不能保证这个?如果不能保证那我要怎么输出?按这个逻辑来讲Order1等于Order2那我输出的序列里要用Order1还是Order2或者是新建一个名字相同的Order?
3. 如果图里有环我是要输出空还是输出null?
我对于第二特别有疑问~~~请做过的同学帮忙解答呀~~~~
. from: 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| xuanyuanyi12 发表于 2016-11-26 13:59:58 | 显示全部楼层
4. 输出是List<Order>吧?这道题我看DFS和BFS应该都可以,大家都是用BFS么?
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-26 14:17:49 | 显示全部楼层
1、对
2、Order Name相同的Order并不一定是同一个Order Object,然而你要把他们算成同一个Order,输出也只要保证Order Name相同就可以,也只会检查你Order Name对不对。确实不合理,也应该是他偷懒的做法,生成OrderDependency的时候省事 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3、题目assume无环
4、是List<Order>,BFS和DFS随意
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-26 14:44:50 | 显示全部楼层
WTYJack 发表于 2016-11-26 14:17. more info on 1point3acres.com
1、对
2、Order Name相同的Order并不一定是同一个Order Object,然而你要把他们算成同一个Order,输出也只 ...

非常感谢~~~
那对于第二问我输出的时候就新建名字相同的order就可以了对吧,如果说这样那根本不用像他们讲的那样在建一个名字和object的map了吧?还有我看他们讲还是处理一下环好要不有的case过不了?好凌乱~~~
非常感谢了~~~~
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-26 14:44:56 | 显示全部楼层
WTYJack 发表于 2016-11-26 14:17
1、对
2、Order Name相同的Order并不一定是同一个Order Object,然而你要把他们算成同一个Order,输出也只 ...

非常感谢~~~
那对于第二问我输出的时候就新建名字相同的order就可以了对吧,如果说这样那根本不用像他们讲的那样在建一个名字和object的map了吧?还有我看他们讲还是处理一下环好要不有的case过不了?好凌乱~~~
非常感谢了~~~~
回复 支持 反对

使用道具 举报

aifer 发表于 2016-11-26 17:22:14 | 显示全部楼层
那个ordermap没必要建。输出的时候自己new就可以。环的话你随意。
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-26 20:17:42 | 显示全部楼层
xuanyuanyi12 发表于 2016-11-26 14:44
非常感谢~~~
那对于第二问我输出的时候就新建名字相同的order就可以了对吧,如果说这样那根本不用像他们 ...

不用建,不放心就处理呗~
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-27 02:18:38 | 显示全部楼层
aifer 发表于 2016-11-26 17:22. 1point 3acres 璁哄潧
那个ordermap没必要建。输出的时候自己new就可以。环的话你随意。

谢谢哒~我又看见有人说有不能完全连通的case, 这个能有啥问题,不连通也算无效case么?1 to 2, 3 to 4,这个不是4231这种输出就可以了么~~~
求解答呀~~~
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-27 04:10:51 | 显示全部楼层
xuanyuanyi12 发表于 2016-11-27 02:18
谢谢哒~我又看见有人说有不能完全连通的case, 这个能有啥问题,不连通也算无效case么?1 to 2, 3 to 4,这 ...

我觉得没啥问题,反正题目里写着assume只有一种可行解,我也就没想那么多。。。
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-27 04:26:49 | 显示全部楼层
WTYJack 发表于 2016-11-27 04:10
我觉得没啥问题,反正题目里写着assume只有一种可行解,我也就没想那么多。。。

OK! 反正童鞋你的test case都过了那我这样假设也一定没问题,这样说的同学可能自己code写错了没找出原因吧~总之非常感谢这么耐心解答~
感动ing~~~
回复 支持 反对

使用道具 举报

NEO_FISH 发表于 2016-11-27 04:49:11 | 显示全部楼层
借楼问个题:是所有order一定都会用上吗?我用拓扑排序的问题就是如果其实有些点用不上的话也会被拓扑排序进去。。。
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-27 05:25:00 | 显示全部楼层
NEO_FISH 发表于 2016-11-27 04:49. visit 1point3acres.com for more.
借楼问个题:是所有order一定都会用上吗?我用拓扑排序的问题就是如果其实有些点用不上的话也会被拓扑排序 ...

童鞋~~~. visit 1point3acres.com for more.
它的输入给的是边没有点吧~~~
那就应该全部要用上吧,即使给点加边也都要用上,你觉得呢?
回复 支持 反对

使用道具 举报

NEO_FISH 发表于 2016-11-27 07:18:27 | 显示全部楼层
xuanyuanyi12 发表于 2016-11-27 05:25
童鞋~~~
它的输入给的是边没有点吧~~~
那就应该全部要用上吧,即使给点加边也都要用上,你觉得呢?

恩 我知道是边,比如这样两个dependency:A->C,B->C,这样的话拓扑排序是A->B->C或者B->A->C。但其实A->C 和B->C是两条路,取其中一条就可以了。虽然全是边但是某些点不需要用上。我大概是这个意思。。所以最后要求的就是拓扑排序就好了嘛?并不是要某一条线路?
回复 支持 反对

使用道具 举报

 楼主| xuanyuanyi12 发表于 2016-11-27 07:45:16 | 显示全部楼层
NEO_FISH 发表于 2016-11-27 07:18
. From 1point 3acres bbs恩 我知道是边,比如这样两个dependency:A->C,B->C,这样的话拓扑排序是A->B->C或者B->A->C。但其实A->C  ...

我觉得就是这样,大家讨论的意思也就是C就是C用一次就好
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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