分享一道C家DS电面题

问题大致是：
有一个500w的数据，三列id（用户id，身份id啥之类的），只要有一种id相同的就可以看成是一个人，最后需要对每行数据输出一个标签，相同的人标签要

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

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

点复杂，面试官说还行，问还有没有更优化的，没时间了，分享大家，一起讨论，求加米！

Union Find

先按照id1合并
再按照id2合并
最后按照id3合并

时间复杂度O(n)

我先想到的是类似clustering的办法 把a,b,c 分别看成x,y,z , 比较每一个observation与其他observation 计算 min（deltax, deltay, deltaz)， 把min=0的全部cluster到一类 不过这个也是O（N^2)
如果三列id像example里一样是sorted的话，把a,b,c 分别看成x,y,z , 然后一行一行的比 计算 min（deltax, deltay, deltaz)  如果等于0， 那么下一行就和上一行是一个人， 如果不是 那就是两个人。 这样 O(n)
如果不是sorted的话 ，sort一下 再用上面的方法是O（NlogN+N）

第一感觉是如果有冲突怎么办？

jzhao59 发表于 2019/07/15 21:37:22
第一感觉是如果有冲突怎么办？

为啥会有冲突？

jev9 发表于 2019-7-15 18:25
为啥会有冲突？

如果同一行用户ID和身份ID分别属于不同的人，这种情况怎么办？（如果我的理解没错）

jzhao59 发表于 2019-7-16 08:28
如果同一行用户ID和身份ID分别属于不同的人，这种情况怎么办？（如果我的理解没错）

额。。不会啊，三种id，只要有一种相同就是一个人的

jbdx6308 发表于 2019-7-16 04:38
我先想到的是类似clustering的办法 把a,b,c 分别看成x,y,z , 比较每一个observation与其他observation 计算 ...

这个方法不错，比我的简单多了。。btw，如果用python面试，可以默认是可以用pandas,numpy这些的吗。。

更新一下，有朋友了解电面之后多久会接到通知吗

jbdx6308 发表于 2019-7-16 04:38
我先想到的是类似clustering的办法 把a,b,c 分别看成x,y,z , 比较每一个observation与其他observation 计算 ...

想了一下有个问题，就是这个sort的话，这样三列sort，可以合并的id，有些始终不会相邻啊？
a,b,c
1,33,555
1,44,666
2,44,777
3,55,777
3,66,888
4,77,999
5,88,1000
6,77,333
8,99,555

jev9 发表于 2019/07/16 18:05:58


想了一下有个问题，就是这个sort的话，这样三列sort，可以合并的id，有些始终不会相邻啊？
a,b,c
1,33,555
1,44,666
2,44,777
3,55,777
3,...

啊 也是 sort这样确实不行。 或者可以这样 类似hash map， 先建一个dict，把所有行都放进去 每行对应值为0, 然后一列一列的sort， 先sort a， 把id相同的在dict里都赋予一个值。 然后sort b， 发现id相同的列 就去dict里看 如果有一列已经赋值了， 那其它几列跟着一起赋相同的值
dict不是loop，在里面查找average time complexity 是 O(1)
这样三列的话是time complexityO(3nlogn+3n)  不过因为要存储dict， space complexity 会增加