狗家新鲜面经

iSomnambulate 发表于 2021-4-15 23:57
想问下lz第一题和一衣衣零具体有哪里不一样呀

你说的那题的node里面有left和right，但是面试题里的node只有parent_index（就是这个node的parent的index

已加米，请问楼主第三题第一问是问的如何uniformly的把所有的cells assign给4个player吗？64个cell，每个player assign16个？

ydog5 发表于 2021-04-15 11:50:47
已加米，请问楼主第三题第一问是问的如何uniformly的把所有的cells assign给4个player吗？64个cell，每个player assign16个？

没错zszs

请问第三题followup是说每个玩家的16个格子至少有两个是相连的吗，还是说地图上某两个相连的格子分给同一个玩家
谢谢！

匿名者 发表于 2021-4-16 03:01
没错zszs

谢谢楼主。第一问可以random number % 4做。第二问能再解释一下吗？我理解是如果一个cell已经assign给一个player，那这个cell周围（4 direction）都必须assign给他。并且还保持uniform distribution

ydog5 发表于 2021-04-15 12:06:05
谢谢楼主。第一问可以random number % 4做。第二问能再解释一下吗？我理解是如果一个cell已经assign给一个player，那这个cell周围（4 direction）都必须assig

是周围的四个方向里至少其中任意一个必须assign给同一个player，并且保持uniform

匿名用户 发表于 2021-04-15 12:08:28
是周围的四个方向里至少其中任意一个必须assign给同一个player，并且保持uniform

好的，我想问下对于每个player初始的位置必须random吗？如果不是random的，我们可以把四个角分别assign给4个player，然后对他们轮流expand

ydog5 发表于 2021-04-15 12:16:08
好的，我想问下对于每个player初始的位置必须random吗？如果不是random的，我们可以把四个角分别assign给4个player，然后对他们轮流expand

我的理解是必须random，因为这是一个游戏的初始棋盘生成，设定位置就违反题意了

请问第一题return的forest也是按照array里面存index的方式嘛

第三题uniform 8 * 8 grid 分配 followup: 周围的四个方向里至少其中任意一个必须assign给同一个player，并且保持uniform

如果grid在角上,只有两个方向的选择, 如果边上 有3 个,其他地方有四个。也就是说着2/3/4个grid必须留一个给周边的player, 在做random.nextInt()的时候, 需要同时check这些grids有没有分配给周边的player（这种情况只可能发生在角上, 或者边上）。 每做一次random的时候，检查邻居条件，如果break的话。必须从周边grid的所属player里随机抽取一个设置, 然后把这个grid设置好。继续下一轮。。。

因为只有8 * 8， 所以不大用考虑优化。万一size上去的话,就是另外一个follow up了