Bloomberg跪经

上周电话面了Bloomberg，题目不难, 给你几对公司建数据结构，<母公司， 子公司>

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

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

，原因不太清楚，有可能是她问我怎么优化code的时候没答好

应该用树吧，题目只不过换了种说法，但是问题全都是关于树的操作

我也想过用树，但建起来有点麻烦。而且有些母公司和子公司与别的公司组是不相连的，那么就要有几个树了。然后当她给我一个公司，我还要去树里面找这个公司在不在，感觉比较麻烦

U..union find?

zsun 发表于 2018-1-12 12:01
U..union find?

应该也行。但我那时候不知道这个算法。。。

请教一下，这里的“母公司”的定义是“直接母公司”，还是“根母公司”。。比如假设有关系A->B->C, D->E->C （子->母），那么A和D是没有直接母公司的，但有根部的母公司（有点像grandmother company...）。不知道在面试的时候这种grandmother company也是被当作“母公司”的嘛？如果是这样，那如何定义uncle就有点tricky了。。
还有就是一个公司能不能有多个母公司。。。如果可以的话。。貌似就不能用类似于家族树的抽象了吧。。。

zsun 发表于 2018-1-12 12:01
U..union find?

我感觉不可以用union find。假设我们要插入一个（母，子）关系，而uf的做法是把“子”的根结点的id对应的值，设置成“母”的根结点的id。也就是说用uf我们确实可以知道“子”和“母”的共同的母公司，但是“母”是“子”的直接母公司这一信息丢失了。