脸家虚拟表演挂经

yulian 发表于 2021-3-27 09:44
第三轮 time complexity 要求是什么？
O(n^3 * lg n) 解法不难，
O(n^3) 也能解，用hashset。

老板能讲讲思路吗

第三轮可用哈希表解决。答案在这里：
https://www.geeksforgeeks.org/pr...with-equal-sum/amp/

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

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

楼主能分享下system design的解法或者准备方法吗？都是往哪些方面延伸的呢？

maoZJCQ 发表于 2021-3-27 23:08
楼主能分享下system design的解法或者准备方法吗？都是往哪些方面延伸的呢？

主要考了如何处理很高qps的db read的问题，解决方法就是cache，再cache方面做了讨论

johnHolmes1 发表于 2021-3-29 04:45
主要考了如何处理很高qps的db read的问题，解决方法就是cache，再cache方面做了讨论

多谢多谢

第三题 我想到的也是O(n^2) time
先把整个array sort一下，这样可以避免重复选同样的值。然后就照你n^2遍历存hashmap。
HashMap不要记录index，直接记出现了几次。
一个key出现n次就是有n个pair，（a,b,c,d）次数就是n choose 2了。加起来就行了。
类似这个的最近leetcode周赛里出现过。

qqzz 发表于 2021-3-29 07:46
第三题 我想到的也是O(n^2) time
先把整个array sort一下，这样可以避免重复选同样的值。然后就照你n^2遍 ...

嗯，我也觉得应该是这个做法。不过周赛我每周都在做对这题没印象呢？哪道题能提示一下么？

極端case相當於計算combination，C(n, 4) = n! / (4!*(n - 4)!) = n*(n-1)*(n-2)*(n-3) / 4!
一定得是 O(n^4) 的吧？

第三轮算法题的题解我写过，是力扣的 454 题。我没有权限发链接， 感兴趣的可以访问我自我介绍里面的链接，直接找 454 题即可。