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

亚麻八月OA SDEII

全局:

2022(7-9月) 码农类General 硕士 全职@amazon - 猎头 - 在线笔试  | 😃 Positive 😣 Hard | Fail | 在职跳槽
八月初拿到的oa。SDEII, 90min 2道题。第二题只做出了暴力解没做出最优解,以为能混过去结果没
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
rong>
第二题少加了一张n的范围的图,经评论提醒加在评论区了

本帖子中包含更多资源

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

x

评分

参与人数 4大米 +23 收起 理由
youngyang + 1 很有用的信息!
wenjun93 + 1 给你点个赞!
H1B_LUCK + 1 很有用的信息!
匿名用户-HETRU + 20

查看全部评分


上一篇:Seven Eight Capital OA所有题目类型
下一篇:Optiver summer 2023 intern oa Q2 Java
推荐
 楼主| dundun1990 2022-9-6 09:03:30 来自APP | 只看该作者
全局:
匿名用户 发表于 2022-09-05 17:41:35
n范围是 1000 还是10000 ?很关键的信息 …
3000。补了原题的图。有用的话记得加米哦

本帖子中包含更多资源

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

x

评分

参与人数 1大米 +1 收起 理由
匿名的 + 1 赞一个

查看全部评分

回复

使用道具 举报

地里匿名用户
🔗
匿名用户-EN36K  2022-9-6 08:39:56 来自APP
第二题 数组长度范围是多少
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-EN36K  2022-9-6 08:41:35 来自APP
匿名用户 发表于 2022-09-05 17:39:56
第二题 数组长度范围是多少
n范围是 1000 还是10000 ?很关键的信息 …
回复

使用道具 举报

全局:
第二题用滑动窗口遍历整个rank数组,同时维护一个sorted_list,里面维护的是排好序的当前的滑动窗口中的元素。每次向右移动的时候,用二分查找更新这个sorted_list,这样时间复杂度是O(logn),总的时间复杂度是O(n^2logn)

补充内容 (2022-09-06 13:46 +08:00):
好像不对,修改数组时间复杂度是o(n),那就是o(n^3)
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-EN36K  2022-9-6 17:22:50 来自APP
hhjimhhj 发表于 2022-09-05 19:34:17
第二题用滑动窗口遍历整个rank数组,同时维护一个sorted_list,里面维护的是排好序的当前的滑动窗口中的元素。每次向右移动的时候,用二分查找更新这个sorted_list,这样时间复杂度是O(
维护数组复杂度太高了 应该维护区间。 这题核心就是算有多少个不连续的区间
回复

使用道具 举报

🔗
hhjimhhj 2022-9-7 07:12:34 | 只看该作者
全局:
匿名用户 发表于 2022-9-6 02:22
维护数组复杂度太高了 应该维护区间。 这题核心就是算有多少个不连续的区间

只维护区间的左右端点吗,那如果一个区间是1,4,5,一个是1,3,5结果是不一样的啊,不太清楚什么意思
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-EN36K  2022-9-7 08:45:18 来自APP
hhjimhhj 发表于 2022-09-06 16:12:34
只维护区间的左右端点吗,那如果一个区间是1,4,5,一个是1,3,5结果是不一样的啊,不太清楚什么意思
是应该不一样的吧

1,4,5 的imblance是1。

1,3,5的imbalance是2
回复

使用道具 举报

🔗
dbsquirrel 2022-9-19 11:39:42 | 只看该作者
全局:
  1. import java.util.HashSet;
  2. import java.util.Set;

  3. class Solution {
  4.     public int findTotalImbalance(int[] rank) {
  5.         int res = 0;
  6.         int n = rank.length;
  7.         for (int i = 0; i < n; i++) {
  8.             int count = 0;
  9.             Set<Integer> set = new HashSet<>();
  10.             for (int j = i; j < n; j++) {
  11.                 count++;
  12.                 if (set.contains(rank[j] + 1)) {
  13.                     count--;
  14.                 }
  15.                 if (set.contains(rank[j] - 1)) {
  16.                     count--;
  17.                 }
  18.                 set.add(rank[j]);
  19.                 if (count > 1) {
  20.                     res++;
  21.                 }
  22.             }
  23.         }
  24.         return res;
  25.     }

  26.     public static void main(String[] args) {
  27.         Solution s = new Solution();
  28.         System.out.println(s.findTotalImbalance(new int[]{4, 1, 3, 2}) == 3);
  29.     }
  30. }
复制代码
这样对吗?不记得在哪个帖子看到的解法。O(n^2)。终于看到这道题的数据范围了。
回复

使用道具 举报

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

本版积分规则

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