狗挂经

好久之前的狗家onsite，5轮每轮45min，跪的心服口服！

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

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

狗家面完没有feedback。不过第二轮是妥妥的挂了。第一次遇到面这个知识点的。自己太弱继续努力吧。也祝福大家。
求米。

hmmm好难

来回答一下……我研究这个东西研究了一晚上- -
第二题，可以通过二分图匹配来找到一个解，左边是每一列，右边是每一个数，列里有数就连边即可
如果要求所有的或者求数目，这个应该是不可能的，这个问题是#P-complete的即使对于每行只有两个数，见这个paper
http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf

第二轮感觉是不是可以用linkedhashset？ 维持一个list<LinkedHashSet<Integer>> 来代表所有可能的路径。 从左往右扫，每次对于当前两个array的上下两个元素，对于每条linksthashset的路径检查是否可以插入。扫到最后这个list里面就是所有可能的路径。但是想了想，这个方法也是O(2^n)... 请无视这条

第二轮的题目可以再详细一点吗？看起来是个match的题目

补充内容 (2019-12-1 08:26):
我想的一个匹配的做法是这样的，先把同一列两个数连一条边，然后把同一行相同的数连边，然后跑一下二分图匹配就行，复杂度应该是n*m n为点数，m为边数

还是祝楼主好运~~~~

楼主，第二题是找出所有路径还是找出路径有多少条？如果是找出所有路径的话，因为可能的路径最多会有2^n，那生成这些路径的时间复杂度起码要O(2^n)吧

Siil 发表于 2019-12-2 00:15
第二轮的题目可以再详细一点吗？看起来是个match的题目

补充内容 (2019-12-1 08:26):

我觉得这是正解
不过最大流最小割这些东西 要是单纯说说思路还好
要是让写code，我觉得似乎没人会预先复习这些东西

Siil 发表于 2019-12-2 00:15
第二轮的题目可以再详细一点吗？看起来是个match的题目

补充内容 (2019-12-1 08:26):

可太强了。求解释，为什么可以这样建图！

真是服了，这是人做的题？

pj19920720 发表于 2019/12/03 14:07:52
可太强了。求解释，为什么可以这样建图！

大概思想就是通过二分图来模拟矛盾关系，一边是选，一边是不选，但是仔细想想好像我的图好像是错的，想听听有没有其他人的想法