狗家OA

国人小哥，OA给了两题，没聊天，直接开始

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题有点迷茫
祝大家都能拿offer！顺便给自己攒点人品……






补充内容 (2019-4-22 13:46):
第二问除了拓扑还有没有什么其他思路，顺便求点大米，最近可能要准备onsite

我的理解，第二题一个判断有向图有没有环的问题吧

如果只问能不能不用discard，用记忆化dfs

pkumcmaster 发表于 2019-4-21 09:50
我的理解，第二题一个判断有向图有没有环的问题吧

如果只问能不能不用discard，用记忆化dfs

我的第一个想法就是有向图，拓扑排序就解决了，后来想到个trick的就是直接从后往前打肯定能打完啊，就把图的想法放弃了，有点紧张了

第二题可以用topology sort。先建立图，把每张牌的penalty当作children nodes。然后遍历graph, 每次找一个没有children的node，然后mark它，并且把有它是child的对应node的children中删掉。如果顺利遍历所有牌，就可以出完。如果有一次找不到这种没有任何children的node，就不行

狗家题目果然多。。

第二题感觉是不是course schedule的变种？

urnotvirgoz 发表于 2019-4-21 15:34
第二题感觉是不是course schedule的变种？

我的感觉也是这样的

urnotvirgoz 发表于 2019-4-21 15:34
第二题感觉是不是course schedule的变种？

好像就是course schedule吧, penalty是children, 顺着找。直到没有children, marked it as played. 请问解法有什么不同吗？

第二题除了拓扑排序还有什么其他思路吗？