脸书店面

这是个8月初的电面，最近回忆起来所以发个帖子。

#1 利口 衣耳漆舞-变体，3x3 变 任意 nxn ，要求O(1)的时

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

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

(1) 判断这步的胜负手。
第二题，利口-而散，更接近面试官的题目描述

sieg 发表于 2020-9-18 11:39
第一题，O（1） 时间复杂度。。？楼主的意思是O（1）判断是否有胜负手？
第二题，是不是 蠡口 而散

第一题，对的, 每下一步棋，用 O(1) 判断这步的胜负手。
第二题，是的，利口 而散 更接近面试官的题目描述

kylelua 发表于 2020-9-18 21:14
没错，O(1) 是指判断每一步是否获胜的复杂度。步数是一个一个给的。

每row每col每dia各给两个counter，每步加当前步的counter，什么时候counter等于边长就可以返回结果了。

yywwd 发表于 2020-9-18 13:59
#1 利口 衣耳漆舞-变体，3x3 变 任意 nxn ，要求O(1)的时间复杂度解出来
请问楼主时间要求是不是写错了。 ...

每次输入一步，都进行判断这步是否分出了胜负。 O(1)是指每一步的复杂度。

第一题，O（1） 时间复杂度。。？楼主的意思是O（1）判断是否有胜负手？
第二题，是不是 蠡口 而散

再问一下，第一题，从3扩展到n，那么是需要有连续n个，不是3个，才能获胜吗？

sieg 发表于 2020-9-18 11:43
再问一下，第一题，从3扩展到n，那么是需要有连续n个，不是3个，才能获胜吗？

是的。获胜状态是n个棋子连成一线。

merge k sorted array 最优解时间复杂度也要O(nlgn)了吧 ？ 空间复杂度至少O(n) ?

O(1)怎么解出来？？

哦没事了，原来步数是一个一个给出来的。

#1 利口 衣耳漆舞-变体，3x3 变 任意 nxn ，要求O(1)的时间复杂度解出来
请问楼主时间要求是不是写错了。最坏情况下，也就是输入有n*n, 那最快也是n*n的吧

hgon23 发表于 2020-9-18 12:59
merge k sorted array 最优解时间复杂度也要O(nlgn)了吧 ？ 空间复杂度至少O(n) ?

是的 紫薯紫薯

chaoye 发表于 2020-9-18 13:45
哦没事了，原来步数是一个一个给出来的。

没错，O(1) 是指判断每一步是否获胜的复杂度。步数是一个一个给的。