onsite

justin 发表于 2016-8-15 16:48
应该不是只有两个group。
指的应该是，给出一系列words，聚类，每个类中任意两个词都是isomorphic的。我 ...

egg, add, dee  
这能不能形成一个group ?
如果任意两个word 我觉得answer是yes
我只有想到brute force o(n^2) 建graph 然后连每个group 能说说hashTable 怎么mapiing value 的算法吗?

say543 发表于 2016-10-17 02:59
egg, add, dee  
这能不能形成一个group ?
如果任意两个word 我觉得answer是yes

能不能用union find的方法呢？比如找到，egg和add，是一组，把egg设为add的parent, add的parent是自己，然后以后再找到add和dee是的话，那就把add的parent设为dee，dee是自己

pinkdatura 发表于 2016-10-28 06:13
能不能用union find的方法呢？比如找到，egg和add，是一组，把egg设为add的parent, add的parent是自己， ...

这想法也蛮好的 不过扔然是o(n^2) 吧?

请问lz 对那个top 500的exception一直有个疑问 比如显示过去24小时的500个exception 那如果用户在8点钟看结果 是过去24要是的 比如8点零5分看 是不是结果就要刷新？相当于一个realtime的monitor exception的系统？还是我想的方向不对？面试时候的具体要求是什么？应该注意什么问题

pinkdatura 发表于 2016-10-28 06:13
能不能用union find的方法呢？比如找到，egg和add，是一组，把egg设为add的parent, add的parent是自己， ...

不需要union find呀。map 就可以，每次要和所有entries的key找. O(n*numOfGroups), worst case O(n^2).

justin 发表于 2016-8-15 16:48
应该不是只有两个group。
指的应该是，给出一系列words，聚类，每个类中任意两个词都是isomorphic的。我 ...

请问能详细讲一下您的方法么？
比如楼下说的，egg,add,dee，我觉得它们三个不是isomorphic的，假设egg,add构成isomorphic,那么，e和a已经对应，e->a, 且a->e, 那么dee中的e使得其无法与egg或add构成isomorphic。
所以我们到底应该怎么map value呢？任意两个string但凡构成isomorphic之后，它们之间的规则就产生了，例如egg和add，这时再取取dee进行对比么？

odarepsed 发表于 2016-11-28 04:48
请问能详细讲一下您的方法么？
比如楼下说的，egg,add,dee，我觉得它们三个不是isomorphic的，假设egg,a ...

感觉egg add dee 是isomorphic. 我觉得可以这么做:
egg->122
add->122
dee->122
key: 122-> {egg,add,dee}
所以复杂度是O(m*n) m is the number of words and n is the length of each word.

treeguard 发表于 2016-11-28 08:53
感觉egg add dee 是isomorphic. 我觉得可以这么做:
egg->122
add->122

这个122 攒来的? 能说一下吗

加油，加油，此处不留人，自有留人处~