Amazon AWS OA

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 s

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

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


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

请问楼主投的岗id是208打头的吗

topaz_64 发表于 2022-8-14 11:05
请问楼主投的岗id是208打头的吗

申过好几个aws的岗位，里边有两个是208打头的，但我也不知道是哪个的oa了哈哈