查看: 2564|回复: 6
收起左侧

Amazon OA

|只看干货
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎

2022(7-9月) 码农类General 本科 实习@Amazon - 网上海投 - 在线笔试  | Other | fresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

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

x
投了 2022 Summer Internship,链接:https://www.amazon.jobs/en/jobs/ ... ship-summer-2022-us

第一题:一群不同级别的人要一起上课,每堂课里最高 level和最低 level 必须小于等于 k,问至少需要开几堂课。给定一个levels 数组和一个数字 k,返回一个 num 代表至少要开几堂课
e.g  [1, 2, 3, 4, 5], 2,至少开两堂课,{1, 2, 3} {4, 5}或者{1, 2}, {3, 4, 5}
我用了sort + 贪心,时间复杂度 O(n logn)

第二题:给定一个数组 numbers和 k,问里面满足 包含至多 k 个奇数的 subarray 有几个。且这里 subarray 要去重,一模一样
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
来代表一个 subarray, 放到一个 set 里消重
现在有点后悔,应该用一个 string 来代表一个  subarray (类似 a_0 $ a_1 $ a_2 $ ... )这样,250^1000太大了。不过我用的是 python,还是可以算出来的(手动捂脸)

结果出了更新

评分

参与人数 10大米 +12 收起 理由
xueniuniu98 + 1 给你点个赞!
Mowen + 1 很有用的信息!
yyyingwj + 2 给你点个赞!
必幸直閃魂 + 1 很有用的信息!
血祭天国 + 2 很有用的信息!
AnastasiaDVJW + 1 给你点个赞!
阿筒阿筒 + 1 给你点个赞!
AdobeZ + 1 很有用的信息!

查看全部评分


上一篇:Akuna Capital Python Dev OA 2022
下一篇:罗宾汉|卡洛特
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   90% (54)
 
 
10% (6)    👎
求问第一题能具体说说怎么解吗?明天一定给lz加米,今天用完了orz
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (431)
 
 
0% (4)    👎
有大神再讲讲第二题做法吗
回复

使用道具 举报

 楼主| 小亩_df40de4 2021-9-21 00:19:07 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
AnastasiaDVJW 发表于 2021-9-18 19:03
求问第一题能具体说说怎么解吗?明天一定给lz加米,今天用完了orz

第一题就是贪心,首先考虑给 level 最低的人开课,然后看看这堂课最多能容纳多少人;然后考虑给剩下的人中 level 最低的人开课,如此循环直到每个人都可以上到课
回复

使用道具 举报

 楼主| 小亩_df40de4 2021-9-21 00:19:55 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
现在OA1 过了,准备 OA2 orz,work simulation 好难 QAQ
回复

使用道具 举报

 楼主| 小亩_df40de4 2021-9-21 00:22:31 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
关于第二题,可能一开始我没讲清楚,subarray 是要求连续的,例如 {2, 4}就不是{1, 2, 3, 4}的 subarray
回复

使用道具 举报

 楼主| 小亩_df40de4 2021-9-21 00:27:19 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
第二题代码:
preOddNumList = [0]
for i in range(n):
    isOddNum = numbers[i] % 2
    preOddNumList.append(isOddNum + preOddNumList[-1])
ans = set()
for i in range(n):
    numStr = ""
    for j in range(i+1, n+1):
        numStr += str(numbers[j-1]) + "$"
        if preOddNumList[j] - preOddNumList[i] <= k:
             ans.add(numStr)
return len(ans)

评分

参与人数 2大米 +3 收起 理由
AdobeZ + 1 很有用的信息!
血祭天国 + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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