狗家intern conversion

拖到上周五才面的intern conversion interview
第一轮：假设一个游戏有四个players，一个n * n board (we can assume 8*8), 每个cell被

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

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

ree的问题，面试官中间穿插着不停的问了一些细节问题。




请问第一轮要怎么做。。。求米

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

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

lrf8682004 发表于 2020-12-9 04:27
第一轮是不是循环64次，每次在还没有占16个的player中随机吗？

follow up 怎么办..

第一轮是不是循环64次，每次在还没有占16个的player中随机吗？

第一问容易，random.shuffle([1,2,3,4]*16)然后reshape一下就可以。第二问可以随机选四个点，然后往任意方向BFS or DFS，keep一个counter。如果traverse到别人的点就占领掉，然后别人的counter往回退，某人到16了就不再继续了，除非被别人占掉。最后能占满全部board的时候能保证每个人的count都是16

Actuant 发表于 2020-12-9 06:38
第一问容易，random.shuffle([1,2,3,4]*16)然后reshape一下就可以。第二问可以随机选四个点，然后往任意方 ...

可是这样的话能保证相连吗?
有可能把别人的切断?

reliveinfire 发表于 2020-12-9 09:50
可是这样的话能保证相连吗?
有可能把别人的切断?

好像是有可能切断，那可以占的时候判断一下，切断的话就不往那边走。如果每个都没路能走了（概率应该不大）就重开一局。可能有更简单的解法，暂时没想到

follow up那个确实难搞啊，四个BFS怎么写？而且corner case太多了吧 包围的种类。或者不足16个的。这道题面试官有提示吗

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

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

薏米红豆芡实 发表于 2020-12-10 00:36
面试官只说了backtracking。对，如果一个player不小心把corner包围了，corner里面有不到16个cells到话就 ...

是的，random之后backtrack可能不成功。我感觉我不会，等大佬吧

用iterative BFS? 这样子4个players就能share一个global state. 然后每个player每次move的时候都check 1. boundaries 2. 会不会block其他人. 比如把别人挡住, 或者把空的cell包了起来.