回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[岛] Roblox OA 2023 四道 Coding 题 | Summer Software Engineer

🔗
匿名用户-NLFJC  2022-8-24 09:10:51 |倒序浏览

2022(7-9月) 码农类General 本科 实习@roblox - 网上海投 - 在线笔试  | 😃 Positive 😐 Average | Other | 应届毕业生
四道Coding题,三道 Easy 一道 Medium,70min;感觉 Roblox 的框架是,前两道遍历数组,第三道搭建系统(不是太难但需要 parse string),第四道难一些,数组+额外的数据结构,比如 Hash,Prefix Sum 等等;下面是四道完整的题目:

Q1: 计算最终值
- 遍历一遍数组,完成过程中的加减,得到最终值
- O ( n )




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


以上就是四道题了!建议可以
- 第一道 3 min
- 第二道 5 min
- 第三道 30 min
- 第四道 30 min

希望能帮助到需要的人~

补充内容 (2022-09-08 05:30 +8:00):
Q4 的答案
- 用一个 diff array,把每个路灯的起点+1,终点-1
- 然后建一个 res array,从 0 开始,每到 diff array +1 处就+1,到 diff array 就 -1
- 这样,res array 就记录了每个点有多少灯照到~
- 时间:O(n)
- 下面是 C++ 代码
- diff array 参考可见:https://www.geeksforgeeks.org/di ... ge-update-query-o1/

```
#include <vector>
#include <iostream>

using namespace std;

vector<int> calcLamp(vector<vector<int> >& lamps, vector<int>& points){
    int Max = 0;
    // find the max / furthest position
    for(auto& vec : lamps){
        if(vec[1] > Max) Max = vec[1];
    }
    for(int i : points){
        if(i > Max) Max = i;
    }

    // use Max position to initialize the diff array
    vector<int> diff(Max+2, 0);
    vector<int> res(Max+2, 0);

    // diff[] is the difference array
    for(auto& vec : lamps){
        diff[vec[0]] ++;
        diff[vec[1]+1] --;
    }

    // res[] records how many lamps overlap at each position
    for(int i = 1; i < res.size(); i++){
        res[i] = res[i-1] + diff[i];
    }

    // build the answer array
    vector<int> ans;
    for(int point : points){
        ans.push_back(res[point]);
    }

    return ans;
}

int main(){
    vector<vector<int> > lamps;
    vector<int> points = {7, 1, 5, 10, 9, 15};
    lamps.push_back({1, 7});
    lamps.push_back({5, 11});
    lamps.push_back({7, 9});
    calcLamp(lamps, points);
}
```

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

评分

参与人数 8大米 +37 收起 理由
garimell + 1 感谢楼主
匿名用户-UQNGE + 30
JJJEEE + 1 给你点个赞!
LUDL0WS + 1 给你点个赞!
qwertycc123 + 1 很有用的信息!

查看全部评分


上一篇:Yelp Canada VO面经
下一篇:自动巡航店面
地里匿名用户
🔗
匿名用户-KGLMS  2022-8-28 06:03:51
已加米,楼主。能多问问第四题的思路吗,没有想明白时间复杂度为N的解。用你说的方法,不需要先sort一下lamps吗,这样就会有NlogN的复杂度了。谢谢!
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-FPGSQ  2022-9-1 12:26:21
第四题lamps不sort的话没法sweep line吧?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-FPGSQ  2022-9-1 14:41:08
匿名用户 发表于 2022-8-27 15:03
已加米,楼主。能多问问第四题的思路吗,没有想明白时间复杂度为N的解。用你说的方法,不需要先sort一下lam ...

求问最后咋做的呀
回复

使用道具 举报

全局:
最后一题可以用binary indexed tree做吧,时间复杂度是nlogn,O(n)没想到咋做
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NLFJC  2022-9-8 05:31:39
匿名用户 发表于 2022-8-27 17:03
已加米,楼主。能多问问第四题的思路吗,没有想明白时间复杂度为N的解。用你说的方法,不需要先sort一下lam ...

Q4答案已补充到帖子,谢谢留言!
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NLFJC  2022-9-8 05:32:43
小亩_e3cf8fe 发表于 2022-9-1 02:57
最后一题可以用binary indexed tree做吧,时间复杂度是nlogn,O(n)没想到咋做

Binary index tree 应该也可以,用 diff array 可以做到 O( n ),答案已补充~
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-NLFJC  2022-9-8 05:33:57
匿名用户 发表于 2022-8-31 23:26
第四题lamps不sort的话没法sweep line吧?

是的 sweep line 应该需要先sort,不过用 diff array 应该可以 O(n) ,已补充答案~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表