Citadel Software Engineer Intern OA

BarrettNBHT 发表于 2023-7-10 12:38
这个最高赞答案确实有可能acc。但后面说easy c++ solution的那个肯定没戏，因为我跟他写的一样就超时了

最高赞就是对的。后面也有人说了关键就在每个人朋友不超过15个。这样围绕每个人来建立common friends关系最多也就常数（15 choose 2）个。这样最后需要统计的可能suggest的人也就O(n)级别

algrev 发表于 2023-7-10 10:56
最高赞就是对的。后面也有人说了关键就在每个人朋友不超过15个。这样围绕每个人来建立common friends关系 ...

感觉很奇怪 他这个也就30n的复杂度
bfs15^15n的复杂度都是kn 这点优化也算优化

匿名用户 发表于 2023-7-10 14:58
确实。这还是第一次见到暴力数数比bfs快的题lol 死得倒是不冤

quant公司的题都有点这种数学小聪明，跟brain teaser似的，多个心眼子就好

同挂….
不知道怎么优化

你是怎么知道自己是超时的呀？

树杪百重泉 发表于 2023-07-10 02:59:33
同挂….
不知道怎么优化

我的感觉是可以cache，因为一个node如果之前被visited过，轮到他自己时是不用从头开始bfs的。不过不清楚是不是有更聪明的解法

小亩_df40de4 发表于 2023-07-10 03:01:16
你是怎么知道自己是超时的呀？

代码写完可以直接运行，有15个testcase

bfs同挂🥺 那么多题偏偏遇到个没准备到的

树杪百重泉 发表于 2023-7-10 02:59
同挂….
不知道怎么优化

如果只bfs2层也会超时 吗

https://leetcode.com/discuss/int ... Citadel-OA-question
这上面有讨论的， 但不知道实际能过几个test cases

匿名用户 发表于 2023-07-10 09:47:53
如果只bfs2层也会超时 吗

是的，我就是两层bfs超时

微信用户_662d654 发表于 2023-07-10 10:10:27
https://leetcode.com/discuss/interview-question/3742851/Citadel-OA-question
这上面有讨论的， 但不知道实际能过几个test

这个最高赞答案确实有可能acc。但后面说easy c++ solution的那个肯定没戏，因为我跟他写的一样就超时了