<
回复: 8
收起左侧

亚麻OA SED2

本楼:   👍  2
100%
0%
0   👎
全局:   2
100%
0%
0

2024(4-6月) 码农类General 硕士 全职@amazon - 内推 - Onsite  | 🙁 Negative 😣 HardPass | 在职跳槽
Recruiter发的OA,俩道题都不简单,第一题没见过,第二题是一道出了名的hard.

1. 第一题有俩个cases超时,可能要用Binary Search优化
2. 第二题用了二维DP,一半cases内存溢出,感觉得优化成一维

时间不够就交了,第三天通知过了,估计他们也知道这破
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
可能这部分答还行?




要是能帮助到的话,加点米朋友们!

本帖子中包含更多资源

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

x

评分

参与人数 9大米 +14 收起 理由
wez10 + 1 给你点个赞!
Falldawn + 2 欢迎分享你知道的情况,会给更多积分奖励!
微信用户_23y9n + 1 赞一个
清道神君 + 5 欢迎分享你知道的情况,会给更多大米奖励!
accd + 1 我也刚过oa,可以加下v吗 hlaccd

查看全部评分


上一篇:买它 PE 2 年经验 HR call
下一篇:GS timeline + 面经

本帖被以下淘专辑推荐:

xinruimuyi 2024-6-19 00:48:15 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   15
100%
0%
0
刚做了oa第一题和楼主一样,sort+sliding window可以解
回复

使用道具 举报

accd 2024-6-16 08:10:12 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   12
92%
8%
1
我也刚过oa,可以加下v吗 hlaccd
扫码关注一亩三分地求职移民公众号
更多干货内容等你发现
回复

使用道具 举报

 楼主| haliluya123 2024-6-17 01:50:58 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   2
100%
0%
0
accd 发表于 2024-6-15 17:10
我也刚过oa,可以加下v吗 hlaccd

加你啦,备注了一亩三分地
回复

使用道具 举报

Falldawn 2024-6-20 09:44:54 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1015
93%
7%
74
本帖最后由 Falldawn 于 2024-6-19 18:46 编辑

第一题就要二分吧

```

public int reduceGifts(int[] prices, int k, int threshold) {
        if (prices == null || prices.length < k) {
            return 0;
        }
        int n = prices.length;
        Arrays.sort(prices);
        int left = 0, right = n - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBig(prices, k, threshold, mid)) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private boolean isBig(int[] prices, int k, int threshold, int mid) {
        int n = prices.length;
        int sum = 0;
        for (int i = n - mid - 1; i >= n - mid - k; i--) {
            sum += prices[i];
            if (sum > threshold) {
                return true;
            }
        }
        return false;
    }
```
回复

使用道具 举报

Falldawn 2024-6-20 11:07:35 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1015
93%
7%
74
第二题也不需要DP吧,也可以算DP
```
public int getMinErrors(String errorString, int x, int y) {
        int mod = (int) (1e9 + 7);
        int a1 = 0, b1 = 0; // a is 0 and b is 1
        int m1 = 0, n1 = 0; // m is number of 01 and n is number of 10
        int a2 = 0, b2 = 0; // a is 0 and b is 1
        int m2 = 0, n2 = 0; // m is number of 01 and n is number of 10
        for (char c : errorString.toCharArray()) {
            if (c == '0') {
                a1++;
                a2++;
                n1 += b1;//all previous 1 can combine with this 0
                n2 += b2;
            } else if (c == '1') {
                b1++;
                b2++;
                m1 += a1;//all previous 0 can combine with this 1
                m2 += a2;
            } else {
                a1++;//! is 0
                n1 += b1;
                b2++;//! is 1
                m2 += a2;
            }
        }
        return Math.min(module(m1, n1, x, y, mod), module(m2, n2, x, y, mod));
    }

    private int module(int a, int b, int x, int y, int mod) {
        return (int)((1L * a * x) % mod + (1L * b * y) % mod) % mod;
    }
```
回复

使用道具 举报

Falldawn 2024-6-21 02:03:50 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1015
93%
7%
74
Falldawn 发表于 2024-6-19 18:44
第一题就要二分吧

```

bug fix
```
public int reduceGifts(int[] prices, int k, int threshold) {
        if (prices == null || prices.length < k) {
            return 0;
        }
        int n = prices.length;
        Arrays.sort(prices);
        if (prices[0] > threshold) {
            return n - k + 1;
        }
        int left = 0, right = n - k + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBig(prices, k, threshold, mid)) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private boolean isBig(int[] prices, int k, int threshold, int mid) {
        int n = prices.length;
        int sum = 0;
        for (int i = n - mid - 1; i >= n - mid - k; i--) {
            sum += prices[i];
            if (sum > threshold) {
                return true;
            }
        }
        return false;
    }
```
回复

使用道具 举报

Heinrich 2024-6-22 08:40:03 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   920
99%
1%
6
本帖最后由 Heinrich 于 2024-6-21 17:47 编辑
Falldawn 发表于 2024-6-20 11:03
bug fix
```
public int reduceGifts(int[] prices, int k, int threshold) {

You already sorted -> O(nlogn), I guess the following binary search doesn't matter really? Hmmm, well, I think binary search is probably still useful given we are not sure about k...
  1. int reduceGiftsa(vector<int> prices, int k, int threshold) {
  2.     if (prices.size() < k) return 0;
  3.     sort(prices.begin(), prices.end(), std::greater<>());
  4.     int window = 0, count = 0;
  5.     for (int i = 0; i < k - 1; i++) {
  6.         window += prices[i];
  7.     }
  8.     for (int i = k - 1; i < prices.size(); i++) {
  9.         window += prices[i];
  10.         if (window > threshold) {
  11.             count++;
  12.             window -= prices[i - k + 1];
  13.         } else {
  14.             break;
  15.         }
  16.     }
  17.     return count;
  18. }
复制代码
回复

使用道具 举报

Falldawn 2024-6-22 08:54:21 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1015
93%
7%
74
Heinrich 发表于 2024-6-21 17:40
You already sorted -> O(nlogn), I guess the following binary search doesn't matter really? Hmmm, w ...

如果你不排序,怎么用二分?
回复

使用道具 举报

Heinrich 2024-6-22 09:24:13 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   920
99%
1%
6
Falldawn 发表于 2024-06-21 17:54:21
如果你不排序,怎么用二分?
我的意思是总体已经是O(nlogn)了,后面是否用二分O(logn)已经不是主要因素了。
回复

使用道具 举报

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

本版积分规则

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