🎁 Offer多多申请季白金卡十一特惠52% off! 🎁 点击查看详情
查看: 598|回复: 2
收起左侧

Amazon AWS OA

|只看干货
匿名用户-228  2022-8-14 12:31:19 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2022(7-9月) 码农类General 本科 全职@Amazon - 内推 - 在线笔试  | 😐 Neutral 😐 AverageFail | 应届毕业生

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

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

x
Input: array a, int b
Output: int c
Requirement: separate a into c groups while the max differences in every group is less than b
Examples: [1,2,3], the max difference is 3-1=2

解法:
Greedy algorithm
Sort array a,
add number n in a group if it satisfys the difference<b. Otherwise, add n to a new group


证明:
Induction:
Basic step: the algorithm is optimal for the first element.
Inductive step: Assume the algorithm is optimal among first m element, then the algorithm would be optimal among m+1 element
Assume there are g groups in the first m elements.
There are two possibilities:
P1:we can add m+1th element to the previous group, then there are still g groups , which is obviously optimal
P2: we cannot add m+1th element to the previous group. then there are g+1 group
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
st g groups among first m-2 element.
am+1 cannot stay in the same group with any element ak while k<=m-2. THerefore, there are at least g+1 groups.
That completes the proof


如果可以的话,帮我加个大米支持一下吧

评分

参与人数 2大米 +9 收起 理由
skycckk + 1 很有用的信息!
instant_dev + 8 给你点个赞!

查看全部评分


上一篇:Goldman Sachs NG OA
下一篇:Amazon SDE 2023 summer intern OA
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (29)
 
 
3% (1)    👎
请问楼主投的岗id是208打头的吗
回复

使用道具 举报

地里匿名用户
匿名用户-228  2022-8-15 06:12:32
本楼: 👍   0% (0)
 
 
0% (0)   👎
topaz_64 发表于 2022-8-14 11:05
请问楼主投的岗id是208打头的吗

申过好几个aws的岗位,里边有两个是208打头的,但我也不知道是哪个的oa了哈哈
扫码关注一亩三分地求职与职场公众号
更多干货内容等你发现
回复

使用道具 举报

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

本版积分规则

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