Roblox Karat 电面

在Linkedin被recruiter勾搭，跟HR沟通后预约了karat面试
面试总体感觉一般，面试官在印度，时间是那边的晚上了所以他面试的时候不停打哈欠。
有两题，第一题是
给一个一维char的数组，每个位置有三种初始值，X, O和空格，要返回的是在哪个空格处放一个X能够形成XOOOOX（可以为0个或者多个O），并且包在里面的

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

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

官是M开头的印度人

补充内容 (2023-01-30 09:56 +8:00):
UPDATE: 虽然第二题没做出来，但还是通知过了，下一步跟HM约时间聊

‘然后以一个或者两个坐标为圆心画一个半径为radius的圆’
圆心为啥是2个？

sealove999 发表于 2023-3-26 21:20
‘然后以一个或者两个坐标为圆心画一个半径为radius的圆’
圆心为啥是2个？

因为有可能在给定的半径的情况下，一个圆盖不住满足要求的点呀··

请解第二题

第二题，虽然也是brute force，但优化方案可以是启用memo.
1. 对于空格位1，遍历一个圆内所有的点。分成两个set去存，setA记录所有圆内O的位置，setB记录所有空格的位置。
2. 如果setB=0,则返回TRUE
3. 如果setB=1,则对空格位2做相同操作，并且判断空格2的setB是否是空格1
4. 如果setB>1,不符合要求，移动下一个空格。

想问下第二题, radius内只能有两个空格吗， 对X的数目有什么限制不