领英详细面经

4）烙印，领英最爱考的找一分钟一小时一天访问次数前K位的页面

请教这个题的思路

第二题如果k=2，就是传统的背包问题，用动态规划有“伪”多项式解。

当k>=3时，是“严格”NP-hard，只能用指数级（暴力搜索）的方法：
https://en.wikipedia.org/wiki/3-partition_problem

实现上可能可以有一些剪枝优化之类的。

magicsets 发表于 2017-7-18 07:31
第二题如果k=2，就是传统的背包问题，用动态规划有“伪”多项式解。

当k>=3时，是“严格”NP-hard，只能 ...

好像说错了.. k>=3时还是可以用DP的，但状态数是(N/k)^k，N为所有数字的和。虽然也是指数级增长，但应该比搜索要快。

magicsets 发表于 2017-7-18 07:37
好像说错了.. k>=3时还是可以用DP的，但状态数是(N/k)^k，N为所有数字的和。虽然也是指数级增长，但应该 ...

如果k是变量的情况要怎么做呢？

第二题很难啊。是不是博士才会考这类比较难的题？

面的是什么组啊，为啥没有系统设计呢

xinzhang1111 发表于 2017-9-17 20:11
面的是什么组啊，为啥没有系统设计呢

第三题就是，翻翻以前的面经，十个里有差不多五个考这个
应该是要用实时采集数据的Kafka， 再加上实时分析数据的工具好像是storm，spark吧
我都只懂点皮毛，简单提了一下，然后主要说如果自己做该怎么做，面试官好像还满意的