Facebook电面

7.13的电面

扫雷地图，给一个地图的长和宽，以及雷的数量，要求返回一个让雷随机分布的grid，雷用-1表示，随机函数直接用random函数就行

应该是像这样

public int[][] getGrid(int H, int

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

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

挂了电话才想出来，如果是sparse grid可以把随机生成的雷的坐标保存在一个list里面，这样标雷数量的时候就只用遍历雷的坐标就可以了

我想可能是跪了

zhuyinghua1203 发表于 2017-7-14 08:24
Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似，每一次生成一个雷的时间 ...

我不太清楚，我写的就是用hashset记录之前雷的位置，如果hashset里面有这个数再生成一个新的。我说完complexity之后，面试官也没有让优化，估计写成这样就是可以了，然后就直接是followup了

2011051305 发表于 2017-7-14 08:23
感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?
...

是吗？我不太清楚 我是本科毕业有两年工作经验 然后在读一个Online Master，所以我也不知道被分为哪种，recruiter是负责校招的

第二个问题不是太明白，请楼主再说说吧。
如果已经给了二维的matrix，返回某个格子周围那8个格子有几个雷，你都有这个matrix了，直接看一下那8个格子不行吗？
如果是parse grid，只给了你parse grid的表示方法，就像楼主说的那样，把雷也存到一个里面，到时候只检查雷的list。

这题明显比以往的题难。楼主答得很好了 加油

edyyy 发表于 2017-7-14 07:34
这题明显比以往的题难。楼主答得很好了 加油

谢谢安慰啊 太紧张容易脑子短路

我现在没有回复消息的权限 所以回答不了短消息

这应该是用水塘抽样把，时间复杂度O(H*W)

zephyryin 发表于 2017-7-14 08:11
这应该是用水塘抽样把，时间复杂度O(H*W)

只是电面，我估计没有你说的这么复杂

zephyryin 发表于 2017-7-14 08:11
这应该是用水塘抽样把，时间复杂度O(H*W)

而且如果是sparse grid的话M很小复杂度只有O(M)，水塘复杂度O(H*W)就有点不太好了吧

cli94 发表于 2017-7-14 08:07
我现在没有回复消息的权限 所以回答不了短消息

感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?

还是说您的简历很多前端和mobile的project ？

Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似，每一次生成一个雷的时间是一样的？