citadel quant 电面挂经

quant 电面第一轮，

先是一道code， 给一个n x n distance矩阵A,  Aij 代表行人i距离自行车j有多远，每个行人挑一辆自行车，求

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

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

容 (2019-9-6 21:36):
居然过了一面...有点水啊

x和y夹角 arccos(0.9)，y和z夹角 arccos(0.9)，求x和z夹角多少。
答案就是 0 到 arccos(0.9)+arccos(0.9)
然后用cor=cos(夹角) 可以得解：1到 cos(arccos(0.9)+arccos(0.9))=0.9*0.9-sqrt(1-0.9^2)*sqrt(1-0.9^2)=0.61(三角和公式)。

dfs不是最优解，lz可以参考利口一零溜溜，corr角度解法绿书上有

楼主de第一个题目是 最优匹配问题，
有现成的“匈牙利算法”，但code它可不简单呀，除非学过，还记牢了。

这个视频讲 Hungarian Algorithm 比较清楚
https://www.youtube.com/watch?v=cQ5MsiGaDY8

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

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

jjqphysics 发表于 2019-8-28 23:47
corr(x,y) = 0.9, corr(y,z) = 0.9的话
可以把x和z分解成 x = 0.9y + sqrt(1-0.9^2) u, z=0.9y + sqrt(1- ...

此楼正解，赞

问下楼主说的 是DFS on state space tree吗?

感觉一道都不会……

可以请问下楼主哪个学校的吗？谢谢分享

djz 发表于 2019-8-29 02:27
dfs不是最优解，lz可以参考利口一零溜溜，corr角度解法绿书上有

确实不是最优解哈，感觉dfs+记忆化才是，不过面试官说这样就行了，谢谢你！

jjqphysics 发表于 2019-8-28 23:47
corr(x,y) = 0.9, corr(y,z) = 0.9的话
可以把x和z分解成 x = 0.9y + sqrt(1-0.9^2) u, z=0.9y + sqrt(1- ...

哈哈，厉害了！！原来还可以这么拆解