Facebook 黑经

dokolo 发表于 2016-12-6 11:25
我把代码放下面了，O(M)时间复杂度，我自己的测试没有发现问题...
不对还请指教...

这样做时间空间都是O(W*H) 吧？有一个O(W*H)的preprocessing

yangluphil 发表于 2016-12-6 11:58
这样做时间空间都是O(W*H) 吧？有一个O(W*H)的preprocessing

这个是不可避免的，因为面试官要求自己初始化，但是这个初始化之外的是O(M)

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

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

yangluphil 发表于 2016-12-6 12:50
用线下算法的话不可避免初始化，但是线上算法比如reservoir sampling就不需要初始化所有元素，所以我觉得 ...

我觉得本质上就是考察在(0,W*H-1)中随机取M个数。开空间的这个消耗是显然的。

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

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

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

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

天竺面试官？可能看完你简历，还没有面你就已经想挂你了，和你水平如何完全无关。
面试的随机性还是很大的。

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

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